# Newton Binomial to find $(x_1+x_2+x_3)(x_4+x_5+x_6+x_7)=77$

What is the number of solutions to $$(x_1+x_2+x_3)(x_4+x_5+x_6+x_7)=77$$, where $$x_1,x_2,\dots,x_6,x_7$$ are non negative integers? Obviously the $$2$$ multipliers are $$1 \times 77$$ and $$7 \times 11$$, so we have $$x_1+x_2+x_3 = 1,7,11,77$$ and $$x_4+x_5+x_6+x_7 = 1,7,11,77$$.

• Have you heard of stars and bars? Mar 22 at 22:25
• Obviously I am not an expert... Mar 22 at 22:26
• You should reverse one of $1,7,11,77$.
– user
Mar 22 at 22:28
• That's alright. It turns out that the number of nonnegative integer solutions to $x_1+x_2+\cdots+x_k = n$ is $\binom{n+k-1}{n}$, where $\binom{}{}$ is the binomial coefficient. A reference can be found at math.stackexchange.com/questions/910809/…. For your problem, you can handle the cases separately: the number of ways for $x_1 + x_2 + x_3 = 1$ and $x_4 + x_5 + x_6 + x_7 = 77$, etc. Mar 22 at 22:30
• @octave - Would you like to post this as an answer? Mar 22 at 22:37

Recall the method of "stars and bars," which tells us that the number of nonnegative integer solutions to the equation $$x_1 + x_2 + \cdots + x_k = n$$ is $$\binom{n+k-1}{n}.$$
There are four cases, as you pointed out. The tuple $$(x_1 + x_2 + x_3, x_4 + x_5 + x_6 + x_7)$$ can only equal $$(1, 77)$$, $$(7, 11)$$, $$(11, 7)$$, or $$(77, 1)$$. In the first case, where $$x_1 + x_2 + x_3 = 1$$ and $$x_4+x_5+x_6+x_7=77$$, the number of solutions is $$\binom{3}{1}\binom{80}{77}.$$
Applying this reasoning for the other three cases, we get that the total number of solutions is $$\binom{3}{1}\binom{80}{77} + \binom{9}{7}\binom{14}{11} + \binom{13}{11}\binom{10}{7} + \binom{79}{77}\binom{4}{1}.$$