CMC - Problem 4

Also, you state that there are 2 tables in the beginning and 4 tables at the end....

Self-explanatory - each table can either have 0, 1, 2, 3, 4, 5, or 6 people at it.

Hello Jatin!

Can you please clarify the following statement? >Case-1: People sit as groups of $(6,4)$, no. of ways = $\binom{10}{4} \times 2!$

From what I understand, $\binom{10}{4}$ denotes the ways to select 4 people out of 10 people. Don't we need to arrange the selected people on the table i.e $\binom{10}{4} \times 6! \times 4! \times 2!$? Can you please help me clear this doubt?

Many thanks!

[Assuming order and selection don't matter] First, we note that there are $3$ ways of sitting the friends at the tables:- this is simply the number of partitions of $10$ where each partition can be at most $6$. To be precise, the partitions are: $10= 4+6= 5+5= 6+4$ Now, let the $i^{\text{th}}$ person receive $a_i$ turkeys, so that $1 \leq a_i \leq 3$, and $\sum a_i= 20$. Using generating functions, the number of solutions is simply the coefficient of $x^{20}$ in $f(x)=(x+x^2+x^3)^{10}$ Note that $f(x)= \left ( \frac{x^4-x}{x-1} \right ) ^{10} = x^{10}(x^3-1)^{10} (x-1)^{-10}$ Recall that for all $|x|<1$, $(x-1)^{-10}= \sum \limits_{k=0}^{\infty} \binom{9+k}{9} x^k$ The binomial expansion of $(x^3-1)^{10}$ is given by $(x^3-1)^{10}= \sum \limits_{k=0}^{10} \binom{10}{k} (-1)^k x^{3k}$ For simplicity, let $c_n$ denote the coefficient of $x^n$ in $(x-1)^{-10}$, and let $d_n$ denote the coefficient of $x^n$ in $(x^3-1)^{10}$. Note that we have already determined the closed forms for $c_n$ and $d_n$: $$ $\begin{array}{lcl} c_n & = & \binom{9+n}{9} \\ d_n & = & (-1)^n\binom{10}{n} \text{ ( iff } n \equiv 0 \pmod{3} \text{ )} \\ & = & 0 \text{ (otherwise)} \end{array}$

Also note that for the term $x^{20}$ to appear in the product, the contributions from the polynomials $(x^3-1)^{10}$ and $(x-1)^{-10}$ must sum up to $10$, since a $x^{10}$ gets multiplied to it. We can afford to ignore the terms whose power of $x$ is $>20$. The coefficient of $x^{20}$ is simply $\sum \limits_{n=0}^{10} c_n d_{10-n}$ Note that $d_n$ is non-zero if and only if $n \equiv 0 \pmod{3}$, so we can simplify this summation further: $\begin{array}{lcl} \sum \limits_{n=0}^{10} c_n d_{10-n} & = & c_{1}d_{9} + c_{4}d_{6} + c_{7}d_{3} + c_{10}d_{0} \\ & = & -\binom{10}{3} \times \binom{10}{9} + \binom{10}{2} \times \binom{13}{9} - \binom{10}{1} \times \binom{16}{9} + \binom{10}{0} \times \binom{19}{9} \\ \end{array}$ Carrying out the sum, we find out that it is equal to $8953$. We have to multiply this with the number of sittings, giving our desired result $8953 \times 3= \boxed{26589}$.

EDIT: Note that the problem statement is insufficient, since it doesn't state whether the friends are identical or distinguishable. I did this by assuming they are identical. If they are distinguishable, we note that any partition of the form $10= a+(10-a)$ can be filled in $\binom{10}{a}$ ways. Summing them over all possible partitions, we find out that the total number of selections is $\binom{10}{6} + \binom{10}{5} + \binom{10}{4}= 672$ We have to multiply this with the total number of ways of distributing the turkeys, giving our final result $672 \times 8953= \boxed{6016416}$.

LaTeX code doesn't work under copy-and-paste.