HMMT 二月 2000 · POW 赛 · 第 17 题

HMMT February 2000 — POW Round — Problem 17

If w e are trying to nd the n um b er of w ords of length m from a giv en set of n letters, with ea h letter o uring at least on e in ea h w ord, let us all the answ er T ( m; n ). This is equiv alen t to nding the n um b er of distribution of a set of m distin t balls in to a set of n distin t b o xes, if no b o xes an b e empt y . T ( m; n ) is the sum of all p ossible partitions of the balls (i.e. w e sum all p ossible w a ys of putting the balls in to b o xes (4 in b o x 1, 2 in b o x 2, 1 in b o x 3 for example)). More pre isely , if w e all m to b e the i P m + m + m = m m ! 1 2 3 n um b er of balls in b o x i , then T ( m; n ) = . F or example, m ;m ;m > =1 1 2 3 m ! m ! m ! ::: m ! 1 2 3 n 3! 3! T (3 ; 2) = + = 3 + 3 = 6. Find a re ursiv e pattern for T ( m; n ) in terms of 1!2! 2!1! previous terms (previous meaning a smaller m , a smaller n , or b oth). Hin t: set up a sort of "P as al's T riangle" for T ( m; n ). Pro v e y our answ er using w ords.

解析

T ( m; n ) = n ( T ( m 1 ; n 1) + T ( m 1 ; n )) for 1 < n < m . T o pro v e this, lo ok at T (5 ; 3) and think of it as the n um b er of 5-letter w ords from f A; B ; C g with no missing letters. There are 3 hoi es for the rst letter. After this, the remaining four letters m ust b e lled in, and the rst letter ( all it X ) do es not ha v e to b e used again. There are t w o ases: If X do es not o ur again, then the w ord an b e ompleted in T (4 ; 2) w a ys. If X do es o ur again, then the n um b er of w a ys to omplete the w ord is T (4 ; 3). As w e ha v e n hoi es for the letter X ( rst letter), w e get that T (5 ; 3) = 3 ( T (4 ; 2) + T (4 ; 3)), or the ab o v e, in general.