combinatoricsproblem solving
How many different ordered triples $(a,b,c)$ of non-negative integers are there such that $a+b+c=50$?
I tried to list the possibilities but the list is way too long, I know how to find the ordered doubles $(x,y)$ such that $x+y=50$, I just have to list them like:
$(0,50)\\(1,49)\\ \vdots\\(49,1)\\(50,0)$
Which is just simply $(50-0)+1=51$. But this is too long to count. I suppose there's a better way to do this?
You need to find the number of cases with $a \lt b \lt c$, $a=b\lt c$, $a \lt b =c$ and $a=b=c$, though you can join the second and third together into a set called "two equal", and we can call the first "none equal" and the last "three equal".
"Three equal" is easy: you want solutions to $3p=9$ and $3s=9$ and there only is $1 \times 1 = 1$ "three equal" solution.
"Two equal" requires the number of solutions to $2p+r=9$ and $2s+u=9$. This is $5 \times 5 = 25$. These will each appear once either as $(2^p5^s,2^p5^s,2^r5^u)$ or as $(2^r5^u,2^p5^s,2^p5^s)$ so we do not need to adjust for duplication. But $1$ is the "three equal" solution, leaving $25-1=24$ "two equal" solutions.
"None equal" is a little harder. You have the $55\times 55$ you found. But you need to subtract three times the $24$ "two equal" solutions [e.g. if you have a solution $(a,a,c)$ then it will appear also as $(a,c,a)$ and $(c,a,a)$] and one times the "three equal" solution. Even then five-sixths of these "none equal" solutions are in the wrong order. So you want $\frac{55\times 55-3\times 24 -1 \times 1}{6}=492$ "none equal" solutions.
And then your answer is $1+24+492=517$ ordered solutions as lnwvr has found.
By way of enrichment I would like to point out that using the Polya Enumeration Theorem the closed form is also given by
$$n! [z^k] Z(P_n)\left(\frac{1}{1-z}\right)$$
where $Z(P_n) = Z(A_n)-Z(S_n)$ is the difference between the cycle index of the alternating group and the cycle index of the symmetric group. This cycle index is known in species theory as the set operator $\mathfrak{P}_{=n}$ and the species equation here is
$$\mathfrak{P}_{=n}\left(\mathcal{E} + \mathcal{Z} + \mathcal{Z}^2 + \mathcal{Z^3} + \cdots\right).$$
Recall the recurrence by Lovasz for the cycle index $Z(P_n)$ of the set operator $\mathfrak{P}_{=n}$ on $n$ slots, which is $$Z(P_n) = \frac{1}{n} \sum_{l=1}^n (-1)^{l-1} a_l Z(P_{n-l}) \quad\text{where}\quad Z(P_0) = 1.$$ This recurrence lets us calculate the cycle index $Z(P_n)$ very easily.
For example when $n=3$ as in the introduction to the problem the cycle index is $$Z(P_3) = 1/6\,{a_{{1}}}^{3}-1/2\,a_{{2}}a_{{1}}+1/3\,a_{{3}} $$ and the generating function becomes $$1/6\, \left( 1-z \right) ^{-3}-1/2\,{\frac {1}{ \left( -{z}^{2}+1 \right) \left( 1-z \right) }}+1/3\, \left( -{z}^{3}+1 \right) ^ {-1} $$ which gives the sequence $$0, 0, 6, 6, 12, 18, 24, 30, 42, 48, 60, 72, 84, 96,\ldots$$ which is six times OEIS A069905.
Similarly when $n=5$ we get the cycle index $$Z(P_5) = {\frac {{a_{{1}}}^{5}}{120}}-1/12\,a_{{2}}{a_{{1}}}^{3}+1/6\,a_{{ 3}}{a_{{1}}}^{2}+1/8\,a_{{1}}{a_{{2}}}^{2}\\-1/4\,a_{{4}}a_{{1}}-1/ 6\,a_{{2}}a_{{3}}+1/5\,a_{{5}}$$ and the generating function becomes $${\frac {1}{120\, \left( 1-z \right) ^{5}}}-1/12\,{\frac {1}{ \left( -{z}^{2}+1 \right) \left( 1-z \right) ^{3}}}\\+1/6\,{ \frac {1}{ \left( -{z}^{3}+1 \right) \left( 1-z \right) ^{2}}}+1 /8\,{\frac {1}{ \left( -{z}^{2}+1 \right) ^{2} \left( 1-z \right) }}-1/4\,{\frac {1}{ \left( -{z}^{4}+1 \right) \left( 1- z \right) }}\\-1/6\,{\frac {1}{ \left( -{z}^{2}+1 \right) \left( - {z}^{3}+1 \right) }}+1/5\, \left( -{z}^{5}+1 \right) ^{-1}$$ which gives the sequence $$0, 0, 0, 0, 0, 0, 0, 0, 0, 120, 120, 240, 360, 600, \ldots$$ which is $120$ times OEIS A001401.
The prefix of zeroes (these two examples start at one) compared to the two OEIS entries represents the fact that the minimum value attainable with $n$ distinct summands in $$[z^k] Z(P_n)\left(\frac{1}{1-z}\right)$$ is $0+1+2+\cdots+n-1 = 1/2\times n\times (n-1).$
These sequences match the formula by @bof, which is $$n! p_n\left(k - \frac{1}{2} n (n - 3)\right).$$
There are many more related links at MSE Meta on Burnside/Polya.
The Maple code for these was as follows.
p :=
proc(n, k)
option remember;
if k=1 then return 1 fi;
if n<k then return 0 fi;
p(n-1, k-1)+p(n-k,k)
end;
pet_cycleind_symm :=
proc(n)
local p, s;
option remember;
if n=0 then return 1; fi;
expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;
pet_cycleind_set :=
proc(n)
local p, s;
option remember;
if n=0 then return 1; fi;
expand(1/n*add((-1)^(l-1)*
a[l]*pet_cycleind_set(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
q1 :=
proc(n, k)
option remember;
local gf;
gf := pet_varinto_cind(1/(1-z), pet_cycleind_set(n));
n!*coeftayl(gf, z=0, k);
end;
q2 :=
proc(n, k)
option remember;
n!*p(k-n*(n-3)/2, n);
end;
Addendum. As per request we now give a mixed (combinatorial, algebraic) proof of the identity $$[z^n] Z(P_k)\left(\frac{1}{1-z}\right) = p_k\left(n - \frac{1}{2} k(k-3)\right).$$
Observe that we have reverted to the standard convention of using $n$ for the sum of the partition and $k$ for the number of parts.
By the same construction as before (PET) we have $$p_k\left(n - \frac{1}{2} k(k-3)\right) = [z^{n- \frac{1}{2} k(k-3)}] Z(S_k)\left(\frac{z}{1-z}\right)$$ with $Z(S_k)$ being the cycle index of the symmetric group (unlabelled multisets with operator $\mathfrak{M}_{=k}$.)
Using basic algebra this becomes $$[z^{n- \frac{1}{2} k(k-3)}] z^k Z(S_k)\left(\frac{1}{1-z}\right) = [z^{n- \frac{1}{2} k(k-3) -\frac{1}{2} 2k}] Z(S_k)\left(\frac{1}{1-z}\right) \\ = [z^{n- \frac{1}{2} k(k-1)}] Z(S_k)\left(\frac{1}{1-z}\right).$$
But this is the species $$\mathfrak{M}_{=k}\left(\mathcal{E} + \mathcal{Z} + \mathcal{Z}^2 + \mathcal{Z^3} + \cdots\right),$$ i.e. partitions with empty constitutents being permitted and constituents not necessarily distinct.
There is however a straighforward bijection between these and
partitions with potentially empty but distinct constituents. To go
from the former to the latter add $q$ circles on the left of every row
in the Ferrers diagram with row indices $q$ starting at zero. Now if
we had two adjacent rows with the first above the second with length
$b_1$ and $a_1$ where $b_1\ge a_1$ then the resulting pair is $b_1+q$
and $a_1+q-1.$ The difference between these is $b_1-a_1+1\ge 1$ so the
new pair is distinct and in non-decreasing order seen from below. To
go from the latter to the former remove $q$ circles from every row
(index is $q$), turning $b_2$ and $a_2$ where $b_2>a_2$ into $b_2-q$
and $a_2 -(q-1).$ The difference is $b_2-a_2-1\ge 0$ and the pair is
non-decreasing order but not necessarily distinct.
The number of circles being added/removed is
$$\sum_{q=0}^{k-1} q = \frac{1}{2} k(k-1).$$
We have shown that $$ [z^{n- \frac{1}{2} k(k-1)}] Z(S_k)\left(\frac{1}{1-z}\right) = [z^n] Z(P_k)\left(\frac{1}{1-z}\right).$$ Here we have $n\ge \frac{1}{2} k (k-1),$ both sides are zero otherwise. This concludes the argument.
Best Answer
Let's try to solve this problem starting from where you're at.
If the question's asking for different ordered doubles such that $x+y=50$ then there're $51$ different ordered pairs. So, the equation that $x+y=n$ can be satisfied by $n+1$ different ordered pairs $(x,y)$:
$$(0,n),(1,n-1),\ldots ,(n-1,1),(n,0)$$
For your case, asking for different ordered triples, we can partition the solution of $a+b+c=50$ into disjoint cases in which $c=0,c=1,\ldots ,c=49,c=50$.
So, if $c=0$, then $a+b=50\implies $ there are $50+1=51$ possible answers for $(a,b,0)$
Now, for $c=1\implies a+b=49\implies $ there are $49+1=50$ possible answers for $(a,b,1)$
$$\vdots$$
So, the general trend is that for each $c=m \implies$ that there are $50-m+1$ ways to choose $a$ and $b$ for that specific $c$.
$\therefore$ There are $51+50+\ldots +3+2+1=\frac{51\times 52}{2}=1326$ different ordered triples.