Mixing
Find no. of non negative integer solutions of $a+2b+3c = 200$
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
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
$dfracdbinom200+222 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$
combinatorics
asked Aug 1 at 17:02
R K
9721039
add a comment |Â
up vote
0
down vote
favorite
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
$dfracdbinom200+222 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$
combinatorics
asked Aug 1 at 17:02
R K
9721039
2
Note that for any $b,c$ with $2b+3cleq 200$ we have a unique value of $a$ that makes the equation true. Can you count the non-negative solutions to $2b+3cleq 200$?
– William Swartworth
Aug 1 at 17:19
$102choose 2frac 23$
– Doug M
Aug 1 at 17:25
can u explain @DougM
– R K
Aug 1 at 17:26
@WilliamSwartworth is it close to $dfracdbinom200+112 times 3$
– R K
Aug 1 at 17:30
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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
$dfracdbinom200+222 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$
combinatorics
asked Aug 1 at 17:02
R K
9721039
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
$dfracdbinom200+222 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$
combinatorics
asked Aug 1 at 17:02
R K
9721039
edited Aug 1 at 17:25
asked Aug 1 at 17:02
R K
9721039
asked Aug 1 at 17:02
R K
9721039
asked Aug 1 at 17:02
R K
9721039
9721039
2
Note that for any $b,c$ with $2b+3cleq 200$ we have a unique value of $a$ that makes the equation true. Can you count the non-negative solutions to $2b+3cleq 200$?
– William Swartworth
Aug 1 at 17:19
$102choose 2frac 23$
– Doug M
Aug 1 at 17:25
can u explain @DougM
– R K
Aug 1 at 17:26
@WilliamSwartworth is it close to $dfracdbinom200+112 times 3$
– R K
Aug 1 at 17:30
add a comment |Â
2
Note that for any $b,c$ with $2b+3cleq 200$ we have a unique value of $a$ that makes the equation true. Can you count the non-negative solutions to $2b+3cleq 200$?
– William Swartworth
Aug 1 at 17:19
$102choose 2frac 23$
– Doug M
Aug 1 at 17:25
can u explain @DougM
– R K
Aug 1 at 17:26
@WilliamSwartworth is it close to $dfracdbinom200+112 times 3$
– R K
Aug 1 at 17:30
2
2
Note that for any $b,c$ with $2b+3cleq 200$ we have a unique value of $a$ that makes the equation true. Can you count the non-negative solutions to $2b+3cleq 200$?
– William Swartworth
Aug 1 at 17:19
Note that for any $b,c$ with $2b+3cleq 200$ we have a unique value of $a$ that makes the equation true. Can you count the non-negative solutions to $2b+3cleq 200$?
– William Swartworth
Aug 1 at 17:19
$102choose 2frac 23$
– Doug M
Aug 1 at 17:25
$102choose 2frac 23$
– Doug M
Aug 1 at 17:25
can u explain @DougM
– R K
Aug 1 at 17:26
can u explain @DougM
– R K
Aug 1 at 17:26
@WilliamSwartworth is it close to $dfracdbinom200+112 times 3$
– R K
Aug 1 at 17:30
@WilliamSwartworth is it close to $dfracdbinom200+112 times 3$
– R K
Aug 1 at 17:30
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
1
down vote
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,..., leftlfloor fracn2 rightrfloor$. So there are $leftlfloor fracn2 rightrfloor + 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.
answered Aug 1 at 17:19
paw88789
28.1k12247
add a comment |Â
up vote
1
down vote
Using generating functions, this would be the coefficient of $x^200$ in
$$f(x) = frac11-x cdot frac11-x^2 cdot frac11-x^3 = frac1(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) = frac2+x9(1+x+x^2) + frac18(1+x) + frac1772(1-x) + frac14(1-x)^2 + frac16(1-x)^3 = \
frac2-x-x^29(1-x^3) + frac18(1+x) + frac1772(1-x) + frac14(1-x)^2 + frac16(1-x)^3.$$
Therefore, the coefficient of $x^200$ would be
$$-frac19 + frac18 + frac1772 + frac14 binom2011 + frac16 binom2022 = 3434.$$
answered Aug 1 at 17:40
Daniel Schepler
6,6381513
add a comment |Â
up vote
1
down vote
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 $binomn+22$ 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-2leftlfloor fracn2 rightrfloor quad quad y,z=leftlfloor fracn2 rightrfloor$$
It is clear that there are $leftlfloor fracn2 rightrfloor +1$ cases. And we would have counted each one three times in our $binomn+22$ 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 $binomn+22$ from before to get that there are $$binomn+22-3left(leftlfloor fracn2 rightrfloor+1right)$$
solutions for $x,y,z$ without $x leq y leq z$ and thus
$$fracbinomn+22-3left(leftlfloor fracn2 rightrfloor+1right)6$$
solutions with $x leq y leq z$
Now we can finally add our cases up to get
$$fracbinomn+22-3left(leftlfloor fracn2 rightrfloor+1right)6+left(leftlfloor fracn2 rightrfloor+1right)$$
$$fracbinomn+22+3left(leftlfloor fracn2 rightrfloor+1right)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
$$fracbinomn+22-3leftlfloor fracn2 rightrfloor - 16 + leftlfloor fracn2 rightrfloor + 1$$ or
$$fracbinomn+22+3leftlfloor fracn2 rightrfloor +56$$
Also, it's fun to notice that this is the closest integer to $$frac(n+3)^212$$
answered Aug 1 at 17:34
Isaac Browne
3,7112928
add a comment |Â
up vote
0
down vote
Consider $x:=a+b+c$, $y:=b+c$, and $z:=c$. Let $n:=200$. Then, $xgeq ygeq zgeq 0$ and $x+y+z=n$. Let $$T_n:=big(x,y,z)inmathbbZ_geq 0^3,,.$$ 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 $xgeq ygeq z$.
By Burnside's Lemma,
$$N_n=frac1S_3,sum_gin S_3,big|textFix(g)big|,,$$
where $textFix(g)$ denotes the number of triples $(x,y,z)in T_n$ fixed by $g$. The class equation of $S_3$ is $$#textidentity+#texttranspositions+#text$3$-cycles=1+3+2,.$$
That is,
$$N_n=frac16,Biggl(1cdot binomn+3-13-1+3cdotleftlfloor fracn+22rightrfloor+2cdot leftlfloorfrac3-(ntext mod 3)3rightrfloorBiggr),,$$
so
$$N_n=frac16,binomn+22+frac12,Biggl(1+leftlfloorfracn2rightrfloorBiggr)+frac13,leftlfloorfrac3-(ntext mod 3)3rightrfloor,.$$
In particular,
$$N_200=frac16,binom2022+frac12,(1+100)+frac13,(0)=3434,.$$
From Daniel Schepler's solution, the generating function $f(t):=sumlimits_n=0^infty,N_n,t^n$ is given by $f(t)=dfrac1(1-t),(1-t^2),(1-t^3)$. This answer gives a slightly more aesthetic expression for $f$:
$$f(t)=frac(1-t)^-36+frac(1+t),left(1-t^2right)^-22+fracleft(1-t^3right)^-13,.$$
answered Aug 1 at 17:43
Batominovski
22.7k22776
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
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,..., leftlfloor fracn2 rightrfloor$. So there are $leftlfloor fracn2 rightrfloor + 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.
answered Aug 1 at 17:19
paw88789
28.1k12247
add a comment |Â
up vote
1
down vote
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,..., leftlfloor fracn2 rightrfloor$. So there are $leftlfloor fracn2 rightrfloor + 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.
answered Aug 1 at 17:19
paw88789
28.1k12247
add a comment |Â
up vote
1
down vote
up vote
1
down vote
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,..., leftlfloor fracn2 rightrfloor$. So there are $leftlfloor fracn2 rightrfloor + 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.
answered Aug 1 at 17:19
paw88789
28.1k12247
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,..., leftlfloor fracn2 rightrfloor$. So there are $leftlfloor fracn2 rightrfloor + 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.
answered Aug 1 at 17:19
paw88789
28.1k12247
answered Aug 1 at 17:19
paw88789
28.1k12247
answered Aug 1 at 17:19
paw88789
28.1k12247
answered Aug 1 at 17:19
paw88789
28.1k12247
28.1k12247
add a comment |Â
add a comment |Â
up vote
1
down vote
Using generating functions, this would be the coefficient of $x^200$ in
$$f(x) = frac11-x cdot frac11-x^2 cdot frac11-x^3 = frac1(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) = frac2+x9(1+x+x^2) + frac18(1+x) + frac1772(1-x) + frac14(1-x)^2 + frac16(1-x)^3 = \
frac2-x-x^29(1-x^3) + frac18(1+x) + frac1772(1-x) + frac14(1-x)^2 + frac16(1-x)^3.$$
Therefore, the coefficient of $x^200$ would be
$$-frac19 + frac18 + frac1772 + frac14 binom2011 + frac16 binom2022 = 3434.$$
answered Aug 1 at 17:40
Daniel Schepler
6,6381513
add a comment |Â
up vote
1
down vote
Using generating functions, this would be the coefficient of $x^200$ in
$$f(x) = frac11-x cdot frac11-x^2 cdot frac11-x^3 = frac1(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) = frac2+x9(1+x+x^2) + frac18(1+x) + frac1772(1-x) + frac14(1-x)^2 + frac16(1-x)^3 = \
frac2-x-x^29(1-x^3) + frac18(1+x) + frac1772(1-x) + frac14(1-x)^2 + frac16(1-x)^3.$$
Therefore, the coefficient of $x^200$ would be
$$-frac19 + frac18 + frac1772 + frac14 binom2011 + frac16 binom2022 = 3434.$$
answered Aug 1 at 17:40
Daniel Schepler
6,6381513
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Using generating functions, this would be the coefficient of $x^200$ in
$$f(x) = frac11-x cdot frac11-x^2 cdot frac11-x^3 = frac1(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) = frac2+x9(1+x+x^2) + frac18(1+x) + frac1772(1-x) + frac14(1-x)^2 + frac16(1-x)^3 = \
frac2-x-x^29(1-x^3) + frac18(1+x) + frac1772(1-x) + frac14(1-x)^2 + frac16(1-x)^3.$$
Therefore, the coefficient of $x^200$ would be
$$-frac19 + frac18 + frac1772 + frac14 binom2011 + frac16 binom2022 = 3434.$$
answered Aug 1 at 17:40
Daniel Schepler
6,6381513
Using generating functions, this would be the coefficient of $x^200$ in
$$f(x) = frac11-x cdot frac11-x^2 cdot frac11-x^3 = frac1(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) = frac2+x9(1+x+x^2) + frac18(1+x) + frac1772(1-x) + frac14(1-x)^2 + frac16(1-x)^3 = \
frac2-x-x^29(1-x^3) + frac18(1+x) + frac1772(1-x) + frac14(1-x)^2 + frac16(1-x)^3.$$
Therefore, the coefficient of $x^200$ would be
$$-frac19 + frac18 + frac1772 + frac14 binom2011 + frac16 binom2022 = 3434.$$
answered Aug 1 at 17:40
Daniel Schepler
6,6381513
answered Aug 1 at 17:40
Daniel Schepler
6,6381513
answered Aug 1 at 17:40
Daniel Schepler
6,6381513
answered Aug 1 at 17:40
Daniel Schepler
6,6381513
6,6381513
add a comment |Â
add a comment |Â
up vote
1
down vote
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 $binomn+22$ 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-2leftlfloor fracn2 rightrfloor quad quad y,z=leftlfloor fracn2 rightrfloor$$
It is clear that there are $leftlfloor fracn2 rightrfloor +1$ cases. And we would have counted each one three times in our $binomn+22$ 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 $binomn+22$ from before to get that there are $$binomn+22-3left(leftlfloor fracn2 rightrfloor+1right)$$
solutions for $x,y,z$ without $x leq y leq z$ and thus
$$fracbinomn+22-3left(leftlfloor fracn2 rightrfloor+1right)6$$
solutions with $x leq y leq z$
Now we can finally add our cases up to get
$$fracbinomn+22-3left(leftlfloor fracn2 rightrfloor+1right)6+left(leftlfloor fracn2 rightrfloor+1right)$$
$$fracbinomn+22+3left(leftlfloor fracn2 rightrfloor+1right)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
$$fracbinomn+22-3leftlfloor fracn2 rightrfloor - 16 + leftlfloor fracn2 rightrfloor + 1$$ or
$$fracbinomn+22+3leftlfloor fracn2 rightrfloor +56$$
Also, it's fun to notice that this is the closest integer to $$frac(n+3)^212$$
answered Aug 1 at 17:34
Isaac Browne
3,7112928
add a comment |Â
up vote
1
down vote
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 $binomn+22$ 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-2leftlfloor fracn2 rightrfloor quad quad y,z=leftlfloor fracn2 rightrfloor$$
It is clear that there are $leftlfloor fracn2 rightrfloor +1$ cases. And we would have counted each one three times in our $binomn+22$ 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 $binomn+22$ from before to get that there are $$binomn+22-3left(leftlfloor fracn2 rightrfloor+1right)$$
solutions for $x,y,z$ without $x leq y leq z$ and thus
$$fracbinomn+22-3left(leftlfloor fracn2 rightrfloor+1right)6$$
solutions with $x leq y leq z$
Now we can finally add our cases up to get
$$fracbinomn+22-3left(leftlfloor fracn2 rightrfloor+1right)6+left(leftlfloor fracn2 rightrfloor+1right)$$
$$fracbinomn+22+3left(leftlfloor fracn2 rightrfloor+1right)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
$$fracbinomn+22-3leftlfloor fracn2 rightrfloor - 16 + leftlfloor fracn2 rightrfloor + 1$$ or
$$fracbinomn+22+3leftlfloor fracn2 rightrfloor +56$$
Also, it's fun to notice that this is the closest integer to $$frac(n+3)^212$$
answered Aug 1 at 17:34
Isaac Browne
3,7112928
add a comment |Â
up vote
1
down vote
up vote
1
down vote
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 $binomn+22$ 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-2leftlfloor fracn2 rightrfloor quad quad y,z=leftlfloor fracn2 rightrfloor$$
It is clear that there are $leftlfloor fracn2 rightrfloor +1$ cases. And we would have counted each one three times in our $binomn+22$ 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 $binomn+22$ from before to get that there are $$binomn+22-3left(leftlfloor fracn2 rightrfloor+1right)$$
solutions for $x,y,z$ without $x leq y leq z$ and thus
$$fracbinomn+22-3left(leftlfloor fracn2 rightrfloor+1right)6$$
solutions with $x leq y leq z$
Now we can finally add our cases up to get
$$fracbinomn+22-3left(leftlfloor fracn2 rightrfloor+1right)6+left(leftlfloor fracn2 rightrfloor+1right)$$
$$fracbinomn+22+3left(leftlfloor fracn2 rightrfloor+1right)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
$$fracbinomn+22-3leftlfloor fracn2 rightrfloor - 16 + leftlfloor fracn2 rightrfloor + 1$$ or
$$fracbinomn+22+3leftlfloor fracn2 rightrfloor +56$$
Also, it's fun to notice that this is the closest integer to $$frac(n+3)^212$$
answered Aug 1 at 17:34
Isaac Browne
3,7112928
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 $binomn+22$ 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-2leftlfloor fracn2 rightrfloor quad quad y,z=leftlfloor fracn2 rightrfloor$$
It is clear that there are $leftlfloor fracn2 rightrfloor +1$ cases. And we would have counted each one three times in our $binomn+22$ 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 $binomn+22$ from before to get that there are $$binomn+22-3left(leftlfloor fracn2 rightrfloor+1right)$$
solutions for $x,y,z$ without $x leq y leq z$ and thus
$$fracbinomn+22-3left(leftlfloor fracn2 rightrfloor+1right)6$$
solutions with $x leq y leq z$
Now we can finally add our cases up to get
$$fracbinomn+22-3left(leftlfloor fracn2 rightrfloor+1right)6+left(leftlfloor fracn2 rightrfloor+1right)$$
$$fracbinomn+22+3left(leftlfloor fracn2 rightrfloor+1right)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
$$fracbinomn+22-3leftlfloor fracn2 rightrfloor - 16 + leftlfloor fracn2 rightrfloor + 1$$ or
$$fracbinomn+22+3leftlfloor fracn2 rightrfloor +56$$
Also, it's fun to notice that this is the closest integer to $$frac(n+3)^212$$
answered Aug 1 at 17:34
Isaac Browne
3,7112928
edited Aug 1 at 17:53
answered Aug 1 at 17:34
Isaac Browne
3,7112928
answered Aug 1 at 17:34
Isaac Browne
3,7112928
answered Aug 1 at 17:34
Isaac Browne
3,7112928
3,7112928
add a comment |Â
add a comment |Â
up vote
0
down vote
Consider $x:=a+b+c$, $y:=b+c$, and $z:=c$. Let $n:=200$. Then, $xgeq ygeq zgeq 0$ and $x+y+z=n$. Let $$T_n:=big(x,y,z)inmathbbZ_geq 0^3,,.$$ 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 $xgeq ygeq z$.
By Burnside's Lemma,
$$N_n=frac1S_3,sum_gin S_3,big|textFix(g)big|,,$$
where $textFix(g)$ denotes the number of triples $(x,y,z)in T_n$ fixed by $g$. The class equation of $S_3$ is $$#textidentity+#texttranspositions+#text$3$-cycles=1+3+2,.$$
That is,
$$N_n=frac16,Biggl(1cdot binomn+3-13-1+3cdotleftlfloor fracn+22rightrfloor+2cdot leftlfloorfrac3-(ntext mod 3)3rightrfloorBiggr),,$$
so
$$N_n=frac16,binomn+22+frac12,Biggl(1+leftlfloorfracn2rightrfloorBiggr)+frac13,leftlfloorfrac3-(ntext mod 3)3rightrfloor,.$$
In particular,
$$N_200=frac16,binom2022+frac12,(1+100)+frac13,(0)=3434,.$$
From Daniel Schepler's solution, the generating function $f(t):=sumlimits_n=0^infty,N_n,t^n$ is given by $f(t)=dfrac1(1-t),(1-t^2),(1-t^3)$. This answer gives a slightly more aesthetic expression for $f$:
$$f(t)=frac(1-t)^-36+frac(1+t),left(1-t^2right)^-22+fracleft(1-t^3right)^-13,.$$
answered Aug 1 at 17:43
Batominovski
22.7k22776
add a comment |Â
up vote
0
down vote
Consider $x:=a+b+c$, $y:=b+c$, and $z:=c$. Let $n:=200$. Then, $xgeq ygeq zgeq 0$ and $x+y+z=n$. Let $$T_n:=big(x,y,z)inmathbbZ_geq 0^3,,.$$ 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 $xgeq ygeq z$.
By Burnside's Lemma,
$$N_n=frac1S_3,sum_gin S_3,big|textFix(g)big|,,$$
where $textFix(g)$ denotes the number of triples $(x,y,z)in T_n$ fixed by $g$. The class equation of $S_3$ is $$#textidentity+#texttranspositions+#text$3$-cycles=1+3+2,.$$
That is,
$$N_n=frac16,Biggl(1cdot binomn+3-13-1+3cdotleftlfloor fracn+22rightrfloor+2cdot leftlfloorfrac3-(ntext mod 3)3rightrfloorBiggr),,$$
so
$$N_n=frac16,binomn+22+frac12,Biggl(1+leftlfloorfracn2rightrfloorBiggr)+frac13,leftlfloorfrac3-(ntext mod 3)3rightrfloor,.$$
In particular,
$$N_200=frac16,binom2022+frac12,(1+100)+frac13,(0)=3434,.$$
From Daniel Schepler's solution, the generating function $f(t):=sumlimits_n=0^infty,N_n,t^n$ is given by $f(t)=dfrac1(1-t),(1-t^2),(1-t^3)$. This answer gives a slightly more aesthetic expression for $f$:
$$f(t)=frac(1-t)^-36+frac(1+t),left(1-t^2right)^-22+fracleft(1-t^3right)^-13,.$$
answered Aug 1 at 17:43
Batominovski
22.7k22776
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Consider $x:=a+b+c$, $y:=b+c$, and $z:=c$. Let $n:=200$. Then, $xgeq ygeq zgeq 0$ and $x+y+z=n$. Let $$T_n:=big(x,y,z)inmathbbZ_geq 0^3,,.$$ 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 $xgeq ygeq z$.
By Burnside's Lemma,
$$N_n=frac1S_3,sum_gin S_3,big|textFix(g)big|,,$$
where $textFix(g)$ denotes the number of triples $(x,y,z)in T_n$ fixed by $g$. The class equation of $S_3$ is $$#textidentity+#texttranspositions+#text$3$-cycles=1+3+2,.$$
That is,
$$N_n=frac16,Biggl(1cdot binomn+3-13-1+3cdotleftlfloor fracn+22rightrfloor+2cdot leftlfloorfrac3-(ntext mod 3)3rightrfloorBiggr),,$$
so
$$N_n=frac16,binomn+22+frac12,Biggl(1+leftlfloorfracn2rightrfloorBiggr)+frac13,leftlfloorfrac3-(ntext mod 3)3rightrfloor,.$$
In particular,
$$N_200=frac16,binom2022+frac12,(1+100)+frac13,(0)=3434,.$$
From Daniel Schepler's solution, the generating function $f(t):=sumlimits_n=0^infty,N_n,t^n$ is given by $f(t)=dfrac1(1-t),(1-t^2),(1-t^3)$. This answer gives a slightly more aesthetic expression for $f$:
$$f(t)=frac(1-t)^-36+frac(1+t),left(1-t^2right)^-22+fracleft(1-t^3right)^-13,.$$
answered Aug 1 at 17:43
Batominovski
22.7k22776
Consider $x:=a+b+c$, $y:=b+c$, and $z:=c$. Let $n:=200$. Then, $xgeq ygeq zgeq 0$ and $x+y+z=n$. Let $$T_n:=big(x,y,z)inmathbbZ_geq 0^3,,.$$ 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 $xgeq ygeq z$.
By Burnside's Lemma,
$$N_n=frac1S_3,sum_gin S_3,big|textFix(g)big|,,$$
where $textFix(g)$ denotes the number of triples $(x,y,z)in T_n$ fixed by $g$. The class equation of $S_3$ is $$#textidentity+#texttranspositions+#text$3$-cycles=1+3+2,.$$
That is,
$$N_n=frac16,Biggl(1cdot binomn+3-13-1+3cdotleftlfloor fracn+22rightrfloor+2cdot leftlfloorfrac3-(ntext mod 3)3rightrfloorBiggr),,$$
so
$$N_n=frac16,binomn+22+frac12,Biggl(1+leftlfloorfracn2rightrfloorBiggr)+frac13,leftlfloorfrac3-(ntext mod 3)3rightrfloor,.$$
In particular,
$$N_200=frac16,binom2022+frac12,(1+100)+frac13,(0)=3434,.$$
From Daniel Schepler's solution, the generating function $f(t):=sumlimits_n=0^infty,N_n,t^n$ is given by $f(t)=dfrac1(1-t),(1-t^2),(1-t^3)$. This answer gives a slightly more aesthetic expression for $f$:
$$f(t)=frac(1-t)^-36+frac(1+t),left(1-t^2right)^-22+fracleft(1-t^3right)^-13,.$$
answered Aug 1 at 17:43
Batominovski
22.7k22776
edited Aug 1 at 20:02
answered Aug 1 at 17:43
Batominovski
22.7k22776
answered Aug 1 at 17:43
Batominovski
22.7k22776
answered Aug 1 at 17:43
Batominovski
22.7k22776
22.7k22776
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2869279%2ffind-no-of-non-negative-integer-solutions-of-a2b3c-200%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
Note that for any $b,c$ with $2b+3cleq 200$ we have a unique value of $a$ that makes the equation true. Can you count the non-negative solutions to $2b+3cleq 200$?
– William Swartworth
Aug 1 at 17:19
$102choose 2frac 23$
– Doug M
Aug 1 at 17:25
can u explain @DougM
– R K
Aug 1 at 17:26
@WilliamSwartworth is it close to $dfracdbinom200+112 times 3$
– R K
Aug 1 at 17:30