How many non – negative integral solutions are possible?

Let's say we have to divide 16 prizes among 3 boys such that each boy gets at least one prize i.e x+y+z =16, where x, y and z are positive integers.

Imagine 16 prizes placed one besides the other. Now we have 15 gaps in between them and to divide this into 3 parts we nee d to select any 2 two gaps from the available 15 gaps which can be done in 15C2 ways = 105 ways.

Now in the given question x, y and z are non-negative which mean a boy can recieve any number of prizes i.e 0 is also allowed. Imagining as in the above case we will have 18 (15+3)gaps from which we need to select 2 gaps which can be done in 18C2 = 153 ways.

So in general....

The number of solutions of the equation x1+x2+--------+xr = n, where x1,x2,...xr belongs to positive integers = (n-1)C(r-1)

The number of solutions of the equation x1+x2+--------+xr = n, where x1,x2,...xr belongs to non-negative integers = (n+r-1)C(r-1)

Vemuri wrote:How many non � negative integral solutions are possible for the given equation?
x + y + z = 16

Ans: 153

This problem is the same as the following:

How many ways can 16 identical chocolates be distributed among three children X, Y and Z?

Use the SEPARATOR method.

16 identical chocolates are to be separated into -- at most -- 3 groupings.
Thus, we need 16 chocolates and two separators:
OOOO|OOOOOO|OOOOOO

Each arrangement of the elements above represents one way to distribute the 16 chocolates among three children X, Y and Z:
OOOO|OOOOOO|OOOOOO = X gets 4 chocolates, Y gets 6 chocolates, Z gets 6 chocolates.
OOOOOOOO||OOOOOOOO = X gets 8 chocolates, Y gets 0 chocolates, Z gets 8 chocolates.
OOOOOOOOOOOOOOOO|| = X gets all 16 chocolates.
And so on.

To count all of the possible distributions, we simply need to count the number of ways to arrange the 18 elements above (the 16 identical chocolates and the two identical separators).
The number of ways to arrange 18 elements = 18!.
But when an arrangement includes identical elements, we must divide by the number of ways to arrange the identical elements.
The reason:
When the identical elements swap positions, the arrangement doesn't change, reducing the total number of unique arrangements.
Thus, we must divide by 16! (the number of ways to arrange the 16 identical chocolates) and 2! (the number of ways to arrange the 2 identical separators):
18!/(16! 2!) = 153.