How do u find the "No of integral solutions of linear equations and inequations" ?

For equations like x1 + x2 + x3+....xr = n

I am super confused with this!!!!

Consider first a special case: x₁ + x₂ = 10.

The idea is basically this: suppose you have 10 identical (indistinguishable) balls and two baskets A and B.  You want to distribute these 10 balls in the two baskets so that each basket can have any number of balls. How many ways can you do so? Or how many distributions exsist? 

Note that the baskets have names. So putting (say) 2 balls in A and 8 in B is not the same as putting 2 in B and 8 in A. (We are talking about ordered pairs).

Transform further the problem as follows: Lets put all the balls in a row:

 o o o o o o o o o o

We take a spearator: | . Wherever I put this separator among the balls, the situation will correspond to a way of distributing balls. The balls on the left will always go to bag A and to the right will always go to B. For instance,

o o o | o o o o o o o

corresponds to 3 ball in A and 7 in B. Similarly, the situation

| o o o o o o o o o o

correspond to no ball in A and 10 balls in B. Now we can easily see that the separator can be placed at 11 positions. And accordingly there are 11 ways of distribution of the balls: (0,10), (1,9), (2,8), (3,7), (4,6), (5,5), (6,4), (7,3),(8,2),(9,1),(10,0) where the first number corresponds to balls in A and second to balls in B.

Now, if we assign the number of balls in A to the variable x₁ and the numbers of balls in B to x_2, then, effectively we found out the number of non-negative integral solutions of  x₁ + x₂ = 10.

Now, consider the general problem: find the number of non-negative integral solution of the equation

 x₁ + x₂ + x₃ + . . .+x_k  =n

Here, arguing as before, we place the n balls in a row:

o o o o o o . . . . o

Since we want to partition in to k baskets, we require k-1 separators. Now, the question is effectively to find out how many ways of placing these identical separators are? That is not a very difficult business. Effectively, we have (n + k -1) objects (n balls and k-1 separators) out of which n are identical of one kind and the remaining (k-1) are identical of another kind. How many ways can we arrange them in a row. The answer is straightforward:

that is ^n+k-1C_n.

Hence, this must be the number of non-negative integral solution of the general equation.

If you require positive solutions for the same equation, continuing with the balls and baskets model, basically we require that the least number of balls in each basket should be 1. So first out of the n balls, put 1 in each basket so that now no matter how I distribute the balls (after putting 1 ball in each basket), non of the baskets will be empty. But now we have the same old problem of finding the number of non-integral solution with n replaced by n-k:

x₁ + x₂ + x₃ + . . . + x_k  = n-k

Putting n-k in place of n in the answer of the last posting, we get the number of positive integral solution of the above equation as ^n-1C_k-1 .

@ Kayamant , can u give us an efficient algorithm for finding all the integral solutions for the system subject to0<= x[i]<k for all i = 1()r

I require it !!!

thanks a lot kaymant, u r really helping me bro. I'll be greatfull. That explanation was crystal clear and made super sense.

what is the meaning of finding coefficient of x^n in the expansion of (x + x^2 + x^3 +.......x^n)^r ?????

Please reply

@rajatsen91 , I am asking for an algorithm for finding all possible ( as defined by me )solutions of the above eqn , not the mere no of solution .

@Kayamant , nested loop will not do here as I want to make both k and n variable ( that is , I want to compute it for a number of times) , so u need to run a variable number of for loops then !!!!!