# Find the number of solutions of the equation $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = N$ subject to constraints

I have the following equation

$$x_1+x_2+x_3+x_4+x_5+x_6= N$$

and constraints on $x_i$ where $1\leq i\leq 5$ is $1\leq x_i\leq k$ and constraint on $x_6$ is $1\leq x_6\leq M$

How to solve this using permutation and combination?

• Do you know multinomial theorem? – Jaideep Khare May 8 '17 at 10:30
• Please read this tutorial on how to typeset mathematics on this site. – N. F. Taussig May 8 '17 at 10:35

Using generating functions, the answer is the coefficient of $x^{N}$ in the expansion below:

$\left(x + x^{2} + \ldots + x^{k}\right)^{5}\left(x + x^{2}+ \ldots + x^{M}\right)$

The reasoning is as follows: the problem is equivalent to counting the number of ways we can choose $N$ items from $6$ boxes each containing (perhaps infinite) items all of a single type. From the first $5$ boxes, we can only choose between $1$ and $k$ items and from the last box, between $1$ and $M$ items. Hence for the first $5$ boxes, we have the expression $\left(x + x^{2} + \ldots + x^{k}\right)$, which indicates that from each of the first $5$ boxes, we can choose $1$ or $2$ or $3$ ... or $k$ items and from the last box, $\left(x + x^{2}+ \ldots + x^{M}\right)$, indicating the choice of $1$ or $2$ or $3$ ... or $M$ items. By multiplying these terms, and since exponents of $x$ get added, determining the coefficient of $x^{N}$ yields the answer.

Getting to answer is bit trickier than using basic combinatorical methods.

The amount of solutions can be chosen as many different ways as coefficient of term $x^N$ in polynomial

$(x+x^2+...+x^k)...(x+x^2+...+x^k)(x+x^2+...+x^M)=(x+x^2+...+x^k)^5(x+x^2+...+x^M)$

By using $1+x+...+x^{k-1}=(1-x^{k})(1-x)^{-1}$
equation can be written as
$=x^5(1-x^{k})^5(1-x)^{-5}x(1-x^{M})(1-x)^{-1}$
$=x^6(1-x^{k})^5(1-x^{M})(1-x)^{-6}$

Now using binomial theorem and identity $(1-x)^{-k} = \sum_{n=0}^\infty \binom{n+k-1}{k-1}x^n$, the coefficient of $x^N$ can be solved from following formula.

$$x^6(1-x^{k})^5(1-x^{M})(1-x)^{-6}=x^6\left(\sum_{n=0}^5\binom{5}{n} (-x^k)^n\right)\left(1-\binom{1}{1}x^N\right) \sum_{n=0}^\infty \binom{n+5}{5}x^n$$