ad

= Number of ways in which $k$ identical balls can be distributed into $n$ distinct boxes

$=\dbinom{k+n-1}{n-1}$ =

= Number of ways in which $k$ identical balls can be distributed into $n$ distinct boxes where each box must contain at least one ball

$=\dbinom{k-1}{n-1}$ =

**Example 1:** Find number of non-negative integral solutions of the equation

$x_1+x_2+x_3+x_4=7$

One solution is $x_1=3, x_2=3, x_3=0, x_4=1$

Another solution is $x_1=1, x_2=0, x_3=3, x_4=3$

Note that $x_1= -1, x_2=0, x_3=0, x_4=8$ is not a solution because each $x_i$ must be a non-negative integer.

Total number of solutions

= ^{(k+n-1)}C_{(n-1)} = ^{(7+4-1)}C_{(4-1)}= ^{10}C_{3} = 120

**Example 2:** Find number of positive integral solutions of the equation

$x_1+x_2+x_3=15$

**Solution 1**

Using the formula, required number of solutions

= ^{(k-1)}C_{(n-1)} = ^{(15-1)}C_{(3-1)} = ^{14}C_{2} = 91

**Solution 2**

Give one to $x_1$, one to $x_2$ and one to $x_3$.

Remaining quantity is 15-3=12 which is to be distributed to $x_1, x_2$ and $x_3$

Therefore, required number of solutions

= number of non-negative integral solutions of

$x_1+x_2+x_3=12$

= ^{(k+n-1)}C_{(n-1)} = ^{(12+3-1)}C_{(3-1)} = ^{14}C_{2} = 91

**Example 3:** A lift starts at the basement with 10 people (6 men and 4 women, excluding the operator) and all get out by the time lift reaches 5^{th} floor. Find the number of ways in which the operator could have perceived the people leaving the lift if all people look alike to the operator?

Required number of ways

= Number of non-negative integer solutions to $x_1+x_2+x_3+x_4+x_5=10$

= ^{(k+n-1)}C_{(n-1)} = ^{(10+5-1)}C_{(5-1)} = ^{14}C_{4} = 1001

Let $x_1, x_2, \cdots , x_m$ be integers.

Then the number of solutions to the equation

$x_1+x_2+\cdots+x_m=n$

subject to the conditions $a_1 ≤ x_1 ≤ b1, a_2 ≤ x_2 ≤ b_2, $ $\cdots,a_m ≤ x_m ≤ b_m$

is equal to the coefficient of $x^n$ in

Then the number of solutions to the equation

$x_1+x_2+\cdots+x_m=n$

subject to the conditions $a_1 ≤ x_1 ≤ b1, a_2 ≤ x_2 ≤ b_2, $ $\cdots,a_m ≤ x_m ≤ b_m$

is equal to the coefficient of $x^n$ in

$\left(x^{a_1}+x^{a_1+1}+\cdots+x^{b_1}\right)\left(x^{a_2}+x^{a_2+1}+\cdots+x^{b_2}\right)\cdots \left(x^{a_m}+x^{a_m+1}+\cdots+x^{b_m}\right)$

$\left(x^{a_1}+x^{a_1+1}+\cdots+x^{b_1}\right)\\×\left(x^{a_2}+x^{a_2+1}+\cdots+x^{b_2}\right)\\ \cdots \\× \left(x^{a_m}+x^{a_m+1}+\cdots+x^{b_m}\right)$

Siddhant

2016-05-10 10:08:46

sir, please give me the full explanation of the last case, i.e., total no. of solutions of the equation

x_{1}+x_{2}+...+x_{m} = n?

x

anonfrog

2015-09-24 15:34:09

It is just a symbol for no. of combinations. Often verbalized as "choose".

0
0

preview