Combinatorics with a condition of maximum sum I have to say that English is not my first language, so excuse me for any mistakes.
I was learning combinatorics to prepare myself for probability and I thought of this problem and I'm not sure if I got the right answer.
Let's say I have $3$ variables ($X$, $Y$ and $Z$) each one can assume a positive integer value, including zero ($0$, $1$, $2$, ..., $100$), but the sum of the three must be $100$. How many combinations do I have ? Different variables can have the same value.
My first guess was $100!/(97!3!)$, but that could work without the rule that states the sum must be $100$, so did I got it right or there is another formula ?
 A: We use a technique called stars and bars for this question. The general form for stars and bars is that the number of integer solutions to the Diophantine $x_{1}+x_{2}+x_{3}+\cdots+x_{k}=n$ such that all numbers $(x_{1},x_{2},x_{3},\cdots,x_{k})$ are nonnegative is
$$\binom{n+k-1}{k-1}.$$
Let's walk through a proof of this formula using your question. We are trying to find the number of nonnegatve integer solutions for $(X,Y,Z)$ to the equation $X+Y+Z=100$. We imagine $100$ stars being lined up in a row. When we put in $2$ bars splitting the stars into $3$ groups, each group represents $X,Y,$ and $Z$, more specifically the number of stars in each group, which all adds up to the $100$ stars. Thus, the number of ways to answer your problem is basically the number of ways to arrange a line of $100$ stars and $2$ bars to make $102$ total objects. By choosing $2$ places for the bars, the other places of the other $100$ stars are already guaranteed. Thus, we just have to choose $2$ places out of $102$, which can obviously be done in
$$\binom{102}{2}=\boxed{5151}$$ ways.
More generally, to prove that the equation $x_{1}+x_{2}+x_{3}+\cdots x_{k}=n$ such that each of $(x_{1},x_{2},x_{3},\cdots,x_{k})$ is nonnegative has $\binom{n+k-1}{k-1}$ ordered solutions for the $k$-tuple $(x_{1},x_{2},x_{3},\cdots,x_{k})$, we let $n$ stars be lined up in a row. By inserting $k-1$ bars anywhere between any two stars, we create $k$ groups of stars. Each number $x_{1},x_{2},x_{3},\cdots,x_{k}$ would then represent the number of stars in each of the $k$ groups, all adding up to the $n$ stars. Thus, the number of ways desired is the number of ways to arrange $n$ stars and $k-1$ bars in a line to make $n+k-1$ total objects, choosing $k-1$ places, fixing the spots for the another $n$ stars. Expressing the number of ways to do this gives us our desired formula,
$$\binom{n+k-1}{k-1}.$$
A: As mentioned in my comment, the page will lead you to the theorem:
For any pair of positive integers n and k, the number of k-tuples of non-negative integers whose sum is n is equal to the number of multisets of cardinality $k−1$ taken from a set of size $n+1$.
Therefore for our case n=100 and k=3, we have:
$${{100+1}\choose{3-1}}={{101}\choose{2}}=5050$$
If you haven't seen the theorem before, it's probably best you read the proofs to gain an intuition for where the formula came from and where you apply it.
