# what is the difference between these two counting?

From combinatorics we know that the number number of non-negative integral solutions of $$x_1+x_2+x_3+\cdots+x_r=n$$ is given by $\binom{n+r-1}{r-1}$,if I have understood this properly then it means all solutions such that $x_i \in [0,9]$

For $r=3$ and $n=12$,does this problem boils down to find all possible solution of the form say $[x_1,x_2,x_3]$ between $[0,0,0]$ to $[9,9,9]$?But using the combinatorial formula we would get $\binom{14}{2}=91$ where as brute-forcing gives the values to be $73$ which are as follows:

[0, 3, 9] [0, 4, 8] [0, 5, 7] [0, 6, 6] [0, 7, 5] [0, 8, 4] [0, 9, 3] [1, 2, 9] [1, 3, 8] [1, 4, 7] [1, 5, 6] [1, 6, 5] [1, 7, 4] [1, 8, 3] [1, 9, 2] [2, 1, 9] [2, 2, 8] [2, 3, 7] [2, 4, 6] [2, 5, 5] [2, 6, 4] [2, 7, 3] [2, 8, 2] [2, 9, 1] [3, 0, 9] [3, 1, 8] [3, 2, 7] [3, 3, 6] [3, 4, 5] [3, 5, 4] [3, 6, 3] [3, 7, 2] [3, 8, 1] [3, 9, 0] [4, 0, 8] [4, 1, 7] [4, 2, 6] [4, 3, 5] [4, 4, 4] [4, 5, 3] [4, 6, 2] [4, 7, 1] [4, 8, 0] [5, 0, 7] [5, 1, 6] [5, 2, 5] [5, 3, 4] [5, 4, 3] [5, 5, 2] [5, 6, 1] [5, 7, 0] [6, 0, 6] [6, 1, 5] [6, 2, 4] [6, 3, 3] [6, 4, 2] [6, 5, 1] [6, 6, 0] [7, 0, 5] [7, 1, 4] [7, 2, 3] [7, 3, 2] [7, 4, 1] [7, 5, 0] [8, 0, 4] [8, 1, 3] [8, 2, 2] [8, 3, 1] [8, 4, 0] [9, 0, 3] [9, 1, 2] [9, 2, 1] [9, 3, 0]

I want to know what exactly is the combinatorial problem is over-counting?

-
The binomial coefficient counts all solutions $(x_1, \ldots, x_r)$, not just those with $0 \leq x_i \leq 9$. I guess if you bruteforce all solutions with $0 \leq x_i \leq 12$ you will find $18$ more solutions. – TMM Sep 20 '11 at 0:26
@Srivatsan Narayanan:aha got it!Thanks you answered this whole question for me. – Quixotic Sep 20 '11 at 0:26
@ThijsLaarhoven: I didn't see your comment until now. Why don't you add your comment as an answer, and I'll delete my answer. – JavaMan Sep 20 '11 at 0:31

From combinatorics we know that the number number of non-negative integral solutions of $$x_1+x_2+x_3+\cdots+x_r=n$$ is given by $\binom{n+r-1}{r-1}$,if I have understood this properly then it means all solutions such that $x_i \in [0,9]$
The combinatorial approach is counting all possible non-negative integral solutions where as your brute-force is restricting to only digits $[0,9]$.
In other words,in the binomial cofficeints case possible solutions for individual $x_i$-s is in $0 \leq x_i \lt \infty$ where as in your case $x_i \in$ $[0,9]$,hence the disagreement.