# Find number of solutions $x_1+x_2+x_3+x_4+x_5+x_6+x_7 = 7$ where $x_i \in \left\{ 0,1,2 \right\}$

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?

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$$

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

• I know, I get this from generating function. – user617243 Apr 1 '19 at 18:32
• So can you compute it? – Robert Israel Apr 1 '19 at 18:32
• 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? – user617243 Apr 1 '19 at 18:34
• I was thinking about pattern $(1+x)^n$ but it also doesn't simplify that – user617243 Apr 1 '19 at 18:39
• 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. – Mark Fischler Apr 1 '19 at 18:44

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.

• $b_n = 1$ because we have $1+x+x^2+x^3...$ and but $a_n$ seems to be finite – user617243 Apr 1 '19 at 20:55
• 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 – Mike Earnest Apr 1 '19 at 22:56

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.

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.