2008 iTest Problems/Problem 65

Revision as of 07:13, 22 January 2019 by Timneh (talk | contribs) (Created page with "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 t...")
(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$

Invalid username
Login to AoPS