2008 iTest Problems/Problem 65

How many rows are drawn?

We will use casework similar to problem 64 but using multinomial coefficients (instead of binomial coefficients) to account for the three different types of patterns: boxes come in triplets, stars come in doublets and circle/x come in singlets.

The decompositions of 15 in (#triplets,#doublets,#singletons) are:

(5,0,0) ; (4,0,3) ; (4,1,1) ; (3,3,0) ; (3,2,2) ; (3,1,4) ; (3,0,6) ; (2,4,1) ; (2,3,3) ; (2,2,5) ; (2,1,7) ; (2,0,9); (1,6,0) ; (1,5,2) ; (1,4,4) ; (1,3,6) ; (1,2,8) ; (1,1,10) ; (1,0,12) ; (0,7,1) ; (0,6,3) ; (0,5,5) ; (0,4,7) ; (0,3,9) ; (0,2,11) ; (0,1,13) ; (0,0,15);

The Multinomial Coefficient $\binom{(a+b+c)}{a,b,c}$ is defined as $\frac{(a+b+c)!}{a!b!c!}$ and represents the number of ways that each (triplet,doublet,singlet) group can be drawn in the sand.

The final calculation is:

$\binom{5}{5,0,0}$ $+\binom{7}{4,0,3}+\binom{6}{4,1,1}$ $+\binom{6}{3,3,0}+\binom{8}{3,2,3}+\binom{8}{3,1,4}+\binom{9}{3,0,6}$ $+\binom{7}{2,4,1}+\binom{8}{2,3,3}+\binom{9}{2,2,5}+\binom{10}{2,1,7}+\binom{11}{2,0,9}$ $+\binom{7}{1,6,0}+\binom{8}{1,5,2} +\binom{9}{1,4,4}+\binom{10}{1,3,6} +\binom{11}{1,2,8} +\binom{12}{1,1,10}+\binom{13}{1,0,12}$ $+\binom{8}{0,7,1} +\binom{9}{0,6,3} +\binom{10}{0,5,5} +\binom{11}{0,4,7} +\binom{12}{0,3,9} +\binom{13}{0,2,11} +\binom{14}{0,1,13} +\binom{15}{0,0,15}$

$=1+35+30+20+560+280+84+105+560+756+360+55+7+168+630+840+495+132+13+8+84+252+330+220+78+14+1$

Page

Toolbox

Search

2008 iTest Problems/Problem 65