Number of non-negative distinct integer solutions of $x+y+z+w=10$

Question

I understand that there are already many questions relating to this, but my question is regarding some concept of mine that should be working but doesn't produce the right result.

So, I follow an approach similar to stars-and-bars. Let there be 10 underscores like this: _ _ _ _ _ _ _ _ _ _ such that I can insert a | at any of the $11$ empty positions. So, ||_ _ _ _ _ _ _|_ _ _ means $x=0,y=0,z=7,w=3$, which is indeed a solution of given equation. Therefore, to figure out number of distinct solutions for $x+y+z+w=10$, I have to find the number of sets of $3$ places, where I can insert 3 bars, out of the available $11$ places (allowing repetition)

I cannot use $^{11}C_3$ because that does not allow repetitions. By repetition, I mean a combination like |||_ _ _ _ _ _ _ _ _ _ ($x=y=z=0, w=10$) or |_ _ _||_ _ _ _ _ _ _ ($x=z=0,y=3,w=7$), i.e. more than 1 bars at same place.

Therefore, each of the three bars has $11$ available positions, and so the result should be $11\cdot11\cdot11=1331$

But the answer is obviously wrong since I already know (from textbook) that it should be $^{N+n-1}C_{n-1}=^{13}C_3=286$

I have read my solution again and again but can't figure out exactly what's the problem with it. Could anybody please spot the problem in my solution?

Answer 1

In your counting method, you would count |||_ _ _ _ _ _ _ _ _ _ once but |_ _ _||_ _ _ _ _ _ _ three times, because you give 11 choices for each bar, so you would count the latter once for each combination of choices:

1_ _ _23_ _ _ _ _ _ _ (note that swapping 2 and 3 here corresponds to the same choices)

2_ _ _13_ _ _ _ _ _ _

3_ _ _12_ _ _ _ _ _ _

Similarly, you would count |_ _ _|_|_ _ _ _ _ _ six times.

Answer 2

Repetition of numbers does not mean more than 1 bar at the same place (that means a zero), it means having bars equally spaced out.

Answer 3

Let us denote the number of ways of writing $n$ as a sum of $k$ distinct positive integers as $Q(n,k)$ and number of $k$ partitions of $n$ as $P(n,k)$. It can be proved that $$Q(n,k) = P\left(n-\frac{1}{2}k(k-1), k\right)$$ - see Barnard and Child, Higher Algebra. For $P(n,k)$ we have the recurrence relation $$P(n,k) = P(n-k,k)+P(n-1,k-1)$$ Using these, we can calculate $Q(10,4), Q(10,3), Q(10,2), Q(10,1)$. One combines these to get the required answer.