Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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
add comment

1 Answer 1

up vote 1 down vote accepted

Your words:

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.