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

 Page 1


6.3 Solutions in Non-negative Integers
De?nition 6.3.1. [Solution in nonnegative integers] Recall that N
0
:= N?{0}. A point
p = (p
1
,...,p
k
)?N
k
0
with p
1
+···+p
k
=n is called a solution of the equation x
1
+···+x
k
=n
in nonnegative integers or a solution of x
1
+··· +x
k
= n in N
0
. Two solutions (p
1
,...,p
k
)
and (q
1
,...,q
k
) are said to be the same if p
i
= q
i
, for each i = 1,...,k. Thus, (5,0,0,5) and
(0,0,5,5) are two di?erent solutions of x+y+z+t = 10 inN
0
.
Example 6.3.2. Determine the number of
1. words which uses 3 A’s and 6 B’s.
2. arrangements of 3 A’s and 6 B’s.
3. distinct strings that can be formed using 3 A’s and 6 B’s.
4. solutions of the equation x
1
+x
2
+x
3
+x
4
= 6, where each x
i
?N
0
and 0=x
i
= 6.
5. ways of placing 6 indistinguishable balls into 4 distinguishable boxes.
6. 3 subsets of an 9-set.
Solution: Observe that all the problems correspond to forming strings using +’s (or|’s
or bars) and 1’s (or balls or dots) in place of A’a and B’s, respectively?
Page 2


6.3 Solutions in Non-negative Integers
De?nition 6.3.1. [Solution in nonnegative integers] Recall that N
0
:= N?{0}. A point
p = (p
1
,...,p
k
)?N
k
0
with p
1
+···+p
k
=n is called a solution of the equation x
1
+···+x
k
=n
in nonnegative integers or a solution of x
1
+··· +x
k
= n in N
0
. Two solutions (p
1
,...,p
k
)
and (q
1
,...,q
k
) are said to be the same if p
i
= q
i
, for each i = 1,...,k. Thus, (5,0,0,5) and
(0,0,5,5) are two di?erent solutions of x+y+z+t = 10 inN
0
.
Example 6.3.2. Determine the number of
1. words which uses 3 A’s and 6 B’s.
2. arrangements of 3 A’s and 6 B’s.
3. distinct strings that can be formed using 3 A’s and 6 B’s.
4. solutions of the equation x
1
+x
2
+x
3
+x
4
= 6, where each x
i
?N
0
and 0=x
i
= 6.
5. ways of placing 6 indistinguishable balls into 4 distinguishable boxes.
6. 3 subsets of an 9-set.
Solution: Observe that all the problems correspond to forming strings using +’s (or|’s
or bars) and 1’s (or balls or dots) in place of A’a and B’s, respectively?
DRAFT
ABBBABABB
ABBBBBAAB
BBABBBABA
+111+1+11 = 0+3+1+2
+11111++1 = 0+5+0+1
11+111+1+ = 2+3+1+0
|• • •| • |• •
|• • • • •|| •
• •|• • •|•|
Figure 6.2: Understanding the three problems
Note that the A’s are indistinguishable among themselves and the same holds for B’s.
Thus, we need to ?nd 3 places, from the 9 = 3+6 places, for the A’s. Hence, the answer
is C(9,3). The answer will remain the same as we just need to replace A’s with +’s (or
|’s) and B’s with 1’s (or balls) in any string of 3 A’s and 6B’s. See Figure 6.2 or note that
four numbers can be added using 3 +’s or four adjacent boxes can be created by putting
3 vertical lines or|’s.
In general, we have the following result.
Theorem 6.3.3. [solutions in N
0
] The number of solutions of x
1
+··· + x
r
= n in N
0
is
C(n+r-1,n).
Proof. Each solution (x
1
,...,x
r
) may be viewed as an arrangement of n dots and r-1 bars.
‘Put x
1
many dots; put a bar; put x
2
many dots; put another bar; continue; and end by
putting x
r
many dots.’
For example, (0,2,1,0,0) is associated to|••|•|| and vice-versa. Thus, there are C(n+r-
1,r-1) arrangements of n dots and r-1 bars.
Theorem 6.3.4. (a) The number of solutions of x
1
+···+x
r
=n in nonnegative integers is
C(n+r,n).
(b) The number of terms in the algebraic expansion of (x
1
+···+x
r
)
n
is C(n+r-1,n).
Proof. (a)Anysolutionofx
1
+···+x
r
=nuniquelycorrespondstoasolutionofx
1
+···+x
r
+y =
n in nonnegative integers..
(b)Notethateachterminthealgebraicexpansionof(x
1
+···+x
r
)
n
hastheformx
i
1
1
x
i
2
2
···x
ir
r
,
withi
1
+i
2
+···+i
r
=n. Thus,eachtermuniquelycorrespondstoasolutionofi
1
+i
2
+···+i
r
=n
in nonnegative integers.
Theorem6.3.5. [r-multiset] The number of r-multisets of elements of [n] is C(n+r-1,n-1).
Proof. Let A be an r-multiset. Let d
i
be the number of copies of i in A. Then, any solution of
d
1
+···+d
n
=r in nonnegative integers gives A uniquely. Hence, the conclusion.
Alternate. Put A ={arrangements of n-1 dots and r bars}. Put B ={r-multisets of [n]}.
For a?A, de?ne f(a) to be the multiset
f(a) ={d(i)+1| where d(i) is the number of dots to the left of the i-th bar}.
For example,||••|•|| gives us{1,1,3,4,4}. Itiseasy tode?neg :B?Asothatf(g(b)) =b,for
eachb?B andg(f(a)) =a,foreacha?A. Thus,bythebijectionprinciple(seeTheorem2.3.8),
|A| =|B|. Also, we know that|A| =C(n+r-1,n-1) and hence the required result follows.
Page 3


6.3 Solutions in Non-negative Integers
De?nition 6.3.1. [Solution in nonnegative integers] Recall that N
0
:= N?{0}. A point
p = (p
1
,...,p
k
)?N
k
0
with p
1
+···+p
k
=n is called a solution of the equation x
1
+···+x
k
=n
in nonnegative integers or a solution of x
1
+··· +x
k
= n in N
0
. Two solutions (p
1
,...,p
k
)
and (q
1
,...,q
k
) are said to be the same if p
i
= q
i
, for each i = 1,...,k. Thus, (5,0,0,5) and
(0,0,5,5) are two di?erent solutions of x+y+z+t = 10 inN
0
.
Example 6.3.2. Determine the number of
1. words which uses 3 A’s and 6 B’s.
2. arrangements of 3 A’s and 6 B’s.
3. distinct strings that can be formed using 3 A’s and 6 B’s.
4. solutions of the equation x
1
+x
2
+x
3
+x
4
= 6, where each x
i
?N
0
and 0=x
i
= 6.
5. ways of placing 6 indistinguishable balls into 4 distinguishable boxes.
6. 3 subsets of an 9-set.
Solution: Observe that all the problems correspond to forming strings using +’s (or|’s
or bars) and 1’s (or balls or dots) in place of A’a and B’s, respectively?
DRAFT
ABBBABABB
ABBBBBAAB
BBABBBABA
+111+1+11 = 0+3+1+2
+11111++1 = 0+5+0+1
11+111+1+ = 2+3+1+0
|• • •| • |• •
|• • • • •|| •
• •|• • •|•|
Figure 6.2: Understanding the three problems
Note that the A’s are indistinguishable among themselves and the same holds for B’s.
Thus, we need to ?nd 3 places, from the 9 = 3+6 places, for the A’s. Hence, the answer
is C(9,3). The answer will remain the same as we just need to replace A’s with +’s (or
|’s) and B’s with 1’s (or balls) in any string of 3 A’s and 6B’s. See Figure 6.2 or note that
four numbers can be added using 3 +’s or four adjacent boxes can be created by putting
3 vertical lines or|’s.
In general, we have the following result.
Theorem 6.3.3. [solutions in N
0
] The number of solutions of x
1
+··· + x
r
= n in N
0
is
C(n+r-1,n).
Proof. Each solution (x
1
,...,x
r
) may be viewed as an arrangement of n dots and r-1 bars.
‘Put x
1
many dots; put a bar; put x
2
many dots; put another bar; continue; and end by
putting x
r
many dots.’
For example, (0,2,1,0,0) is associated to|••|•|| and vice-versa. Thus, there are C(n+r-
1,r-1) arrangements of n dots and r-1 bars.
Theorem 6.3.4. (a) The number of solutions of x
1
+···+x
r
=n in nonnegative integers is
C(n+r,n).
(b) The number of terms in the algebraic expansion of (x
1
+···+x
r
)
n
is C(n+r-1,n).
Proof. (a)Anysolutionofx
1
+···+x
r
=nuniquelycorrespondstoasolutionofx
1
+···+x
r
+y =
n in nonnegative integers..
(b)Notethateachterminthealgebraicexpansionof(x
1
+···+x
r
)
n
hastheformx
i
1
1
x
i
2
2
···x
ir
r
,
withi
1
+i
2
+···+i
r
=n. Thus,eachtermuniquelycorrespondstoasolutionofi
1
+i
2
+···+i
r
=n
in nonnegative integers.
Theorem6.3.5. [r-multiset] The number of r-multisets of elements of [n] is C(n+r-1,n-1).
Proof. Let A be an r-multiset. Let d
i
be the number of copies of i in A. Then, any solution of
d
1
+···+d
n
=r in nonnegative integers gives A uniquely. Hence, the conclusion.
Alternate. Put A ={arrangements of n-1 dots and r bars}. Put B ={r-multisets of [n]}.
For a?A, de?ne f(a) to be the multiset
f(a) ={d(i)+1| where d(i) is the number of dots to the left of the i-th bar}.
For example,||••|•|| gives us{1,1,3,4,4}. Itiseasy tode?neg :B?Asothatf(g(b)) =b,for
eachb?B andg(f(a)) =a,foreacha?A. Thus,bythebijectionprinciple(seeTheorem2.3.8),
|A| =|B|. Also, we know that|A| =C(n+r-1,n-1) and hence the required result follows.
Example 6.3.6. 1. There are 5 kindsof ice-creams available in our market complex. In how
many ways can you buy 15 of them for a party?
Ans: Suppose you buy x
i
ice-creams of the i-th type. Then, the problem is the same as
?nding the number of solutions of x
1
+···+x
5
= 15 in nonnegative integers.
2. How many solutions inN
0
are there to x+y+z = 60 such that x= 3,y= 4,z= 5?
Ans: (x,y,z)issuchasolutionifandonlyif(x-3,y-4,z-5)isasolutiontox+y+z = 48
inN
0
. So, answer is C(50,2).
3. How many solutions in N
0
are there to x+y +z = 60 such that 20= x= 3,30= y=
4,40=z= 5?
Ans: We are looking for solution in N
0
of x+y +z = 48 such that x= 17,y= 26 and
z= 35. Let A ={(x,y,z)?N
3
0
|x+y+z =48}, A
x
={(x,y,z)?N
3
0
|x+y+z = 48,x=
18}, A
y
={(x,y,z)?N
3
0
| x+y+z = 48,y= 27} and A
z
={(x,y,z)?N
3
0
| x+y+z =
48,z= 36}. We know that|A| =C(50,2). Our answer is then C(50,2)-|A
x
?A
y
?A
z
|.
Very soon we will learn to ?nd the value of|A
x
?A
y
?A
z
|.
Page 4


6.3 Solutions in Non-negative Integers
De?nition 6.3.1. [Solution in nonnegative integers] Recall that N
0
:= N?{0}. A point
p = (p
1
,...,p
k
)?N
k
0
with p
1
+···+p
k
=n is called a solution of the equation x
1
+···+x
k
=n
in nonnegative integers or a solution of x
1
+··· +x
k
= n in N
0
. Two solutions (p
1
,...,p
k
)
and (q
1
,...,q
k
) are said to be the same if p
i
= q
i
, for each i = 1,...,k. Thus, (5,0,0,5) and
(0,0,5,5) are two di?erent solutions of x+y+z+t = 10 inN
0
.
Example 6.3.2. Determine the number of
1. words which uses 3 A’s and 6 B’s.
2. arrangements of 3 A’s and 6 B’s.
3. distinct strings that can be formed using 3 A’s and 6 B’s.
4. solutions of the equation x
1
+x
2
+x
3
+x
4
= 6, where each x
i
?N
0
and 0=x
i
= 6.
5. ways of placing 6 indistinguishable balls into 4 distinguishable boxes.
6. 3 subsets of an 9-set.
Solution: Observe that all the problems correspond to forming strings using +’s (or|’s
or bars) and 1’s (or balls or dots) in place of A’a and B’s, respectively?
DRAFT
ABBBABABB
ABBBBBAAB
BBABBBABA
+111+1+11 = 0+3+1+2
+11111++1 = 0+5+0+1
11+111+1+ = 2+3+1+0
|• • •| • |• •
|• • • • •|| •
• •|• • •|•|
Figure 6.2: Understanding the three problems
Note that the A’s are indistinguishable among themselves and the same holds for B’s.
Thus, we need to ?nd 3 places, from the 9 = 3+6 places, for the A’s. Hence, the answer
is C(9,3). The answer will remain the same as we just need to replace A’s with +’s (or
|’s) and B’s with 1’s (or balls) in any string of 3 A’s and 6B’s. See Figure 6.2 or note that
four numbers can be added using 3 +’s or four adjacent boxes can be created by putting
3 vertical lines or|’s.
In general, we have the following result.
Theorem 6.3.3. [solutions in N
0
] The number of solutions of x
1
+··· + x
r
= n in N
0
is
C(n+r-1,n).
Proof. Each solution (x
1
,...,x
r
) may be viewed as an arrangement of n dots and r-1 bars.
‘Put x
1
many dots; put a bar; put x
2
many dots; put another bar; continue; and end by
putting x
r
many dots.’
For example, (0,2,1,0,0) is associated to|••|•|| and vice-versa. Thus, there are C(n+r-
1,r-1) arrangements of n dots and r-1 bars.
Theorem 6.3.4. (a) The number of solutions of x
1
+···+x
r
=n in nonnegative integers is
C(n+r,n).
(b) The number of terms in the algebraic expansion of (x
1
+···+x
r
)
n
is C(n+r-1,n).
Proof. (a)Anysolutionofx
1
+···+x
r
=nuniquelycorrespondstoasolutionofx
1
+···+x
r
+y =
n in nonnegative integers..
(b)Notethateachterminthealgebraicexpansionof(x
1
+···+x
r
)
n
hastheformx
i
1
1
x
i
2
2
···x
ir
r
,
withi
1
+i
2
+···+i
r
=n. Thus,eachtermuniquelycorrespondstoasolutionofi
1
+i
2
+···+i
r
=n
in nonnegative integers.
Theorem6.3.5. [r-multiset] The number of r-multisets of elements of [n] is C(n+r-1,n-1).
Proof. Let A be an r-multiset. Let d
i
be the number of copies of i in A. Then, any solution of
d
1
+···+d
n
=r in nonnegative integers gives A uniquely. Hence, the conclusion.
Alternate. Put A ={arrangements of n-1 dots and r bars}. Put B ={r-multisets of [n]}.
For a?A, de?ne f(a) to be the multiset
f(a) ={d(i)+1| where d(i) is the number of dots to the left of the i-th bar}.
For example,||••|•|| gives us{1,1,3,4,4}. Itiseasy tode?neg :B?Asothatf(g(b)) =b,for
eachb?B andg(f(a)) =a,foreacha?A. Thus,bythebijectionprinciple(seeTheorem2.3.8),
|A| =|B|. Also, we know that|A| =C(n+r-1,n-1) and hence the required result follows.
Example 6.3.6. 1. There are 5 kindsof ice-creams available in our market complex. In how
many ways can you buy 15 of them for a party?
Ans: Suppose you buy x
i
ice-creams of the i-th type. Then, the problem is the same as
?nding the number of solutions of x
1
+···+x
5
= 15 in nonnegative integers.
2. How many solutions inN
0
are there to x+y+z = 60 such that x= 3,y= 4,z= 5?
Ans: (x,y,z)issuchasolutionifandonlyif(x-3,y-4,z-5)isasolutiontox+y+z = 48
inN
0
. So, answer is C(50,2).
3. How many solutions in N
0
are there to x+y +z = 60 such that 20= x= 3,30= y=
4,40=z= 5?
Ans: We are looking for solution in N
0
of x+y +z = 48 such that x= 17,y= 26 and
z= 35. Let A ={(x,y,z)?N
3
0
|x+y+z =48}, A
x
={(x,y,z)?N
3
0
|x+y+z = 48,x=
18}, A
y
={(x,y,z)?N
3
0
| x+y+z = 48,y= 27} and A
z
={(x,y,z)?N
3
0
| x+y+z =
48,z= 36}. We know that|A| =C(50,2). Our answer is then C(50,2)-|A
x
?A
y
?A
z
|.
Very soon we will learn to ?nd the value of|A
x
?A
y
?A
z
|.
6.4 Set Partitions
De?nition 6.4.1. [Set partition] A partition of a set S is a collection of pairwise disjoint
nonempty subsets whose union is S.
Example 6.4.2. (a)

{1,2},{3},{4,5,6}
	
,

{1,3},{2},{4,5,6}
	
and

{1,2,3,4},{5},{6}
	
are
both partitions of [6] into 3 subsets.
(b) There are 2
n-1
-1 partitions of [n], n= 2 into two subsets. To see this, observe that for
each nontrivial subset A?P([n]), the set{A,A
c
} is a partition of [n] into two subsets.
Since, the total number of nontrivial subsets ofP([n]) equals 2
n
-2, the required result
follows.
(c) Number of allocations of 7 students into 7 di?erent project groups so that each group has
one student, is 7! = C(7;1,1,1,1,1,1,1) butthenumberof partitions of a setof 7students
into 7 subsets is 1.
Page 5


6.3 Solutions in Non-negative Integers
De?nition 6.3.1. [Solution in nonnegative integers] Recall that N
0
:= N?{0}. A point
p = (p
1
,...,p
k
)?N
k
0
with p
1
+···+p
k
=n is called a solution of the equation x
1
+···+x
k
=n
in nonnegative integers or a solution of x
1
+··· +x
k
= n in N
0
. Two solutions (p
1
,...,p
k
)
and (q
1
,...,q
k
) are said to be the same if p
i
= q
i
, for each i = 1,...,k. Thus, (5,0,0,5) and
(0,0,5,5) are two di?erent solutions of x+y+z+t = 10 inN
0
.
Example 6.3.2. Determine the number of
1. words which uses 3 A’s and 6 B’s.
2. arrangements of 3 A’s and 6 B’s.
3. distinct strings that can be formed using 3 A’s and 6 B’s.
4. solutions of the equation x
1
+x
2
+x
3
+x
4
= 6, where each x
i
?N
0
and 0=x
i
= 6.
5. ways of placing 6 indistinguishable balls into 4 distinguishable boxes.
6. 3 subsets of an 9-set.
Solution: Observe that all the problems correspond to forming strings using +’s (or|’s
or bars) and 1’s (or balls or dots) in place of A’a and B’s, respectively?
DRAFT
ABBBABABB
ABBBBBAAB
BBABBBABA
+111+1+11 = 0+3+1+2
+11111++1 = 0+5+0+1
11+111+1+ = 2+3+1+0
|• • •| • |• •
|• • • • •|| •
• •|• • •|•|
Figure 6.2: Understanding the three problems
Note that the A’s are indistinguishable among themselves and the same holds for B’s.
Thus, we need to ?nd 3 places, from the 9 = 3+6 places, for the A’s. Hence, the answer
is C(9,3). The answer will remain the same as we just need to replace A’s with +’s (or
|’s) and B’s with 1’s (or balls) in any string of 3 A’s and 6B’s. See Figure 6.2 or note that
four numbers can be added using 3 +’s or four adjacent boxes can be created by putting
3 vertical lines or|’s.
In general, we have the following result.
Theorem 6.3.3. [solutions in N
0
] The number of solutions of x
1
+··· + x
r
= n in N
0
is
C(n+r-1,n).
Proof. Each solution (x
1
,...,x
r
) may be viewed as an arrangement of n dots and r-1 bars.
‘Put x
1
many dots; put a bar; put x
2
many dots; put another bar; continue; and end by
putting x
r
many dots.’
For example, (0,2,1,0,0) is associated to|••|•|| and vice-versa. Thus, there are C(n+r-
1,r-1) arrangements of n dots and r-1 bars.
Theorem 6.3.4. (a) The number of solutions of x
1
+···+x
r
=n in nonnegative integers is
C(n+r,n).
(b) The number of terms in the algebraic expansion of (x
1
+···+x
r
)
n
is C(n+r-1,n).
Proof. (a)Anysolutionofx
1
+···+x
r
=nuniquelycorrespondstoasolutionofx
1
+···+x
r
+y =
n in nonnegative integers..
(b)Notethateachterminthealgebraicexpansionof(x
1
+···+x
r
)
n
hastheformx
i
1
1
x
i
2
2
···x
ir
r
,
withi
1
+i
2
+···+i
r
=n. Thus,eachtermuniquelycorrespondstoasolutionofi
1
+i
2
+···+i
r
=n
in nonnegative integers.
Theorem6.3.5. [r-multiset] The number of r-multisets of elements of [n] is C(n+r-1,n-1).
Proof. Let A be an r-multiset. Let d
i
be the number of copies of i in A. Then, any solution of
d
1
+···+d
n
=r in nonnegative integers gives A uniquely. Hence, the conclusion.
Alternate. Put A ={arrangements of n-1 dots and r bars}. Put B ={r-multisets of [n]}.
For a?A, de?ne f(a) to be the multiset
f(a) ={d(i)+1| where d(i) is the number of dots to the left of the i-th bar}.
For example,||••|•|| gives us{1,1,3,4,4}. Itiseasy tode?neg :B?Asothatf(g(b)) =b,for
eachb?B andg(f(a)) =a,foreacha?A. Thus,bythebijectionprinciple(seeTheorem2.3.8),
|A| =|B|. Also, we know that|A| =C(n+r-1,n-1) and hence the required result follows.
Example 6.3.6. 1. There are 5 kindsof ice-creams available in our market complex. In how
many ways can you buy 15 of them for a party?
Ans: Suppose you buy x
i
ice-creams of the i-th type. Then, the problem is the same as
?nding the number of solutions of x
1
+···+x
5
= 15 in nonnegative integers.
2. How many solutions inN
0
are there to x+y+z = 60 such that x= 3,y= 4,z= 5?
Ans: (x,y,z)issuchasolutionifandonlyif(x-3,y-4,z-5)isasolutiontox+y+z = 48
inN
0
. So, answer is C(50,2).
3. How many solutions in N
0
are there to x+y +z = 60 such that 20= x= 3,30= y=
4,40=z= 5?
Ans: We are looking for solution in N
0
of x+y +z = 48 such that x= 17,y= 26 and
z= 35. Let A ={(x,y,z)?N
3
0
|x+y+z =48}, A
x
={(x,y,z)?N
3
0
|x+y+z = 48,x=
18}, A
y
={(x,y,z)?N
3
0
| x+y+z = 48,y= 27} and A
z
={(x,y,z)?N
3
0
| x+y+z =
48,z= 36}. We know that|A| =C(50,2). Our answer is then C(50,2)-|A
x
?A
y
?A
z
|.
Very soon we will learn to ?nd the value of|A
x
?A
y
?A
z
|.
6.4 Set Partitions
De?nition 6.4.1. [Set partition] A partition of a set S is a collection of pairwise disjoint
nonempty subsets whose union is S.
Example 6.4.2. (a)

{1,2},{3},{4,5,6}
	
,

{1,3},{2},{4,5,6}
	
and

{1,2,3,4},{5},{6}
	
are
both partitions of [6] into 3 subsets.
(b) There are 2
n-1
-1 partitions of [n], n= 2 into two subsets. To see this, observe that for
each nontrivial subset A?P([n]), the set{A,A
c
} is a partition of [n] into two subsets.
Since, the total number of nontrivial subsets ofP([n]) equals 2
n
-2, the required result
follows.
(c) Number of allocations of 7 students into 7 di?erent project groups so that each group has
one student, is 7! = C(7;1,1,1,1,1,1,1) butthenumberof partitions of a setof 7students
into 7 subsets is 1.
DRAFT
(d) In how many ways can I write
n
{1,2},{3,4},{5,6},{7,8,9},{10,11,12}
o
on a piece of
paper, with the condition that sets have to be written in a row in increasing size?
Ans: Let us write a few ?rst.
n
{1,2},{3,4},{5,6},{7,8,9},{10,11,12}
o
correct
n
{2,1},{3,4},{5,6},{7,8,9},{10,11,12}
o
correct
n
{5,6},{3,4},{1,2},{10,11,12},{9,7,8}
o
correct
n
{2,3},{1,4},{5,6},{7,8,9},{10,11,12}
o
incorrect, not the same partition
n
{2,1},{3,4},{7,8,9},{5,6},{10,11,12}
o
incorrect, not satisfying the condition
There are 3!(2!)
3
×2!(3!)
2
ways. Notice that from each written partition, if I remove the
brackets I get an arrangement of elements of [12].
(e) How many arrangements do I generate from a partition with p
i
subsets of size n
i
, n
1
<
··· <n
k
?
Ans: p
1
!(n
1
!)
p
1
···p
k
!(n
k
!)
p
k
=
k
Y
i=1
[p
i
!(n
i
)
p
i
].
Theorem 6.4.3. [Set partition] The number of partitions of [n] with p
i
subsets of size n
i
,
n
1
<··· <n
k
is
n!
(n
1
!)
p
1
p
1
!···(n
k
!)
p
k
p
k
!
.
Proof. Note that each such partition generates
k
Q
i=1
[p
i
!(n
i
)
p
i
] arrangement of elements of [n].
Conversely, for each arrangement of elements of [n] we can easily construct a partition of the
above type which can generate this arrangement. Thus, the proof is complete.
De?nition 6.4.4. Stirling numbers of the second kind, denotedS(n,r), is the number of
partitions of [n] into r-subsets (r-parts). By convention, S(n,r) = 1, if n = r and 0, whenever
either ‘n> 0 and r = 0’ or ‘n<r’.
Theorem 6.4.5. [recurrence for S(n,r)] S(n+1,r) =S(n,r-1)+rS(n,r).
Proof. Write an r-partition of [n+1] and erase n+1 from it. That is, if{n+1} is an element
of an r-partition, then the number of such partitions become S(n,r-1); else n+1 appears in
one of the element of an r-partition of [n], which gives the number rS(n,r).
Example 6.4.6. Determine the number of ways of putting n distinguishable/distinct balls into
r indistinguishable boxes with the restriction that no box is empty.
Ans: Let A be the set of n distinct balls and let the balls in i-th box be B
i
, 1=i=r.
1. Since each box is non-empty, each B
i
is non-empty.
2. Also, each ball is in some box and hence
r
S
i=1
B
i
=A.