Find the number of integral solutions of $x_1, x_2, \dots, x_6$ satisfying the equations [closed]

Find the number of integral solutions of $x_1, x_2, \dots, x_6$ satisfying the equations

\begin{align}x_i &\ge 0\\ {}x_1 + \phantom{6}x_2 +\phantom{6} x_3 +\phantom{6} x_4 +\phantom{6} x_5 +\phantom{6} x_6 &= n \\ x_1 + 2x_2 + 3x_3 + 4x_4 + 5x_5 + 6x_6 &= c\end{align}

Solution 1:

[Edited 4/2/16 to clarify exposition]

As a warmup, let's consider the number $a(n,c)$ of sequences of $n$ rolls of a six-sided die, such that the sum of the rolls is $c$. There is not going to be a simple formula for the answer, though it can be encoded (and computed) using generating functions. For example, if $n=2$, we obtain the following counts:

$$\begin{array}{c|ccccccccccccc} c & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ a(2,c) & 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 5 & 4 & 3 & 2 & 1 \ \end{array} $$

This is piecewise linear; in general you are essentially taking an $n$-fold convolution of a uniform distribution over an interval, and you end up with a distribution which is piecewise described by polynomials of degree at most $n-1$). It's not hard to see that $a(n,c)$ is the coefficient of $s^n t^c$ in $1/(1-s(t+t^2+\cdots+t^6))$.

The problem you are asking is related, but you consider two sequences of throws to be the same if they differ only in the order of the throws. In other words, this is the number of partitions of $c$ into $n$ positive parts, each part at most $6$. Let's call this $b(n,c)$; to clarify the difference, $a(2,3)=2$ (the two sequences of throws are $(1,2)$ and $(2,1)$), but $b(2,3)=1$ since these sequences are the same up to reordering.

To find the generating function for $b(n,c)$: use a variable $s$ to keep track of the sum of the $x_i$'s [in your first equation], and a variable $t$ to keep track of the sum of the $i x_i$'s [in the second equation]. The answer you are looking for is the coefficient of $s^n t^c$ in the product $$(1+st+s^2t^2+\cdots)(1+st^2+s^2t^4+\cdots)\cdots(1+st^6 +s^2t^{12}+\cdots),$$ which can be written more compactly as $$\prod_{i=1}^6 \frac1{1-st^i}.$$

To see this, $x_1$ (the number of ones thrown) determines the term to pick from the first sum, contributing $s^{x_1}t^{x_1}$. $x_2$ determines the term to pick from the second sum, contributing $s^{x_2}t^{2x_2}$, and so on. Extracting the coefficient of $s^n t^c$ at the end gives the number you want.

Finally, we remark that $a(n,c)$ can be computed recursively: $a(n,c)=0$ if $n$ or $c$ are negative; $a(0,0)=1$, and $$a(n,c)=a(n-1,c-1)+a(n-1,c-2)+\cdots+a(n-1,c-6)$$ if $n>0$. This can be seen from the generating function or directly from the dice-throwing interpretation. The generating function for $b(n,c)$ implies that they can be computed recursively as well, but the recurrence is not as easy to describe directly.

Solution 2:

Let's consider a system of equations:

\begin{align}\\ \sum_{i=1}^k \phantom{1} x_i& = n \\ \sum_{i=1}^k ix_i& = c\end{align}

Where $x_i \geqslant 0$ , $x_i \in \mathbb{Z}$. $n$ and $c$ are non negative integers.

I can define a function $s(k,n,c)$ as the number of solutions. Using recursion properly I obtain: $$s(k,n,c)=s(k,n-1,c-1)+s(k-1,n,c-n) \label{eq:1} \tag{1}$$

Note that if $x_1\neq 0$ then the set of such a solutions is equinumerous with the set of solutions where instead of $n$ we have $n-1$ and instead of $c$ is $c-1$. Substracting one from first variable is a bijection between the solutions.If $x_1=0$ then I can obtain this same kind of equations by substracting first equastion from the second one, but in that case $k$ is decremented by one.

Discusing boundary cases:

$s(0,n,c) = 0$ , $s(1,n,c) = 1$ only if n and c are non negative and equal, otherwise $s(1,n,c) = 0$. $s(2,n,c) = 1$ only if $0\leqslant n\leqslant c \leqslant 2n$, otherwise $s(2,n,c)=0$.

If $k\geqslant 3$ then $s(k,n,c)=1$ when $n=c$. If $n>c$ or $c>k\ n$ then $s(k,n,c)=0$. Note that: $$\sum_{i=1}^k ix_i=\sum_{i=1}^k \sum_{j=i}^k x_j\leqslant \sum_{i=1}^k \sum_{j=1}^k x_j = k\ n$$ $$(\sum_{i=1}^k \sum_{j=i}^k x_j= \sum_{i=1}^k \sum_{j=1}^k x_j) \Rightarrow x_k = n$$ When $n=0$ or $c=0$ then $s(k,n,c)=1$ if $n=c$ otherwise $s(k,n,c)=0$

You can obtain your solution by using formula \eqref{eq:1} with taking into account border cases as I discussed and substituting 6 as $k$.