# Find no. of non negative integer solutions of $a+2b+3c = 200$

I want to find number of the non negative integer solutions of $a+2b+3c = 200$ (answer can contain $a,b,c = 0$)

Example one of the solutions is $a = 100, b = 50, c = 0$

I used stars and bars trick and here i get is

$\dfrac{\dbinom{200+2}{2}}{2 \times 3}$ but it is incorrect

any type of math is welcomed

what I have learnt from stars and bars technique is to find the solutions of $x+y = n , x,y,n > 0$ are positive integers but I am confused with equation of type $ax+by = n$ where $a , b> 1$

• Note that for any $b,c$ with $2b+3c\leq 200$ we have a unique value of $a$ that makes the equation true. Can you count the non-negative solutions to $2b+3c\leq 200$? – William Swartworth Aug 1 '18 at 17:19
• ${102\choose 2}\frac {2}{3}$ – Doug M Aug 1 '18 at 17:25
• can u explain @DougM – R K Aug 1 '18 at 17:26
• @WilliamSwartworth is it close to $\dfrac{\dbinom{200+1}{1}}{2 \times 3}$ – R K Aug 1 '18 at 17:30

Using generating functions, this would be the coefficient of $x^{200}$ in $$f(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^3} = \frac{1}{(1-x)^3 (1+x) (1+x+x^2)}.$$ Now, according to Maxima, if you calculate a partial fractions expansion of $f(x)$ you should get: $$f(x) = \frac{2+x}{9(1+x+x^2)} + \frac{1}{8(1+x)} + \frac{17}{72(1-x)} + \frac{1}{4(1-x)^2} + \frac{1}{6(1-x)^3} = \\ \frac{2-x-x^2}{9(1-x^3)} + \frac{1}{8(1+x)} + \frac{17}{72(1-x)} + \frac{1}{4(1-x)^2} + \frac{1}{6(1-x)^3}.$$ Therefore, the coefficient of $x^{200}$ would be $$-\frac{1}{9} + \frac{1}{8} + \frac{17}{72} + \frac{1}{4} \binom{201}{1} + \frac{1}{6} \binom{202}{2} = 3434.$$

You can't use stars and bars since $2b$ and $3c$ cannot be any integer. However, a nice way to do this generally for $a+2b+3c=n$ is to make the substitution $x=c$, $y=b+c$ and $z=a+b+c$ so we have $x \leq y \leq z$. Then it comes down to some casework for when all three are different, two are the same, and all three are the same.

The total amount of cases without $x \leq y \leq z$ would be $\binom{n+2}{2}$ by stars and bars, and this will help us in that we only need to consider two of the cases, then solve for the last.

Case 1: All three are the same. For $n=200$, there will not be a case when all three are the same since $3$ does not divide $200$.

Case 2: Two numbers are the same. After beginning to list out the possibilities $$x=n \quad \quad y,z=0$$ $$x=n-2 \quad \quad y,z=1$$ $$\cdots$$ $$x=n-2\left\lfloor \frac{n}{2} \right\rfloor \quad \quad y,z=\left\lfloor \frac{n}{2} \right\rfloor$$ It is clear that there are $\left\lfloor \frac{n}{2} \right\rfloor +1$ cases. And we would have counted each one three times in our $\binom{n+2}{2}$ since there we do not include the condition $x \leq y \leq z$.

Case 3: All three are different. We can now calculate these using our total $\binom{n+2}{2}$ from before to get that there are $$\binom{n+2}{2}-3\left(\left\lfloor \frac{n}{2} \right\rfloor+1\right)$$ solutions for $x,y,z$ without $x \leq y \leq z$ and thus $$\frac{\binom{n+2}{2}-3\left(\left\lfloor \frac{n}{2} \right\rfloor+1\right)}{6}$$ solutions with $x \leq y \leq z$

Now we can finally add our cases up to get $$\frac{\binom{n+2}{2}-3\left(\left\lfloor \frac{n}{2} \right\rfloor+1\right)}{6}+\left(\left\lfloor \frac{n}{2} \right\rfloor+1\right)$$ $$\frac{\binom{n+2}{2}+3\left(\left\lfloor \frac{n}{2} \right\rfloor+1\right)}{6}$$

And for $n=200$, we get the answer $3434$.

Addendum: I like to solve things generally, so here it is for numbers that are divisible by $3$. We'll have $1$ solution for our Case 1 and have to subtract off $1$ from Case 2 since there'll be a solution $x=y=z$. So, instead we'd have $$\frac{\binom{n+2}{2}-3\left\lfloor \frac{n}{2} \right\rfloor - 1}{6} + \left\lfloor \frac{n}{2} \right\rfloor + 1$$ or $$\frac{\binom{n+2}{2}+3\left\lfloor \frac{n}{2} \right\rfloor +5}{6}$$

Also, it's fun to notice that this is the closest integer to $$\frac{(n+3)^2}{12}$$

Outline:

Step 1: How many solutions are there to $a+2b=n$ where $n$ is a fixed nonnegative integer. Answer: $b$ can be any of $0, 1, 2,..., \left\lfloor \frac{n}{2} \right\rfloor$. So there are $\left\lfloor \frac{n}{2} \right\rfloor + 1$ solutions.

Step 2: $n$ (from step 1) can be anything of the form $200 - 3c$ where $c$ takes on values from $0$ to $66$. [That is the values of $n$ are $200, 197, 194, ...,2$.]

Step 3: For each value of $n$ in step 2 you will get some number of solutions (based on step 1). Add these all together. There may be helpful patterns you can exploit.

Consider $x:=a+b+c$, $y:=b+c$, and $z:=c$. Let $n:=200$. Then, $x\geq y\geq z\geq 0$ and $x+y+z=n$. Let $$T_n:=\big\{(x,y,z)\in\mathbb{Z}_{\geq 0}^3\,|\,x+y+z=n\big\}\,.$$ Then, the symmetric group $S_3$ of order $3!=6$ acts on $T_n$ by permuting the three entries of each element of $T_n$. The number of $S_3$-orbits $N_n$ in $T_n$ is precisely the number of triples $(x,y,z)\in T_n$ with $x\geq y\geq z$.

By Burnside's Lemma, $$N_n=\frac{1}{|S_3|}\,\sum_{g\in S_3}\,\big|\text{Fix}(g)\big|\,,$$ where $\text{Fix}(g)$ denotes the number of triples $(x,y,z)\in T_n$ fixed by $g$. The class equation of $S_3$ is $$\#\{\text{identity}\}+\#\{\text{transpositions}\}+\#\{\text{3-cycles}\}=1+3+2\,.$$ That is, $$N_n=\frac{1}{6}\,\Biggl(1\cdot \binom{n+3-1}{3-1}+3\cdot\left\lfloor \frac{n+2}{2}\right\rfloor+2\cdot \left\lfloor\frac{3-(n\text{ mod }3)}{3}\right\rfloor\Biggr)\,,$$ so $$N_n=\frac{1}{6}\,\binom{n+2}{2}+\frac{1}{2}\,\Biggl(1+\left\lfloor\frac{n}{2}\right\rfloor\Biggr)+\frac{1}{3}\,\left\lfloor\frac{3-(n\text{ mod }3)}{3}\right\rfloor\,.$$ In particular, $$N_{200}=\frac{1}{6}\,\binom{202}{2}+\frac{1}{2}\,(1+100)+\frac{1}{3}\,(0)=3434\,.$$

From Daniel Schepler's solution, the generating function $f(t):=\sum\limits_{n=0}^\infty\,N_n\,t^n$ is given by $f(t)=\dfrac{1}{(1-t)\,(1-t^2)\,(1-t^3)}$. This answer gives a slightly more aesthetic expression for $f$: $$f(t)=\frac{(1-t)^{-3}}{6}+\frac{(1+t)\,\left(1-t^2\right)^{-2}}{2}+\frac{\left(1-t^3\right)^{-1}}{3}\,.$$