# 2008 iTest Problems/Problem 65

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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$