HMMT 二月 2000 · POW 赛 · 第 17 题
HMMT February 2000 — POW Round — Problem 17
题目详情
英文原题
- If we are trying to nd the number of w ords of length m from a giv en set of n letters,
with each letter o uring at least on e in each w ord, let us all the answ er T ( m; n ).
This is equiv alen t to nding the number 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 be empt y . T ( m; n ) is the sum of all p ossiblepartitions of the balls (i.e. we 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 we all m to be theim + m + m = m pm !
1 2 3
number 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 asort 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 number of 5-letter w ords from f A; B ; C g with nomissing letters. There are 3 hoi es for the rst letter. After this, the remaining fourletters m ust be lled in, and the rst letter ( all it X ) do es not have to be used again.
There are t w o ases:
If X do es not o ur again, then the w ord an be ompleted in T (4 ; 2) w a ys.
If X do es o ur again, then the number of w a ys to omplete the w ord is T (4 ; 3).
As we have n hoi es for the letter X ( rst letter), we get that T (5 ; 3) = 3 ( T (4 ; 2) +
T (4 ; 3)), or the ab o v e, in general.