# Determine the Number of Integer Solutions $x_1 + x_2 + x_3 + x_4 = 32$ with restrictions

The Question

My Problem

Part a is straight forward, just $C(35,32)$. I'm having a little difficulty with the restrictions and understanding what they mean. $x_1 > 0$ means we shouldn't have any solutions of the form $(0 + 32)$? If that's the case how would I factor that into my answer? I'm thinking taking the answer to part a and subtracting all the solutions which contain $32+0$ but I don't really know how to count those.

• Hint: for $b)$ let $y_i=x_i+1$ – Mark Bennet Nov 10 '14 at 19:29
• @MarkBennet interesting, so I could kind of think of this as distributing 32 cookies amongst 4 children, where each child receives at least one cookie? – Dunka Nov 10 '14 at 19:32
• Indeed - if that helps you to get the idea. You can translate the others into the same language. – Mark Bennet Nov 10 '14 at 19:41

For part (b), $x_i > 0$ for all $i$, let $y_i = x_i - 1$. Then the problem is equivalent to problem (a), only with a sum of 28 instead of 32 -- the answer is $C(31, 28) == C(31,3)$.

For part (c) let $y_i = x_i-5$ for $i\in \left\{ 1,2 \right\}$ and $y_i = x_i-7$ otherwise. Then you have problem (a) again, with a sum of 8; the answer is $C(7,3)$.

For part (d) the same reasoning gives $C(3,3) = 1$.

For part (e) let $y_i = x_i +2$ to get $C(39,3)$.

For part (f), you can start with the solution to (b), and subtract the cases where $x_4 > 25$. To get the latter, do $y_4 = x_4 -25$, and find an answer of $C(10,3)$ so the answer to part (f) is $C(35,3) - C(10,3)$.


With $\ds{S\ >\ 0}$:

\begin{align} &\color{#66f}{\large\sum_{x_{1}\ =\ 0}^{\infty} \sum_{x_{2}\ =\ 0}^{\infty}\sum_{x_{3}\ =\ 0}^{\infty} \sum_{x_{4}\ =\ 0}^{\infty}\delta_{x_{1} + x_{2} + x_{3} + x_{4},S}} \\[5mm]&=\sum_{x_{1}\ =\ 0}^{\infty}\sum_{x_{2}\ =\ 0}^{\infty}\sum_{x_{3}\ =\ 0}^{\infty} \sum_{x_{4}\ =\ 0}^{\infty}\oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{-x_{1} - x_{2} - x_{3} - x_{4} + S + 1}}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{S + 1}} \pars{\sum_{x\ =\ 0}^{\infty}z^{x}}^{4}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{S + 1}\pars{1 - z}^{4}} \,{\dd z \over 2\pi\ic} \\[5mm]&=\sum_{k\ =\ 0}^{\infty}{-4 \choose k}\pars{-1}^{k} \oint_{\verts{z}\ =\ 1^{-}}{1 \over z^{S - k + 1}}\,{\dd z \over 2\pi\ic} =\pars{-1}^{S}{-4 \choose S} =\pars{-1}^{S}{4 + S - 1 \choose S}\pars{-1}^{S} \\[5mm]&={S + 3 \choose 3} =\color{#66f}{\large{\pars{S + 3}\pars{S + 2}\pars{S + 1} \over 6}} \end{align}

${\bf a}$) $\ds{S = 32}$. $${35 \times 34 \times 33 \over 6} = \color{#66f}{\large 6545}$$ ${\bf b}$) $\ds{S = 28}$ because \begin{align} &\sum_{x_{1}\ =\ 1}^{\infty} \sum_{x_{2}\ =\ 1}^{\infty}\sum_{x_{3}\ =\ 1}^{\infty} \sum_{x_{4}\ =\ 1}^{\infty}\delta_{x_{1} + x_{2} + x_{3} + x_{4},32} \\[5mm]&=\sum_{x_{1}\ =\ 0}^{\infty} \sum_{x_{2}\ =\ 0}^{\infty}\sum_{x_{3}\ =\ 0}^{\infty} \sum_{x_{4}\ =\ 0}^{\infty}\delta_{x_{1} + x_{2} + x_{3} + x_{4},28} \end{align} $${31 \times 30 \times 29 \over 6} = \color{#66f}{\large 4495}$$ ${\bf c}$) $\ds{S = 8}$ because \begin{align} &\sum_{x_{1}\ =\ 5}^{\infty} \sum_{x_{2}\ =\ 5}^{\infty}\sum_{x_{3}\ =\ 7}^{\infty} \sum_{x_{4}\ =\ 7}^{\infty}\delta_{x_{1} + x_{2} + x_{3} + x_{4},32} \\[5mm]&=\sum_{x_{1}\ =\ 0}^{\infty} \sum_{x_{2}\ =\ 0}^{\infty}\sum_{x_{3}\ =\ 0}^{\infty} \sum_{x_{4}\ =\ 0}^{\infty}\delta_{x_{1} + x_{2} + x_{3} + x_{4},8} \end{align} $${11 \times 10 \times 9 \over 6} = \color{#66f}{\large 165}$$

${\tt\mbox{and so on}}$.

For part f) we can use generating functions. The one that models f is

$$G(x)=\left(x+x^2+x^3+...+\right)^3 \left(x+x^2+...+x^{25}\right)$$

these are useful because they reduce combinatoric problems to computational ones. The above gf can be written:

$$g=\left(\frac{x}{1-x}\right)^3 \cdot \frac{ \left(x-x^{26}\right)}{1-x}$$

Now we just need to get at the coefficient of $x^{32}$. I have done that already for you to keep the post small. The term of interest is $4475x^{32}$. So the answer is 4475.

• Thanks for the answer! I have no idea what a generating function is (I think they save that for part II of my course). The answer is useful for someone who does though. – Dunka Nov 11 '14 at 3:08
• Hi; Did not mean to confuse you with too much. Just keep it in mind when you get to part II and good luck. – bobbym Nov 11 '14 at 10:30