# Find the number of positive integer solutions to the equation: $(x_1+x_2+x_3)(y_1+y_2+y_3+y_4)=77.$

Q: Find the number of positive integer solutions to the equation:

\begin{align} (x_1+x_2+x_3)(y_1+y_2+y_3+y_4)=77. \end{align}

The solution given is $\begin{pmatrix} 6\\2 \end{pmatrix}$ \begin{pmatrix} 10\\3 \end{pmatrix}$$+ \begin{pmatrix} 10\\2 \end{pmatrix} \begin{pmatrix} 6\\3 \end{pmatrix}. I am clueless as to how can I go about solving this, given that the method of solving this question should centre around the concepts of combinations, distribution problems and multisets, in particular the formulas for r \mathbb identical objects, n distinct boxes: 1. Each box can hold at most 1 object:$$\begin{align} C_r^n = \begin{pmatrix} n\\r \end{pmatrix} \end{align}$$2. Each box can hold any number of obects:$$\begin{align} H_r^n = \begin{pmatrix} {r+n-1}\\r \end{pmatrix} \end{align}$$3. Each box must hold at least one object - Put 1 object in each box first: r-n objects left. Apply (2), then number of ways:$$\begin{align} \begin{pmatrix} {r-n+n-1}\\{r-n} \end{pmatrix} = \begin{pmatrix} {r-1}\\{n-1} \end{pmatrix}\end{align}$Some help will be deeply appreciated. • Factor$77$, what does this imply about the values of$(x_1 + x_2 + x_3)$and$(y_1 + y_2 + y_3 + y_4)$? From there on, your knowledge of partitioning numbers and combinatorics should come in handy – J. Marx-Kuo Sep 23 '16 at 4:12 • Is it something like what @Nick Peterson suggested below? – Stoner Sep 23 '16 at 5:59 • Yes, his last sentence is especially important – J. Marx-Kuo Sep 23 '16 at 6:52 ## 1 Answer Hint: You probably have specific examples of how to find the number of integer solutions to either$x_1+x_2+x_3=k$or$y_1+y_2+y_3+y_4=k$, for any constant$k$. (If you don't: think about trying to distribute those$k1$'s into boxes, such that each box gets at least one.) To reduce there: note that$77=7\cdot11$, which are both prime. So, if$A\cdot B=77$, you must have one of: •$A=1$,$B=77$•$A=7$,$B=11$•$A=11$,$B=7$•$A=77$,$B=1$Only two of these are possible with all$x_i$and$y_j$positive. • Oh @Nick Peterson do you mean$x_1+x_2+x_3=7$and$y_1+y_2+y_3+y_4=11$, for which in total there are 2 possibilities as stated above and so I have to consider all the aforementioned cases? (Since all$x_i, y_i > 0\$) – Stoner Sep 23 '16 at 5:59
• Alright I got it! Thank you for your suggestion! – Stoner Sep 23 '16 at 7:41