0
$\begingroup$

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?

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

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.

$\endgroup$
1
$\begingroup$

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$$

$\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.