 ×  Custom Search
cancel   ×

# Important Formulas(Part 8) - Permutation and Combination

## Counting non-negative integral solutions

Number of non-negative integral solutions of equation $x_1+x_2+\cdots+x_n=k$

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

$=\dbinom{k+n-1}{n-1}$ = (k+n-1)C(n-1)

## Counting positive integral solutions

Number of positive integral solutions of equation $x_1+x_2+\cdots+x_n=k$

= 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}$ = (k-1)C(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)= 10C3 = 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) = 14C2 = 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) = 14C2 = 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 5th 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) = 14C4 = 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
$\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
x1+x2+...+xm = n? 0 0 reply ayush
2015-06-10 10:57:40
what s this c used in finding probability called 0 0 reply anonfrog
2015-09-24 15:34:09
It is just a symbol for no. of combinations. Often verbalized as "choose". 0 0