We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.More informationAgree
ad

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)$

Comments(3)

profileSiddhant
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?
like 0 dislike 0 reply
profileayush
2015-06-10 10:57:40 
what s this c used in finding probability called
like 0 dislike 0 reply
profileanonfrog
2015-09-24 15:34:09 
It is just a symbol for no. of combinations. Often verbalized as "choose".
like 0 dislike 0

Add Your Comment

(use Q&A for new questions)
?
Name
cancel
preview