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

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?

• I don't think there is a combinatorial way. Why? Well, if the greatest common divisor of the coefficients doesn't divide the LHS, then there is no solution, but you can't see that using combinatorics(the value of the gcd) – Mastrem Sep 24 '16 at 12:26
• @Mastrem Is there any way at all? – user369582 Sep 29 '16 at 4:34
• I think this question should be closed as a duplicate of math.stackexchange.com/questions/30638/… but that's not possible because of the bounty. Anyway, I encourage ZOZ and Avi and anyone else who is interested in this question to have a look at the older question and to follow the links given there. See also iaeng.org/IJAM/issues_v40/issue_1/IJAM_40_1_01.pdf and mathoverflow.net/questions/61329/… – Gerry Myerson Sep 29 '16 at 7:08
• – Gerry Myerson Sep 29 '16 at 7:14

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.

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

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.

• Fantastic, I hope such answer if complemented by linking to an explanation of why NT needs $\gcd$ to find if solution is possible or not, makes it a complete one. – jiten Dec 24 '17 at 0:48

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