Permutations and combinations (Part - 1)- Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

 Page 1


DRAFT
Counting
Discussion 6.0.1. In the previous chapters, we had learnt that two sets, say A and B, have
the same cardinality if there exists a one-one and onto function f : A?B. We also learnt the
following two rules of counting which play a basic role in the development of this subject.
1. [Multiplication rule] If a task has n compulsory parts, say A
1
,A
2
,...,A
n
and the ith
part can be completed in m
i
=|A
i
| ways, i = 1,...,n, then the task can be completed in
m
1
m
2
···m
n
ways. In mathematical terms,
|A
1
×A
2
×···×A
n
|=|A
1
|·|A
2
|·····|A
n
|.
2. [Addition rule] If a task consists of n alternative parts, say A
1
,A
2
,...,A
n
, and the ith
part can be done in|A
i
| = m
i
ways, i = 1,...,n, then the task can be completed in
m
1
+m
2
+···+m
n
ways. In mathematical terms,
|A
1
?A
2
?···?A
n
| =|A
1
|+|A
2
|+···+|A
n
|, whenever A
i
nA
j
6=Ø,1=i<j=n.
De?nition 6.0.2. We use the notation n! = 1·2·····n. By convention, we take 0! = 1.
6.1 Permutations and Combinations
Example 6.1.1. How many three digit natural numbers can be formed using digits 0,1,··· ,9?
Identify the number of parts in the task and the type of the parts (compulsory or alternative).
Which rule applies here?
Ans: The task has three compulsory parts. Part 1: choose a digit for the leftmost place.
Part 2: choose a digit for the middle place. Part 3: choose a digit for the rightmost place.
Multiplication rule applies. Ans: 900.
Example 6.1.2. How many three digit natural numbers with distinct digits can be formed
using digits 1,··· ,9 such that each digit is odd or each digit is even? Identify the number of
parts in thetask andthe typeof theparts (compulsory or alternative). Which ruleapplies here?
91
Page 2


DRAFT
Counting
Discussion 6.0.1. In the previous chapters, we had learnt that two sets, say A and B, have
the same cardinality if there exists a one-one and onto function f : A?B. We also learnt the
following two rules of counting which play a basic role in the development of this subject.
1. [Multiplication rule] If a task has n compulsory parts, say A
1
,A
2
,...,A
n
and the ith
part can be completed in m
i
=|A
i
| ways, i = 1,...,n, then the task can be completed in
m
1
m
2
···m
n
ways. In mathematical terms,
|A
1
×A
2
×···×A
n
|=|A
1
|·|A
2
|·····|A
n
|.
2. [Addition rule] If a task consists of n alternative parts, say A
1
,A
2
,...,A
n
, and the ith
part can be done in|A
i
| = m
i
ways, i = 1,...,n, then the task can be completed in
m
1
+m
2
+···+m
n
ways. In mathematical terms,
|A
1
?A
2
?···?A
n
| =|A
1
|+|A
2
|+···+|A
n
|, whenever A
i
nA
j
6=Ø,1=i<j=n.
De?nition 6.0.2. We use the notation n! = 1·2·····n. By convention, we take 0! = 1.
6.1 Permutations and Combinations
Example 6.1.1. How many three digit natural numbers can be formed using digits 0,1,··· ,9?
Identify the number of parts in the task and the type of the parts (compulsory or alternative).
Which rule applies here?
Ans: The task has three compulsory parts. Part 1: choose a digit for the leftmost place.
Part 2: choose a digit for the middle place. Part 3: choose a digit for the rightmost place.
Multiplication rule applies. Ans: 900.
Example 6.1.2. How many three digit natural numbers with distinct digits can be formed
using digits 1,··· ,9 such that each digit is odd or each digit is even? Identify the number of
parts in thetask andthe typeof theparts (compulsory or alternative). Which ruleapplies here?
91
Ans: The task has two alternative parts. Part 1: form a three digit number with distinct
numbers from{1,3,5,7,9} using the odd digits. Part 2: form a three digit number with distinct
numbers from{2,4,6,8} using the even digits. Observe that Part 1 is a task having three
compulsory subparts. In view of 6.1.1, we see that Part 1 can be done in 60 ways. Part 2 is a
task having three compulsory subparts. In view of 6.1.1, we see that Part 2 can be done in 24
ways. Since our task has alternative parts, addition rule applies. Ans: 84.
De?nition 6.1.3. [r-sequence] Anr-sequence of elements of X is a sequence of length r with
elements from X. This may be viewed as a word of length r with alphabets from X or as a
function f :[r]?X. We write ‘an r-sequence of S’ to mean ‘an r-sequence of elements of S’.
Theorem 6.1.4. [Number of r-sequences] The number of r-sequences of [n] is n
r
.
Proof. Here the task has r compulsory parts. Choose the ?rst element of the sequence, the
second element and so on.
De?nition 6.1.6. [r-permutation, n-set] By an n-set, we mean a set containing n elements.
An r-permutation of an n-set S is an arrangement of r distinct elements of S in a row. An
r-permutation may be viewed as a one-one mapping f :[r]?S. An n-permutation of an n-set
is simply called a permutation.
Page 3


DRAFT
Counting
Discussion 6.0.1. In the previous chapters, we had learnt that two sets, say A and B, have
the same cardinality if there exists a one-one and onto function f : A?B. We also learnt the
following two rules of counting which play a basic role in the development of this subject.
1. [Multiplication rule] If a task has n compulsory parts, say A
1
,A
2
,...,A
n
and the ith
part can be completed in m
i
=|A
i
| ways, i = 1,...,n, then the task can be completed in
m
1
m
2
···m
n
ways. In mathematical terms,
|A
1
×A
2
×···×A
n
|=|A
1
|·|A
2
|·····|A
n
|.
2. [Addition rule] If a task consists of n alternative parts, say A
1
,A
2
,...,A
n
, and the ith
part can be done in|A
i
| = m
i
ways, i = 1,...,n, then the task can be completed in
m
1
+m
2
+···+m
n
ways. In mathematical terms,
|A
1
?A
2
?···?A
n
| =|A
1
|+|A
2
|+···+|A
n
|, whenever A
i
nA
j
6=Ø,1=i<j=n.
De?nition 6.0.2. We use the notation n! = 1·2·····n. By convention, we take 0! = 1.
6.1 Permutations and Combinations
Example 6.1.1. How many three digit natural numbers can be formed using digits 0,1,··· ,9?
Identify the number of parts in the task and the type of the parts (compulsory or alternative).
Which rule applies here?
Ans: The task has three compulsory parts. Part 1: choose a digit for the leftmost place.
Part 2: choose a digit for the middle place. Part 3: choose a digit for the rightmost place.
Multiplication rule applies. Ans: 900.
Example 6.1.2. How many three digit natural numbers with distinct digits can be formed
using digits 1,··· ,9 such that each digit is odd or each digit is even? Identify the number of
parts in thetask andthe typeof theparts (compulsory or alternative). Which ruleapplies here?
91
Ans: The task has two alternative parts. Part 1: form a three digit number with distinct
numbers from{1,3,5,7,9} using the odd digits. Part 2: form a three digit number with distinct
numbers from{2,4,6,8} using the even digits. Observe that Part 1 is a task having three
compulsory subparts. In view of 6.1.1, we see that Part 1 can be done in 60 ways. Part 2 is a
task having three compulsory subparts. In view of 6.1.1, we see that Part 2 can be done in 24
ways. Since our task has alternative parts, addition rule applies. Ans: 84.
De?nition 6.1.3. [r-sequence] Anr-sequence of elements of X is a sequence of length r with
elements from X. This may be viewed as a word of length r with alphabets from X or as a
function f :[r]?X. We write ‘an r-sequence of S’ to mean ‘an r-sequence of elements of S’.
Theorem 6.1.4. [Number of r-sequences] The number of r-sequences of [n] is n
r
.
Proof. Here the task has r compulsory parts. Choose the ?rst element of the sequence, the
second element and so on.
De?nition 6.1.6. [r-permutation, n-set] By an n-set, we mean a set containing n elements.
An r-permutation of an n-set S is an arrangement of r distinct elements of S in a row. An
r-permutation may be viewed as a one-one mapping f :[r]?S. An n-permutation of an n-set
is simply called a permutation.
Example 6.1.7. How many one-one maps f : [4]?A ={A,B,...,Z} are there?
Ans: The task has 4 compulsory parts: select f(1), select f(2), select f(3) and select f(4).
Note that f(2) cannot be f(1), f(3) cannot be f(1) or f(2) and so on. Now apply the multipli-
cation rule. Ans: 26·25·24·23 =
26!
22!
.
Theorem 6.1.8. [Number of r-permutations] The number of r-permutation of an n-set S is
P(n,r)=
n!
(n-r)!
.
Proof. Let us view an r-permutation as a one-one map from f : [r] ? S. Here the task
has r compulsory tasks: select f(1), select f(2), ..., select f(r) with the condition, for 2=
k= r, f(k)6?{f(1),f(2),...,f(k- 1)}. Multiplication rule applies. Hence, the number of
r-permutations equals n(n-1)···(n-r+1) =
n!
(n-r)!
.
De?nition 6.1.9. ByP(n,r), we denote the number of r-permutations of [n]. By convention,
P(n,0) = 1. Some books use the notation n
(r)
and call it the falling factorial of n. Thus, if
r >n then P(n,r)=n
(r)
= 0 and if n=r then P(n,r) =n
(r)
=n!.
Proposition 6.1.11. [principle of disjoint pre-images of equal size] Let A,B be ?nite sets
and f :A?B be a function such that for each pair b
1
,b
2
?B we have|f
-1
(b
1
)|=k =|f
-1
(b
2
)|
(recall that f
-1
(b
1
)nf
-1
(b
2
) =Ø). Then,|A| =k|B|.
Discussion 6.1.12. Consider the word AABAB. Give subscripts to the three As and the two
Bs and complete the following list. Notice that each of them will give us AABAB if we erase
the subscripts.
A
1
A
2
B
1
A
3
B
2
A
1
A
2
B
1
B
2
A
3
A
1
A
2
A
3
B
1
B
2
A
1
A
2
A
3
B
2
B
1
A
1
A
2
B
2
B
1
A
3
A
1
A
2
B
2
A
3
B
1
··· ··· ··· ···
··· ··· ··· ··· ···
··· ··· ··· ··· ···
··· ··· ··· B
2
A
3
B
1
A
1
A
2
B
2
A
3
B
1
A
2
A
1
Example 6.1.13. How many words of size 5 are there which use three A’s and two B’s?
Ans: PutA ={arrangements of A
1
,A
2
,A
3
,B
1
,B
2
} andB ={words of size 5 which use three
A’s and two B’s}. For each arrangement a? A, de?ne f(a) to be the word in B obtained by
erasing the subscripts. Then, the function f :A?B satis?es:
‘for each b,c?B,b6=c, we have|f
-1
(b)| =|f
-1
(c)| = 3!2! and f
-1
(b)nf
-1
(c) =Ø’.
Thus, by Proposition 6.1.11,|B|=
|A|
3!2!
=
5!
3!2!
.
Page 4


DRAFT
Counting
Discussion 6.0.1. In the previous chapters, we had learnt that two sets, say A and B, have
the same cardinality if there exists a one-one and onto function f : A?B. We also learnt the
following two rules of counting which play a basic role in the development of this subject.
1. [Multiplication rule] If a task has n compulsory parts, say A
1
,A
2
,...,A
n
and the ith
part can be completed in m
i
=|A
i
| ways, i = 1,...,n, then the task can be completed in
m
1
m
2
···m
n
ways. In mathematical terms,
|A
1
×A
2
×···×A
n
|=|A
1
|·|A
2
|·····|A
n
|.
2. [Addition rule] If a task consists of n alternative parts, say A
1
,A
2
,...,A
n
, and the ith
part can be done in|A
i
| = m
i
ways, i = 1,...,n, then the task can be completed in
m
1
+m
2
+···+m
n
ways. In mathematical terms,
|A
1
?A
2
?···?A
n
| =|A
1
|+|A
2
|+···+|A
n
|, whenever A
i
nA
j
6=Ø,1=i<j=n.
De?nition 6.0.2. We use the notation n! = 1·2·····n. By convention, we take 0! = 1.
6.1 Permutations and Combinations
Example 6.1.1. How many three digit natural numbers can be formed using digits 0,1,··· ,9?
Identify the number of parts in the task and the type of the parts (compulsory or alternative).
Which rule applies here?
Ans: The task has three compulsory parts. Part 1: choose a digit for the leftmost place.
Part 2: choose a digit for the middle place. Part 3: choose a digit for the rightmost place.
Multiplication rule applies. Ans: 900.
Example 6.1.2. How many three digit natural numbers with distinct digits can be formed
using digits 1,··· ,9 such that each digit is odd or each digit is even? Identify the number of
parts in thetask andthe typeof theparts (compulsory or alternative). Which ruleapplies here?
91
Ans: The task has two alternative parts. Part 1: form a three digit number with distinct
numbers from{1,3,5,7,9} using the odd digits. Part 2: form a three digit number with distinct
numbers from{2,4,6,8} using the even digits. Observe that Part 1 is a task having three
compulsory subparts. In view of 6.1.1, we see that Part 1 can be done in 60 ways. Part 2 is a
task having three compulsory subparts. In view of 6.1.1, we see that Part 2 can be done in 24
ways. Since our task has alternative parts, addition rule applies. Ans: 84.
De?nition 6.1.3. [r-sequence] Anr-sequence of elements of X is a sequence of length r with
elements from X. This may be viewed as a word of length r with alphabets from X or as a
function f :[r]?X. We write ‘an r-sequence of S’ to mean ‘an r-sequence of elements of S’.
Theorem 6.1.4. [Number of r-sequences] The number of r-sequences of [n] is n
r
.
Proof. Here the task has r compulsory parts. Choose the ?rst element of the sequence, the
second element and so on.
De?nition 6.1.6. [r-permutation, n-set] By an n-set, we mean a set containing n elements.
An r-permutation of an n-set S is an arrangement of r distinct elements of S in a row. An
r-permutation may be viewed as a one-one mapping f :[r]?S. An n-permutation of an n-set
is simply called a permutation.
Example 6.1.7. How many one-one maps f : [4]?A ={A,B,...,Z} are there?
Ans: The task has 4 compulsory parts: select f(1), select f(2), select f(3) and select f(4).
Note that f(2) cannot be f(1), f(3) cannot be f(1) or f(2) and so on. Now apply the multipli-
cation rule. Ans: 26·25·24·23 =
26!
22!
.
Theorem 6.1.8. [Number of r-permutations] The number of r-permutation of an n-set S is
P(n,r)=
n!
(n-r)!
.
Proof. Let us view an r-permutation as a one-one map from f : [r] ? S. Here the task
has r compulsory tasks: select f(1), select f(2), ..., select f(r) with the condition, for 2=
k= r, f(k)6?{f(1),f(2),...,f(k- 1)}. Multiplication rule applies. Hence, the number of
r-permutations equals n(n-1)···(n-r+1) =
n!
(n-r)!
.
De?nition 6.1.9. ByP(n,r), we denote the number of r-permutations of [n]. By convention,
P(n,0) = 1. Some books use the notation n
(r)
and call it the falling factorial of n. Thus, if
r >n then P(n,r)=n
(r)
= 0 and if n=r then P(n,r) =n
(r)
=n!.
Proposition 6.1.11. [principle of disjoint pre-images of equal size] Let A,B be ?nite sets
and f :A?B be a function such that for each pair b
1
,b
2
?B we have|f
-1
(b
1
)|=k =|f
-1
(b
2
)|
(recall that f
-1
(b
1
)nf
-1
(b
2
) =Ø). Then,|A| =k|B|.
Discussion 6.1.12. Consider the word AABAB. Give subscripts to the three As and the two
Bs and complete the following list. Notice that each of them will give us AABAB if we erase
the subscripts.
A
1
A
2
B
1
A
3
B
2
A
1
A
2
B
1
B
2
A
3
A
1
A
2
A
3
B
1
B
2
A
1
A
2
A
3
B
2
B
1
A
1
A
2
B
2
B
1
A
3
A
1
A
2
B
2
A
3
B
1
··· ··· ··· ···
··· ··· ··· ··· ···
··· ··· ··· ··· ···
··· ··· ··· B
2
A
3
B
1
A
1
A
2
B
2
A
3
B
1
A
2
A
1
Example 6.1.13. How many words of size 5 are there which use three A’s and two B’s?
Ans: PutA ={arrangements of A
1
,A
2
,A
3
,B
1
,B
2
} andB ={words of size 5 which use three
A’s and two B’s}. For each arrangement a? A, de?ne f(a) to be the word in B obtained by
erasing the subscripts. Then, the function f :A?B satis?es:
‘for each b,c?B,b6=c, we have|f
-1
(b)| =|f
-1
(c)| = 3!2! and f
-1
(b)nf
-1
(c) =Ø’.
Thus, by Proposition 6.1.11,|B|=
|A|
3!2!
=
5!
3!2!
.
DRAFT
Remark 6.1.14. Let us ?x n,k?N with 0= k= n and ask the question ‘how many words of
size n are there which uses k many A’s and (n-k) many B’s’?
Ans: Put A ={arrangements of A
1
A
2
...A
k
B
1
B
2
...B
n-k
} and B ={words of size n which
uses k many A’s and (n-k) many B’s} and proceed as above to get
|B|=
|A|
k!(n-k)!
=
n!
k!(n-k)!
as the required answer. Observe that the above argument implies
n!
k!(n-k)!
?Z. We denote this
number by P(n;k). Note that P(n;k) = P(n;n-k), Also, as per convention, P(n;k) = 0,
whenever k < 0 or n<k.
The above idea is further generalized below.
De?nition 6.1.15. Amultiset is a collection of objects wherean object can appear morethan
once. So, a set is a multiset. Note that{a,a,b,c,d} and{a,b,a,c,d} are the same 5-multisets.
Theorem 6.1.16. [Arrangements] Let us ?x n,k?N with 1=k=n and let S be a multiset
containing n
i
? N objects of i-th type, for i = 1,...,k with n =
k
P
i=1
n
i
. Then, there are
(n
1
+···+n
k
)!
n
1
!n
2
!···n
k
!
=
n!
n
1
!n
2
!···n
k
!
arrangements of the objects in S.
Proof. Assume that S consists of n
i
copies of A
i
, i = 1,...,k. Put
A ={A
11
,...,A
1n
1
,A
21
,...,A
2n
2
} and
B ={words of size made using elements of }.For each arrangementa?A,
de?ne f(a) to be the word in B obtained by erasing the right subscripts of the objects of a.
Then, the function f :A?B satis?es:
‘for each b,c?B, b6=c, we have|f
-1
(b)| =|f
-1
(c)| = and f
-1
(b)nf
-1
(c) =Ø’.
Thus, by Proposition 6.1.11,|B|=
|A|
n
1
!···n
k
!
=
(n
1
+···+n
k
)!
n
1
!···n
k
!
=
n!
n
1
!n
2
!···n
k
!
.
Theorem 6.1.17. [Allocation I: distinct locations; identical objects (n
i
of type i); at most
one per place] Fix a positive integer k and for 1= i= k, let G
i
’s be boxes containing n
i
?N
identical objects. Ifthe objects indistinct boxesare non-identical andn=
k
P
i=1
n
i
then, the number
of allocations of the objects in n distinct locations l
1
,...,l
n
, each location receiving at most one
object, is
n!
n
1
!···n
k
!(n-
P
n
i
)!
.
Proof. Consider a new group G
k+1
with n
k+1
= n-
k
P
1
n
i
objects of a new type. Notice that
an allocation of objects from G
1
,...,G
k
to n distinct places, where each location receives at
most one object, gives a unique arrangement of elements of G
1
,...,G
k+1
.
1
Thus, the number
1
Take an allocation of objects from G1,...,G
k
to n distinct places, where each location receives at most one
object. There are n
k+1
locations which are empty. Supply an object from G
k+1
to each of these locations.
We have created an arrangement of elements of G1,...,G
k+1
. Conversely, take an arrangement of elements of
G1,...,G
k+1
. Viewthis as an allocation of elements ofG1,...,G
k+1
ton distinct places. Emptythe places which
have received elements from G
k+1
. We have created an allocation of elements of G1,...,G
k
to n distinct places,
where each location receives at most one object.
Page 5


DRAFT
Counting
Discussion 6.0.1. In the previous chapters, we had learnt that two sets, say A and B, have
the same cardinality if there exists a one-one and onto function f : A?B. We also learnt the
following two rules of counting which play a basic role in the development of this subject.
1. [Multiplication rule] If a task has n compulsory parts, say A
1
,A
2
,...,A
n
and the ith
part can be completed in m
i
=|A
i
| ways, i = 1,...,n, then the task can be completed in
m
1
m
2
···m
n
ways. In mathematical terms,
|A
1
×A
2
×···×A
n
|=|A
1
|·|A
2
|·····|A
n
|.
2. [Addition rule] If a task consists of n alternative parts, say A
1
,A
2
,...,A
n
, and the ith
part can be done in|A
i
| = m
i
ways, i = 1,...,n, then the task can be completed in
m
1
+m
2
+···+m
n
ways. In mathematical terms,
|A
1
?A
2
?···?A
n
| =|A
1
|+|A
2
|+···+|A
n
|, whenever A
i
nA
j
6=Ø,1=i<j=n.
De?nition 6.0.2. We use the notation n! = 1·2·····n. By convention, we take 0! = 1.
6.1 Permutations and Combinations
Example 6.1.1. How many three digit natural numbers can be formed using digits 0,1,··· ,9?
Identify the number of parts in the task and the type of the parts (compulsory or alternative).
Which rule applies here?
Ans: The task has three compulsory parts. Part 1: choose a digit for the leftmost place.
Part 2: choose a digit for the middle place. Part 3: choose a digit for the rightmost place.
Multiplication rule applies. Ans: 900.
Example 6.1.2. How many three digit natural numbers with distinct digits can be formed
using digits 1,··· ,9 such that each digit is odd or each digit is even? Identify the number of
parts in thetask andthe typeof theparts (compulsory or alternative). Which ruleapplies here?
91
Ans: The task has two alternative parts. Part 1: form a three digit number with distinct
numbers from{1,3,5,7,9} using the odd digits. Part 2: form a three digit number with distinct
numbers from{2,4,6,8} using the even digits. Observe that Part 1 is a task having three
compulsory subparts. In view of 6.1.1, we see that Part 1 can be done in 60 ways. Part 2 is a
task having three compulsory subparts. In view of 6.1.1, we see that Part 2 can be done in 24
ways. Since our task has alternative parts, addition rule applies. Ans: 84.
De?nition 6.1.3. [r-sequence] Anr-sequence of elements of X is a sequence of length r with
elements from X. This may be viewed as a word of length r with alphabets from X or as a
function f :[r]?X. We write ‘an r-sequence of S’ to mean ‘an r-sequence of elements of S’.
Theorem 6.1.4. [Number of r-sequences] The number of r-sequences of [n] is n
r
.
Proof. Here the task has r compulsory parts. Choose the ?rst element of the sequence, the
second element and so on.
De?nition 6.1.6. [r-permutation, n-set] By an n-set, we mean a set containing n elements.
An r-permutation of an n-set S is an arrangement of r distinct elements of S in a row. An
r-permutation may be viewed as a one-one mapping f :[r]?S. An n-permutation of an n-set
is simply called a permutation.
Example 6.1.7. How many one-one maps f : [4]?A ={A,B,...,Z} are there?
Ans: The task has 4 compulsory parts: select f(1), select f(2), select f(3) and select f(4).
Note that f(2) cannot be f(1), f(3) cannot be f(1) or f(2) and so on. Now apply the multipli-
cation rule. Ans: 26·25·24·23 =
26!
22!
.
Theorem 6.1.8. [Number of r-permutations] The number of r-permutation of an n-set S is
P(n,r)=
n!
(n-r)!
.
Proof. Let us view an r-permutation as a one-one map from f : [r] ? S. Here the task
has r compulsory tasks: select f(1), select f(2), ..., select f(r) with the condition, for 2=
k= r, f(k)6?{f(1),f(2),...,f(k- 1)}. Multiplication rule applies. Hence, the number of
r-permutations equals n(n-1)···(n-r+1) =
n!
(n-r)!
.
De?nition 6.1.9. ByP(n,r), we denote the number of r-permutations of [n]. By convention,
P(n,0) = 1. Some books use the notation n
(r)
and call it the falling factorial of n. Thus, if
r >n then P(n,r)=n
(r)
= 0 and if n=r then P(n,r) =n
(r)
=n!.
Proposition 6.1.11. [principle of disjoint pre-images of equal size] Let A,B be ?nite sets
and f :A?B be a function such that for each pair b
1
,b
2
?B we have|f
-1
(b
1
)|=k =|f
-1
(b
2
)|
(recall that f
-1
(b
1
)nf
-1
(b
2
) =Ø). Then,|A| =k|B|.
Discussion 6.1.12. Consider the word AABAB. Give subscripts to the three As and the two
Bs and complete the following list. Notice that each of them will give us AABAB if we erase
the subscripts.
A
1
A
2
B
1
A
3
B
2
A
1
A
2
B
1
B
2
A
3
A
1
A
2
A
3
B
1
B
2
A
1
A
2
A
3
B
2
B
1
A
1
A
2
B
2
B
1
A
3
A
1
A
2
B
2
A
3
B
1
··· ··· ··· ···
··· ··· ··· ··· ···
··· ··· ··· ··· ···
··· ··· ··· B
2
A
3
B
1
A
1
A
2
B
2
A
3
B
1
A
2
A
1
Example 6.1.13. How many words of size 5 are there which use three A’s and two B’s?
Ans: PutA ={arrangements of A
1
,A
2
,A
3
,B
1
,B
2
} andB ={words of size 5 which use three
A’s and two B’s}. For each arrangement a? A, de?ne f(a) to be the word in B obtained by
erasing the subscripts. Then, the function f :A?B satis?es:
‘for each b,c?B,b6=c, we have|f
-1
(b)| =|f
-1
(c)| = 3!2! and f
-1
(b)nf
-1
(c) =Ø’.
Thus, by Proposition 6.1.11,|B|=
|A|
3!2!
=
5!
3!2!
.
DRAFT
Remark 6.1.14. Let us ?x n,k?N with 0= k= n and ask the question ‘how many words of
size n are there which uses k many A’s and (n-k) many B’s’?
Ans: Put A ={arrangements of A
1
A
2
...A
k
B
1
B
2
...B
n-k
} and B ={words of size n which
uses k many A’s and (n-k) many B’s} and proceed as above to get
|B|=
|A|
k!(n-k)!
=
n!
k!(n-k)!
as the required answer. Observe that the above argument implies
n!
k!(n-k)!
?Z. We denote this
number by P(n;k). Note that P(n;k) = P(n;n-k), Also, as per convention, P(n;k) = 0,
whenever k < 0 or n<k.
The above idea is further generalized below.
De?nition 6.1.15. Amultiset is a collection of objects wherean object can appear morethan
once. So, a set is a multiset. Note that{a,a,b,c,d} and{a,b,a,c,d} are the same 5-multisets.
Theorem 6.1.16. [Arrangements] Let us ?x n,k?N with 1=k=n and let S be a multiset
containing n
i
? N objects of i-th type, for i = 1,...,k with n =
k
P
i=1
n
i
. Then, there are
(n
1
+···+n
k
)!
n
1
!n
2
!···n
k
!
=
n!
n
1
!n
2
!···n
k
!
arrangements of the objects in S.
Proof. Assume that S consists of n
i
copies of A
i
, i = 1,...,k. Put
A ={A
11
,...,A
1n
1
,A
21
,...,A
2n
2
} and
B ={words of size made using elements of }.For each arrangementa?A,
de?ne f(a) to be the word in B obtained by erasing the right subscripts of the objects of a.
Then, the function f :A?B satis?es:
‘for each b,c?B, b6=c, we have|f
-1
(b)| =|f
-1
(c)| = and f
-1
(b)nf
-1
(c) =Ø’.
Thus, by Proposition 6.1.11,|B|=
|A|
n
1
!···n
k
!
=
(n
1
+···+n
k
)!
n
1
!···n
k
!
=
n!
n
1
!n
2
!···n
k
!
.
Theorem 6.1.17. [Allocation I: distinct locations; identical objects (n
i
of type i); at most
one per place] Fix a positive integer k and for 1= i= k, let G
i
’s be boxes containing n
i
?N
identical objects. Ifthe objects indistinct boxesare non-identical andn=
k
P
i=1
n
i
then, the number
of allocations of the objects in n distinct locations l
1
,...,l
n
, each location receiving at most one
object, is
n!
n
1
!···n
k
!(n-
P
n
i
)!
.
Proof. Consider a new group G
k+1
with n
k+1
= n-
k
P
1
n
i
objects of a new type. Notice that
an allocation of objects from G
1
,...,G
k
to n distinct places, where each location receives at
most one object, gives a unique arrangement of elements of G
1
,...,G
k+1
.
1
Thus, the number
1
Take an allocation of objects from G1,...,G
k
to n distinct places, where each location receives at most one
object. There are n
k+1
locations which are empty. Supply an object from G
k+1
to each of these locations.
We have created an arrangement of elements of G1,...,G
k+1
. Conversely, take an arrangement of elements of
G1,...,G
k+1
. Viewthis as an allocation of elements ofG1,...,G
k+1
ton distinct places. Emptythe places which
have received elements from G
k+1
. We have created an allocation of elements of G1,...,G
k
to n distinct places,
where each location receives at most one object.
DRAFT
of allocations of objects from G
1
,...,G
k
to n distinct places, where each location receives at
most one object, is the same as the number of arrangements of elements of G
1
,...,G
k+1
. By
Theorem 6.1.16, this number is
n!
n
1
!···n
k
!(n-
P
n
i
)!
.
De?nition 6.1.18. Let n,n
1
,n
2
,...,n
k
? N. Then, the number
n!
n
1
!···n
k
!(n-
P
n
i
)!
is de-
notedbyP(n;n
1
,...,n
k
). Thus,P(6;1,1,1) =P(6,3). Asaconvention, P(n;n
1
,...,n
k
) = 0
whenever either n
i
< 0; for some i,1=i=k, or
k
P
i=1
n
i
>n. Many texts use C(n;n
1
,··· ,n
k
) to
mean P(n;n
1
,··· ,n
k
). We shall interchangeably use them.
De?nition 6.1.19. [r-combination] An r-combination of an n-set S is an r-subset of S.
The number of r-subsets of an n-set is denoted by C(n,r). Thus, for any natural number n,
C(n,0) =C(n,n)= 1.
Theorem 6.1.20. [Combination] C(n,r)=P(n;r)=
n!
r!(n-r)!
.
Proof. By Theorem 6.1.17, the number of allocations of r identical objects in n distinct places
(p
1
,...,p
n
) with each place receiving at most 1 is P(n;r). Note that each such allocation A
uniquely corresponds to a r-subset of [n], namely to{i| p
i
receives an object by A}. Thus,
C(n,r)=P(n;r)=
n!
r!(n-r)!
.
Example 6.1.21. In how many ways can you allocate 3 identical passes to 10 students so that
each student receives at most one? Ans: C(10,3)
Theorem 6.1.22. [Pascal] C(n,r)+C(n,r+1) =C(n+1,r+1).
Proof. By Theorem 6.1.20, C(n,r)=
n!
r!(n-r)!
. Now verify the above identity to get the result.
Experiment
Complete the following list by ?lling the left list with all 3-subsets of [5] and the right list
with 3-subsets of [4] as well as with 2-subsets of [4] as shown below.
C(5,3)
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
{1,2,3}
{2,3,4}
{1,2,5}
{3,4,5}
{1,2,3}
{2,3,4}
?
?
?
?
?
?
?
C(4,3)
{1,2}
{3,4}
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
C(4,2)
Theorem 6.1.23. [Alternate proof of Pascal’s Theorem 6.1.22] Here we supply a combi-
natorial proof, i.e., ‘by associating the numbers with objects’. Let S = [n+1] and A be an
(r+1)-subset of S. Then, there are C(n+1,r+1) such sets with either n+1?A or n+16?A.
Note that n + 1? A if and only if A\{n + 1} is an r-subset of [n]. So, the number of
(r+1)-subsets of [n+1] which contain the element n+1 is, by de?nition, C(n,r).