1
$\begingroup$

How many integer solutions are there to $x_1+x_2+x_3+x_4+x_5 = 28$ with:
a) $x_i \ge 0$?
b) $x_i > 0$?
c) $x_i \ge i (i = 1, 2, 3, 4, 5)?$

I know how I would count these, for example, a) I would start with one integer being 28, the rest 0, its combinations, and then subtract and distribute, but how do I count when the numbers start getting smaller and the distributions are difficult to keep track of? Is there an easy method to do this?

$\endgroup$
  • $\begingroup$ for part (c), you can let $y_i=x_i-i$, and the question will be reduced to previous parts. $\endgroup$ – user220124 Mar 12 '16 at 23:50
  • $\begingroup$ Are you familiar with combinations with repetition? $\endgroup$ – N. F. Taussig Mar 12 '16 at 23:50
  • $\begingroup$ Try replacing 28 with a smaller number, like 7, or 3, and doing part (b). If that still doesn't work, try replacing 5 with a smaller number, too. I guarantee you know the sorts of numbers showing up in the answers; the trick is to get some data! $\endgroup$ – Eric Stucky Mar 12 '16 at 23:52
  • $\begingroup$ Use Stars and Bars $\endgroup$ – Foobaz John Mar 12 '16 at 23:53
  • 1
    $\begingroup$ Yes its ${n+r-1 \choose r}$ but how would I incorporate that here? $\endgroup$ – Jodo1992 Mar 12 '16 at 23:53
2
$\begingroup$

How many solutions does the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 28$ have in the non-negative integers?

A particular solution to the equation in the non-negative integers corresponds to the placement of four addition signs in a row of $28$ ones. For instance, $$1 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 + + 1 1 1 1$$ corresponds to the solution $x_1 = 9$, $x_2 = 8$, $x_3 = 7$, $x_4 = 0$, and $x_5 = 4$. Thus, the number of solutions of the equation in the non-negative integers is the number of ways four addition signs can be placed in a row of $28$ ones, which is $$\binom{28 + 4}{4} = \binom{32}{4}$$ since we must choose which four of the $32$ symbols (four addition signs and $28$ ones) will be addition signs.

In general, the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the non-negative integers is equal to the number of ways $k - 1$ addition signs can be inserted into a row of $n$ ones, which is $$\binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}$$ since we must choose which $k - 1$ of the $n + k - 1$ symbols ($n$ ones and $k - 1$ addition signs) will be addition signs or, alternatively, which $n$ of the symbols will be ones.

How many solutions does the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 28$ have in the positive integers?

A particular solution of the equation in the positive integers corresponds to the placement of four addition signs in the $27$ spaces between successive ones in a row of $28$ ones. For instance, $$1 1 1 1 1 1 + 1 1 1 1 1 1 1 + 1 1 1 1 1 1 + 1 1 1 1 1 + 1 1 1 1$$ corresponds to the solution $x_1 = 6$, $x_2 = 7$, $x_3 = 6$, $x_4 = 5$, and $x_5 = 4$. Thus, the number of solutions of the equation in the positive integers is the number of ways four addition signs can be placed in the $27$ gaps between successive ones in a row of $28$ ones, which is $$\binom{27}{4}$$ In general, the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the positive integers is the number of ways $k - 1$ addition signs can be placed in the $n - 1$ gaps between successive ones in a row of $n$ ones, which is $$\binom{n - 1}{k - 1}$$

How many solutions does the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 28$ have in the integers subject to the restraints $x_k \geq k$, $1 \leq k \leq 5$.

Hint: Let $y_k = x_k - k$, $1 \leq k \leq 5$. Substitute $y_k + k$ for $x_k$, $1 \leq k \leq 5$, then solve the resulting equation in the non-negative integers.

$\endgroup$
  • $\begingroup$ What of part c)? $\endgroup$ – Jodo1992 Mar 13 '16 at 1:31
  • $\begingroup$ If you follow my hint, you obtain \begin{align*} y_1 + 1 + y_2 + 2 + y_3 + 3 + y_4 + 4 + y_5 + 5 & = 28\\ y_1 + y_2 + y_3 + y_4 + y_5 & = 13\end{align*} Since $x_k \geq k$, $1 \leq k \leq 5$, $y_k = x_k - k \geq 0$ for $1 \leq k \leq 5$. Thus, we must solve the equation $y_1 + y_2 + y_3 + y_4 + y_5 = 13$ in the non-negative integers. Using the reasoning outlined in (a), the number of solutions is $$\binom{13 + 4}{4} = \binom{17}{4}$$ $\endgroup$ – N. F. Taussig Mar 13 '16 at 1:55
1
$\begingroup$

While the problem does not ask for such, a generating-function approach is particularly flexible.

First case: Each $x_k$ is some nonnegative integer. (Those larger than 28 will not be relevant, but it is simpler not to exclude these cases explicitly.) This is represented by the generating function (GF) $$g(t)=t^0+t^1+t^2+\cdots =\sum_{k=0}^\infty t^k = \frac{1}{1-t}$$ i.e. the geometric series. Integer combinations of $n$ such terms are then generated by $p(t)^n$, with the $k$-th coefficient $[t^k]p(t)^n$ counting how many such combinations add to $k$.

But these coefficients are known: The negative binomial series satisfies $$(1-t)^{-n-1}=\sum_{k=0}^\infty \binom{n+k}{n}t^k\hspace{.5cm}\implies \hspace{.5cm}[t^k](1-t)^{-n-1}=\binom{n+k}{n}$$ and so we can count such combinations explicitly. In particular, we have $[t^{28}]{(1-t)^{-5}}=\binom{32}{4}$ as the answer for part $(a)$ of the question (the same as found in N.F. Taussig's answer).

Second case: We now further require that $x_k>0$. But this only changes the initial GF to $t p(t)=t^1+t^2+t^3+\cdots = t(1-t)^{-1}$. Consequently the relevant coefficient is now $[t^k]t^n p(x)^n=[t^{k-n}]p(x)^n$, and for the case $(n,k)=(5,28)$ we obtain $[t^{23}](1-t)^{-5}=\binom{27}{4}$ (once more in agreement with Taussig's answer) as the number of positive integer combinations.

Third case: Now the $x_k$ have distinct constraints $x_k\geq k$. Hence each has a different GF. But as in the second case, all that changes is that each GF picks up a prefactor i.e. $p_k(t)=t^k p(t)=t^k(1-t)^{-1}$. Hence the GF for integer combinations in the case at hand is $$p_1(t)p_2(t)p_3(t)p_4(t)p_5(t)=\frac{t^1}{1-t}\frac{t^2}{1-t}\frac{t^3}{1-t}\frac{t^4}{1-t}\frac{t^5}{1-t}=\frac{t^{15}}{(1-t)^5}.$$ From this we obtain the number of constrained integer combinations for the case $k=28$ as $$[t^{28}]\frac{t^{15}}{(1-t)^{5}}=[t^{13}]\frac{1}{(1-t)^{5}}=\binom{17}{4}$$ which is in agreement with the result reported in a comment of Taussig's answer.

As a postscript, this method gives us an immediate corollary: The number of integer combinations of $n$ in $k$ terms with constraints $\{x_k\geq a_k\}$ depends only on $\sum_k a_k$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.