Hey, I think the following argument works, but there might be a better way:
First consider the problem: x1 + x2 + ... = N, where xi's are non- negative. Soln: Let us assume we have N balls that we must separate into k groups (xi = number of balls in the ith group). If we represent each ball by "O" and separator by "|" then our problem is permuting (k-1) |'s and N O's. If all of them were distinct it is fact(N+k-1), but since N balls are identical and (k-1) separators are identical, Total number of permutations = fact(N+k-1)/fact(k-1)*fact(N) = (N+k-1)C(k-1) Now looking at the original problem: We can modify the above solution by considering each separator to be "| O" i.e., a separator and a ball to the right. Since all the xi's contain atleast one ball, let us fix a ball to the left of all the permutations. We now have N-(k-1) - 1 = N-k balls and k-1 separators. Using the above result, No of permutations = (N-1)C(k-1). Hope that helps, Harshith On Apr 9, 1:04 am, GentLeBoY <vikrantsing...@gmail.com> wrote: > no. of solutions to linear equation as > x1+x2+x3+. . .+xk=n , all variables are positive natural numbers > how is it (n-1)C(k-1) plz explain -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
