0
$\begingroup$

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$

$\endgroup$
  • 2
    $\begingroup$ 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$? $\endgroup$ – William Swartworth Aug 1 '18 at 17:19
  • $\begingroup$ ${102\choose 2}\frac {2}{3}$ $\endgroup$ – Doug M Aug 1 '18 at 17:25
  • $\begingroup$ can u explain @DougM $\endgroup$ – R K Aug 1 '18 at 17:26
  • $\begingroup$ @WilliamSwartworth is it close to $\dfrac{\dbinom{200+1}{1}}{2 \times 3}$ $\endgroup$ – R K Aug 1 '18 at 17:30
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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}\,.$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.