Consider the traditional combinatorial problem
How many non-negative solutions does this equation have ?
X_1 + X_2 +....+X_n = N
For example, X_1 + X_2 = 10
Let me write a string of ten zeroes.
0 0 0 0 0 0 0 0 0 0
Let me insert 1 in any of the 11 available positions adjacent to any of the zeroes.This 1 acts as a separator, thus giving the value of X_1 and X_2.Hence there are (10+1)C 1 ways to arrange ie,. 11 solutions.
generalizing the same
original equation has (N+n-1)C(n-1) solutions.
How many solutions are there if X_i < style="color: rgb(255, 0, 0);">[S]
Subscribe to:
Post Comments (Atom)
5 comments:
I found that this could be solved by application the same formula in a complicatedly repetitive fashion.I shall post it if nobody comes up with something elegant, better.
(N+n-1)C(n-1) - (N-m+n-2)C(n-2).
Explanation:
Just set one of the X_i to m and find number of solutions for
Summation(X_i) = N-m. (i goes from 1 to n-1)
This gives you all solutions with at least one X_i > m.
Does this solve the problem ?
Correction.
What needs to be subtracted is
Diff =
Summation[ (N - k + n - 2)C(n-2) ]
where k ranges from m to N.
This gives all solutions with at least one X_i >= m.
correct solution
surprising when I look back...how did I miss this?????
Post a Comment