0
$\begingroup$

Let $x_1,x_2,.....,x_m$ are integers.then number of solutions to the equation $$x_1+x_2+....+x_m=n$$ subject to the conditions $a_1 \leq x_1 \leq b_1,.......,a_m \leq x_m \leq b_m$

My book just states the formula as

The number of solutions is equal to the coefficient of $x^n$ in $$(x^(a_1)+x^(a_2)+....x^(b_1))......( x^(a_m)+x^(a_m+1)+.......x^(b_m))$$.I can't understand why it should be so? Any help?Thanks.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

$$ 1 + x + x^2 + \dots + x^n = \frac{x^{n+1}-1}{x-1}$$

$$ x^{a} + x^{a+1} + \dots + x^b = x^a(1 + x + x^2 + \dots + x^{b-a}) = \frac{x^a(x^{b-a+1} -1)}{x - 1} = \frac{x^{b+1} - x^a}{x-1}$$

The range of integers $a_k$ to $b_k$ are represented in the powers of $x$ of the generating function.

Multiply all the generating functions for the ranges $x_1$ to $x_m$ together.

When multiplied the powers of each term are added to the power of other terms in different ranges.

$$F(x) = \prod_{n=1}^{m} \left( \frac{x^{b_n + 1} - x^{a_n}}{x-1} \right) = \prod_{n=1}^{m} \left( x^{a_n} + x^{a_n + 1} \dots + x^{b_n} \right) = \sum_{k}c_k x^k$$

$c_n$ is the number of ways that the sum (power of $x^n$) can add up to $n$.

i.e. the powers add up to the sum $n$ and the coefficient $c_n$ is the count of how many ways that sum can be made.

Try a very small example by hand e.g. a pair of dice.

Each dice has a range of six numbers $1$ to $6$ so how many ways can $7$ be made.

$$F(x) = (x^1 + x^2 + \dots + x^6)(x^1 + x^2 + \dots + x^6) $$

The left () is one dice the right () is the other. Multiply them to find the combinations.

$$ F(x)= x^{12}+2\,x^{11}+3\,x^{10}+4\,x^9+5\,x^8+6\,x^7+5\,x^6+4\,x^5+3\,x^ 4+2\,x^3+x^2$$

There are $6$ ways to roll $7$ : $(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)$.

Note there is no way to roll $1$ with a pair of dice.

$\endgroup$
4
  • $\begingroup$ @ arthur I can't understand when you said "$c_n$ is the number of ways that the sum (power of ) can add up to $n$".please can you be a little more explanative.thanks $\endgroup$
    – Navin
    Oct 10, 2016 at 15:09
  • $\begingroup$ navinstudent - in the dice example the addition of dice faces is being done in the powers of $x$ when the terms are multiplied. The number of ways this can happen is in the coefficient $c_n$. $$-$$ Take the events (dice1 $=3$ and dice2 $= 4$) and (dice1 $=2$ and dice2 $= 5$) these events are represented as $x^3.x^4 + x^2.x^5 = 2x^7$ both add up to $7$ thus $x^7$, the sum of $7$ occured in $2$ ways. $$-$$ Multiplying $(x^1 + x^2 + \dots + x^6)(x^1 + x^2 + \dots + x^6)$ generates all the sums $x^{sum}$ and counts the number of ways each sum can happen $count_{sum} x^{sum}$ $\endgroup$
    – user186104
    Oct 10, 2016 at 16:32
  • $\begingroup$ navinstudent - The sum $x_1+x_2+....+x_m$ is occuring in the power of $x$ i.e. $x^{sum}$ or $x^n$. The number of ways if happens is $c_n$ in $c_n x^n$ $\endgroup$
    – user186104
    Oct 10, 2016 at 16:40
  • $\begingroup$ thanks for your explanation.especially for your example of dice. $\endgroup$
    – Navin
    Oct 10, 2016 at 18:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .