5
$\begingroup$

Find number of solutions $$ x_1+x_2+x_3+x_4+x_5+x_6+x_7 = 7 \text{ such that } \forall_i x_i \in \left\{0,1,2\right\}$$ I know how I can do this when I don't have restriction $\forall_i x_i \in \left\{0,1,2\right\}$: $$ ooooooooooooo \text{ n+(k-1) = 7 + (7-1) = 13 balls }$$ $$ oo||o|oo|o|o| \text{ k-1 = 6 balls I replace with sticks }$$ and I have $$ 2 + 0 + 1 + 2 + 1 + 1 + 0 = 7 $$ I can do this in $$ \binom{n+k-1}{k} = \binom{13}{7} $$ ways. But how to deal with additional restriction?

$\endgroup$
3
$\begingroup$

The number of unique combinations of numbers summed to achieve $7$ in such a way are $$\{1,1,1,1,1,1,1\}$$ $$\{2,1,1,1,1,1\}$$ $$\{2,2,1,1,1\}$$ $$\{2,2,2,1\}$$ So the total number of solutions is given by $$\frac{7!}{7!}+\frac{7!}{5!}+\frac{7!}{3!\cdot2!\cdot2!}+\frac{7!}{3!\cdot3!}=393$$

$\endgroup$
5
$\begingroup$

Hint: The answer is the coefficient of $x^7$ in $(1 + x + x^2)^7$.

$\endgroup$
7
  • $\begingroup$ I know, I get this from generating function. $\endgroup$ – user617243 Apr 1 '19 at 18:32
  • $\begingroup$ So can you compute it? $\endgroup$ – Robert Israel Apr 1 '19 at 18:32
  • $\begingroup$ Do you mean manual? Chmm, there is a lot of calculus. But what if there will be not $7$ but $77$? Unless you think about some smarter way? $\endgroup$ – user617243 Apr 1 '19 at 18:34
  • $\begingroup$ I was thinking about pattern $(1+x)^n$ but it also doesn't simplify that $\endgroup$ – user617243 Apr 1 '19 at 18:39
  • $\begingroup$ The result for any particular exponent does not have a nice closed form expression. To use your example, for $77$, the answer is $27\cdot 19 \cdot 233 \cdot 675602617$ times a $22$-digit prime. $\endgroup$ – Mark Fischler Apr 1 '19 at 18:44
4
$\begingroup$

Hint: You want the coefficient of $x^7$ in $$ (1+x+x^2)^7=\left(\frac{1-x^3}{1-x}\right)^7=(1-x^3)^7\times (1-x)^{-7} $$ Now, $(1-x^3)^7$ and $ (1-x)^{-1}$ are the generating functions of two nice series, $a_n$ and $b_n$; can you find them? Once you do, since you want the convolution of these two series: $$ \sum_{k=0}^7 a_kb_{n-k}. $$ Furthermore, you will find that $a_k$ equals zero unless $k$ is a multiple of $3$, so that the above summation is has only three nonzero terms and is therefore easily computable by hand.

$\endgroup$
2
  • $\begingroup$ $b_n = 1 $ because we have $1+x+x^2+x^3...$ and but $a_n$ seems to be finite $\endgroup$ – user617243 Apr 1 '19 at 20:55
  • $\begingroup$ Yes, $a_n$ is finite. $a_{3k}=\binom{7}{k}(-1)^k$, and $a_{3k+1}=a_{3k+2}=0$. But you expanded $(1-x)^{-7}=\frac1{(1-x)^7}$ incorrectly. Use Newton's binomial theorem. @VirtualUser $\endgroup$ – Mike Earnest Apr 1 '19 at 22:56
2
$\begingroup$

The "closed form answer" for the number of ways to assign $\{x_1, x_2, \cdots ,x_k\}$ such that $\forall n : x_n \in \{0,1,2\}$ and $\sum_{n=1}^k x_n = k$ is, for odd $k$ $$ F^{-\frac{k}2, -\frac{k-1}2}_1(4) $$ and for even $k$ $$ F^{-\frac{k-1}2, -\frac{k}2 }_1(4) $$ These $F^{a,b}_c$ are hypergeometric functions.

This is obtained by letting $n$ be the number of $2$s used and doing $$ \sum_{n=0}^\left\lfloor{\frac{k}2}\right\rfloor \binom{k}{n}\binom{k-n}{k-2n} $$ and using the techniques put forth in Concrete Mathematics.

$\endgroup$
1
$\begingroup$

From the theory of Generating Functions it's clear the answer boils down to finding the coefficient of $x^7$ in $(1 + x + x^2)^7$,

Write out the equivalent of Pascal's Triangle for the Trinomial Coefficients, or look it up, or write a quick program to generate them (each term is the sum of the three terms, above left, directly above, above right) $$1$$ $$1 : 1 : 1$$ $$1: 2: 3: 2: 1$$ $$1: 3: 6: 7: 6: 3: 1$$ $$1: 4: 10: 16: 19: 16: 10: 4: 1$$ $$1: 5: 15: 30: 45: 51: 45: 30: 15: 5: 1$$ $$1: 6: 21: 50: 90: 126: 141: 126: 90: 50: 21: 6: 1$$ $$1: 7: 28: 77: 161: 266: 357: 393: 357: 266: 161: 77: 28: 7: 1 $$ The number sought is the central coefficient in Row 7, the 393.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy