ad
Important Formulas(Part 7) - Permutation and Combination
Here, we are counting the number of ways in which k balls can be distributed into n boxes under various conditions.
The conditions which are generally asked are
1. The balls are either distinct or identical.
2. The boxes are either distinct or identical.
3. No box can contain more than one ball or any box may contain more than one ball.
4. No box can be empty or any box can be empty.
This is an area which many students choose to ignore. However these concepts will help us in solving many advanced problems in permutations and combinations.
We can use the principles of permutations and combinations to deal with problems of distributing balls into boxes. The concept of identical boxes are more complicated and generally studied in detail in combinatorics.
The table below explains the number of ways in which k balls can be distributed into n boxes under various conditions. All the below mentioned cases are derived under the assumption that the order in which the balls are placed into the boxes is not important. (i.e., if a box has many balls, the order of the balls inside the box is not important).
| Distribution of | How many balls boxes can contain | ||||
| k Balls | into n Boxes | No Restrictions | ≤ 1 (At most one) | ≥ 1 (At least one) | = 1 (Exactly one) |
| Distinct | Distinct | nk (formula 1) | nPk (formula 2) | S(k,n) × n! (formula 3) (more info) | nPn = n! if k = n 0 if k ≠ n (formula 4) |
| Identical | Distinct | (k+n-1)C(n-1) (formula 5) | nCk (formula 6) | (k-1)C(n-1) (formula 7) | 1 if k = n 0 if k ≠ n (formula 8) |
| Distinct | Identical | $\sum\limits_{i=1}^{n}\text{S(k,i)}$ (formula 9) (more info) | 1 if k ≤ n 0 if k > n (formula 10) | S(k,n) (formula 11) (more info) | 1 if k = n 0 if k ≠ n (formula 12) |
| Identical | Identical | $\sum\limits_{i=1}^{n}\text{P(k, i)}$ (formula 13) (more info) | 1 if k ≤ n 0 if k > n (formula 14) | P(k, n) (formula 15) (more info) | 1 if k = n 0 if k ≠ n (formula 16) |
| Distribution of k distinct balls into n distinct boxes | |||
| No Restrictions | Each box can contain at most one ball (≤ 1) | Each box must contain at least one ball (≥ 1) | Each box must contain exactly one ball (=1) |
| nk (formula 1) | nPk (formula 2) | S(k,n) × n! (formula 3) (more info) | nPn if k=n 0 if k≠n (formula 4) (Note: nPn=n!) |
| Distribution of k identical balls into n distinct boxes | |||
| No Restrictions | Each box can contain at most one ball (≤ 1) | Each box must contain at least one ball (≥ 1) | Each box must contain exactly one ball (=1) |
| (k+n-1)C(n-1) (formula 5) | nCk (formula 6) | (k-1)C(n-1) (formula 7) | 1 if k = n 0 if k ≠ n (formula 8) |
| Distribution of k distinct balls into n identical boxes | |||
| No Restrictions | Each box can contain at most one ball (≤ 1) | Each box must contain at least one ball (≥ 1) | Each box must contain exactly one ball (=1) |
| $\sum\limits_{i=1}^{n}\text{S(k,i)}$ (formula 9) (more info) | 1 if k ≤ n 0 if k > n (formula 10) | S(k,n) (formula 11) (more info) | 1 if k = n 0 if k ≠ n (formula 12) |
| Distribution of k identical balls into n identical boxes | |||
| No Restrictions | Each box can contain at most one ball (≤ 1) | Each box must contain at least one ball (≥ 1) | Each box must contain exactly one ball (=1) |
| $\sum\limits_{i=1}^{n}\text{P(k, i)}$ (formula 13) (more info) | 1 if k ≤ n 0 if k > n (formula 14) | P(k, n) (formula 15) (more info) | 1 if k = n 0 if k ≠ n (formula 16) |
S(k,n), Stirling number of the second kind can be defined as
$\text{S(k,n)} = \dfrac{1}{n!}\sum\limits_{i=0}^{n-1} \left(-1\right)^i n_{C_i}(n-i)^k$
$=\dfrac{1}{n!}[n_{C_0}(n-0)^k - n_{C_1}(n-1)^k $ $+ n_{C_2}(n-2)^k + \cdots + \left(-1\right)^{n-1}n_{C_{n-1}}(1)^k]$
Special Cases
S(0,0) = 1
S(k,0) = 0 for k ≥ 1
S(k,n) = 0 for k < n
$\text{S(k,n)} = \dfrac{1}{n!}\sum\limits_{i=0}^{n-1} \left(-1\right)^i n_{C_i}(n-i)^k$
$=\dfrac{1}{n!}[n_{C_0}(n-0)^k - n_{C_1}(n-1)^k $ $+ n_{C_2}(n-2)^k + \cdots + \left(-1\right)^{n-1}n_{C_{n-1}}(1)^k]$
Special Cases
S(0,0) = 1
S(k,0) = 0 for k ≥ 1
S(k,n) = 0 for k < n
P(k,n) = The number of partitions of the integer k into n parts.
Formula for P(k,n) is much harder than that of S(k, n). The following examples will explain how we can find the value of P(k,n).
What is the value of P(6,3) ?
The partitions of 6 into 3 parts are
4 + 1 + 1
3 + 2 + 1
2 + 2 + 2
(Note that 4 + 1 + 1, 1 + 4 + 1, 1 + 1 + 4 are same. Similarly we need to consider all other cases as well)
Hence the number of partitions of 6 into 3 parts = 3
=> P(6,3) = 3
What is the value of P(6,2) ?
The partitions of 6 into 2 parts are
1 + 5
2 + 4
3 + 3
Hence the number of partitions of 6 into 2 parts = 3
=> P(6,2) = 3
What is the value of P(6,1) ?
Here, we count the number of partitions of 6 into 1 part.
Clearly the number of such partitions = 1
=> P(6,1) = 1
Now try to find out the value of P(6,4)
The partitions of 6 into 4 parts are
1 + 1 + 1 + 3
1 + 2 + 2 + 2
Hence the number of partitions of 6 into 4 parts = 2
=> P(6,4) = 2
Special Cases
P(0, 0) = P(k, k) = P(k, k-1) = P(k, 1) = 1
Formula for P(k,n) is much harder than that of S(k, n). The following examples will explain how we can find the value of P(k,n).
What is the value of P(6,3) ?
The partitions of 6 into 3 parts are
4 + 1 + 1
3 + 2 + 1
2 + 2 + 2
(Note that 4 + 1 + 1, 1 + 4 + 1, 1 + 1 + 4 are same. Similarly we need to consider all other cases as well)
Hence the number of partitions of 6 into 3 parts = 3
=> P(6,3) = 3
What is the value of P(6,2) ?
The partitions of 6 into 2 parts are
1 + 5
2 + 4
3 + 3
Hence the number of partitions of 6 into 2 parts = 3
=> P(6,2) = 3
What is the value of P(6,1) ?
Here, we count the number of partitions of 6 into 1 part.
Clearly the number of such partitions = 1
=> P(6,1) = 1
Now try to find out the value of P(6,4)
The partitions of 6 into 4 parts are
1 + 1 + 1 + 3
1 + 2 + 2 + 2
Hence the number of partitions of 6 into 4 parts = 2
=> P(6,4) = 2
Special Cases
P(0, 0) = P(k, k) = P(k, k-1) = P(k, 1) = 1
Comments(5)
Cell2015-12-24 08:29:08
The formula 5 should be incorrect. That is no way the formula will be k+n-1 C k
The correct formula should be k+n-1 C n-1
The correct formula should be k+n-1 C n-1
sam2016-01-08 12:23:51
Both are same indeed.
We know ncr = nc(n-r). Using this, we have
(k+n-1) C k = (k+n-1) C (k+n-1-k) = (k+n-1) C (n-1)
We know ncr = nc(n-r). Using this, we have
(k+n-1) C k = (k+n-1) C (k+n-1-k) = (k+n-1) C (n-1)
0
0
asdad2013-12-09 17:37:43
What is the value of p(11,3)?
Is it 22?
Any other way instead of counting each possible way?
shiv2015-04-01 09:39:50
Yeah
X+Y +Z = 11
(a^0 + a^1 +a^2......a^11)^3
The coeff of a^11 in this will be the answer
0
0
preview
▲
Terms & ConditionsCopyright PolicyPrivacy Policy
careerbless@gmail.com
careerbless@gmail.com
© 2012-2020 careerbless.com. All rights reserved.