How many solutions for this equation using combinatorics?

245 Views Asked by At

In combinatoric, with the equation $$x_1+x_2+x_3+x_4+\dots +x_n=k,\quad x_i \geq 0,$$ we know, that the number of solutions is: $$ \left({n\choose k}\right)={n+k-1 \choose n-1}=\frac{(n+k-1)!}{(n-1)!\cdot k!} $$

Is there a way in combinatoric to find the numbers of solution for an equations like $$a_1\cdot x_1+a_2\cdot x_2+a_3\cdot x_3 + \dots + a_n\cdot x_n=k, \quad x_i \geq 0,$$ where we know the values of $a_1,a_2,\dots, a_n$?

2

There are 2 best solutions below

2
On

The number of solutions is the coefficient of $x^k$ in the generating function

$$ \prod_{i=1}^n\frac1{1-x^{a_i}}\;. $$

3
On

I totally agree with the first answer. Here I'm just going to explain why it is corect.

If we had $x_1 +x_2 +x_3+ \cdots +x_n =k$, then the number of integer solutions to this equation, where $x_i \ge 0$,is equal to the coefficient of $x^k$ in the expansion of $$\underbrace{(1+x+x^2+ \cdots)\ldots(1+x+x^2+\cdots)}_{\text{n times}},$$

i.e., $[x^k] (1+x+x^2+ \cdots )^n$. This method works because from each one of the $n$ brackets in the product, the exponents of $x$ are added to get certain numbers and the coefficient of $x^k$ would be equal to the number of ways we can get $k$ by adding $n$ non-negative integers.

Now, for $a_1x_1 + a_2x_2 +a_3x_3 + \cdots + a_nx_n=k$, the number of integer solutions would be the coefficient of $x^k$ in the expansion of $$(1+x^{a_1}+x^{2a_1}+\ldots)(1+x^{a_2}+x^{2a_2}+\ldots)\cdots (1+x^{a_n}+x^{2a_n}+\ldots)$$ because here the numbers that you add up have to be integer multiples of $(a_1,a_2,\ldots,a_n)$.

That simplifies to $$[x^k] \left(\frac{1}{1-x^{a_1}}\right)\left(\frac{1}{1-x^{a_2}}\right)\left(\frac{1}{1-x^{a_3}}\right) \cdots \left(\frac{1}{1-x^{a_n}}\right)$$

$$=[x^k] \prod_{i=1}^n \frac{1}{1- x^{a_i}}$$