Number of non-negative whole number solutions if the coefficients of the variables are not equal to $1$

Question

We know how to find the number of non-negative whole number solutions of the equation $x_1+x_2+x_3+...x_r=n$.It is given by $\binom{n+r-1}{r}$ by the method of stars and bars.

But how to find the number of non-negative whole number solutions if the coefficients of the variables are not equal to $1$ for all.

For example I take an equation like $2x_1+3x_2+5x_3=100$.How to find number of whole number solutions in this case?

Is there any combinatorial way?Is there there any way to use binomial theorem/generating functions to solve this problem?

Answer 1

A generating function approach will work.

The example first then generalize it.

$2x_1+3x_2+5x_3=100$

Let $$A(z) = 1 + z^2 + z^4 + \dots + z^{2k} + \dots = \frac1{1 - z^2}$$ $$B(z) = 1 + z^3 + z^6 + \dots + z^{3k} + \dots = \frac1{1 - z^3}$$ $$C(z) = 1 + z^5 + z^{10} + \dots + z^{5k} + \dots = \frac1{1 - z^5}$$

$$F(z) = A(z)B(z)C(z) = \sum_{k=0}^{\infty} c_k z^k$$

$c_n$ equals the number of ways the three terms can add up to $n$.

Note all the poles of $F(z)$ are roots of unity.

We can choose an integration contour inside of these roots.

Using the residue theorem:

$$c_n = \frac1{2\pi i} \oint \frac{F(z)}{z^{n+1}} dz$$

Where the contour is around $z = 0$ and inside $|z| = 1$

$n = 100$ is too large for octave. Some math package capable of large floating point numbers would be required.

But $n = 10$ can be demonstrated.

octave code:

function r = F(z)   r = (1 - z.^2).*(1-z.^3).*(1-z.^5);   r = 1./r; end

 [q err] = quadgk (@(z)F(z)./z.^11, (1+1i)/4, (1+1i)/4,
 "WayPoints",[(-1+1i)/4,(-1-1i)/4,(1-1i)/4]) q/(2*pi*i)

 ans = 4.0000e+000 + 1.4765e-011i

Manually checking for $n = 10$

 2.5
 2.2 + 3.2
 2.1 + 3.1 + 5.1
 5.2

There are $4$ answers.

---

Addendum

In Maxima

taylor(1/((1-z^2)*(1-z^3)*(1-z^5)),z,0,100);

$$184\,z^{100}+180\,z^{99}+177\,z^{98}+173\,z^{97}+170\,z^{96}+167\,z ^{95}+163\,z^{94}+160\,z^{93}+157\,z^{92}+153\,z^{91}+151\,z^{90}+ 147\,z^{89}+144\,z^{88}+141\,z^{87}+138\,z^{86}+135\,z^{85}+132\,z^{ 84}+129\,z^{83}+126\,z^{82}+123\,z^{81}+121\,z^{80}+117\,z^{79}+115 \,z^{78}+112\,z^{77}+109\,z^{76}+107\,z^{75}+104\,z^{74}+101\,z^{73} +99\,z^{72}+96\,z^{71}+94\,z^{70}+91\,z^{69}+89\,z^{68}+86\,z^{67}+ 84\,z^{66}+82\,z^{65}+79\,z^{64}+77\,z^{63}+75\,z^{62}+72\,z^{61}+71 \,z^{60}+68\,z^{59}+66\,z^{58}+64\,z^{57}+62\,z^{56}+60\,z^{55}+58\, z^{54}+56\,z^{53}+54\,z^{52}+52\,z^{51}+51\,z^{50}+48\,z^{49}+47\,z ^{48}+45\,z^{47}+43\,z^{46}+42\,z^{45}+40\,z^{44}+38\,z^{43}+37\,z^{ 42}+35\,z^{41}+34\,z^{40}+32\,z^{39}+31\,z^{38}+29\,z^{37}+28\,z^{36 }+27\,z^{35}+25\,z^{34}+24\,z^{33}+23\,z^{32}+21\,z^{31}+21\,z^{30}+ 19\,z^{29}+18\,z^{28}+17\,z^{27}+16\,z^{26}+15\,z^{25}+14\,z^{24}+13 \,z^{23}+12\,z^{22}+11\,z^{21}+11\,z^{20}+9\,z^{19}+9\,z^{18}+8\,z^{ 17}+7\,z^{16}+7\,z^{15}+6\,z^{14}+5\,z^{13}+5\,z^{12}+4\,z^{11}+4\,z ^{10}+3\,z^9+3\,z^8+2\,z^7+2\,z^6+2\,z^5+z^4+z^3+z^2+1+\cdots $$

I don't know exactly how maxima does the Taylor series expansion but it is fast?

It arrives at $184$ ways to get a sum of $100$.

---

Addendum 2

Alternatively expand the denominator and divide $1$:

$$1 - z^2 -z^3 +z^7 +z^8 -z^{10} \, \, \overline{)1 \qquad \qquad \qquad \qquad }$$

Then find the cofficient of $c_{100} z^{100}$

---

Generalization

$$\sum_{k = 1}^{r} a_k x_k = n$$

Let

$$F(z) = \prod_{k=1}^{r}\frac1{1 - z^{a_k}}$$

$$c_n = \frac1{2\pi i} \oint \frac{F(z)}{z^{n+1}} dz$$

Where the integration contour is inside the roots of unity.

$c_n$ is the number of ways the terms can sum to $n$.

Or find the Taylor series expansion of $F(z)$ and the $c_n$ coefficient.

Answer 2

As pointed out in this solution, the generating function for the number $f(n)$ of solutions to $2x_1+3x_2+5x_3=n$ is $$ \frac{1}{(1-x^2)(1-x^3)(1-x^5)}.$$

The denominator expands to $$1-x^2-x^3+x^7+x^8-x^{10},$$ which means that $f(n)$ satisfies the recurrence $$f(n)=f(n-2)+f(n-3)-f(n-7)-f(n-8)+f(n-10).$$ With the initial conditions $f(0)=1$ and $f(n)=0$ for $n<0$, and a little patience, you can now work out $f(n)$ for $n\le100$ by hand if you want, and find $f(100)=184.$