Transcript A 1 ∪A 2 ∪…∪A n |=|A 1 |+|A 2 |+…+|A n

4.2 Permutations of sets
4.2.1
Basic counting principles
4.3(Addition principle): If A1, A2, … ,
An are disjoint sets, then the number of
elements in the union of these sets is the sum
of the numbers of elements in them.
 | A1∪A2∪…∪An |=|A1|+|A2|+…+|An|
 Theorem
 Example1:
A student wishes to take either a
mathematics course or biology course, but not
both. If there are 4 mathematics course and 2
biology course for which the student has the
necessary prerequisites, then the student can
choose a course to take in 4+2=6 ways.
 Theorem 4.4(Multiplication principle): Let A
and B be two finite sets. Let |A|=p and |B|=q,
then |A×B|=p×q.
 Example2: A student
wishes to take a
mathematics course and a biology course. If
there are 4 mathematics course and 2 biology
course for which the student has the
necessary prerequisites, then the student can
choose courses to take in 4×2=8 ways.
4.2.2 Permutations of sets
 An
ordered arrangement of r elements of an
n-element set is called an r-permutation.
 We denote by p(n,r) the number of rpermutations of an n-element set. If r>n, then
p(n,r)=0. An n-permutation of an n-element
set S is called a permutation of S. A
permutation of a set S is a listing of the
elements of S in some order.
Theorem 4.5: For n and r positive integers with rn,
 p(n,r)=n(n-1)…(n-r+1)
 Proof:In constructing an r-permutation of an nelement set, we can choose the first item in n ways,
the second item in n-1 ways whatever choice of the
first item,… , and the rth item in n-(r-1) ways
whatever choice of the first r-1 items. By the
multiplication principle the r items can be chosen in
n(n-1)…(n-r+1) ways.
 We define n! by
 n!= n(n-1)…2•1
 with the convention that 0!=1.Thus p(n,r)=n!/(n-r)!.

Example:What is the number of ways to order the
26 letters of the alphabet so that no two of the
vowels a,e,i,o,and u occur consecutively?(元音字母
中任意两个都不得相继出现)
 Solution:The first task is to decide how to order the
consonants among themselves.
 21!
 Our second task is put the vowels in these places.
 p(22,5)=22!/17!
 By the multiplication principle, the numble of
ordered arrangements of the letters of the alphabet
with no two vowels consecutive is 21!22!/17! .

 Example:
What is the number of ways to
order the 26 letters of the alphabet so that it
contains exactly seven letters between a and b?
 a…….b，P(24,7)
 b…….a，P(24,7)
 between a and b
2P(24,7)
 P(18,18)=18!.
 2P(24,7)18!
 linar permutation
 circular permutation
linar permutation
 circular permutation

 linar
permutation 12345
 linar permutation 45123
 circular permutation
For example, the circular permutation
 arises
from each of the linear
permutation
 12345 23451 34512 45123 51234




Theorem 4.6: The number of circular rpermutations of a set of n elements is given
by p(n,r)/r=n!/r(n-r)! . In particular,the
number of circular permutations of n
elements is (n-1)! .
Proof: The set of linear r-permutations can
be partitioned into parts in such a way that
two linear r-permutations are in the same
part if only if they correspond to the same
circular r-permutations .
Thus the number of circular r-permutations
equals the number of parts.
Since each part contains r linear rpermutations, the number of parts is the
number p(n,r) of linear r-permutations
divided by r.
 Example:
Ten people, including two who do
not wish to sit next to one another, are to be
seated at a round table. How many circular
seating arrangements are there?
4.3 Combinations of sets
 4.3.1
Combinations of sets
 Definition:
Let r be a non-negative integer. An
r-combination of a set S is an r-element subset
of S. We denote by nCr, or C(n,r), or
n
 
r
 Example:
Let S={a,b,c,d}, then {a,b,c}, {a,b,d},
{a,c,d}, {b,c,d} are the 3-combinations of S.
 Note that these are subsets, not sequences.
 Therefore,
{a,b,c}={a,c,b}={b,a,c}={b,c,a}={c,a,b}
={c,b,a}.
 If r>n, then C(n,r)=0. Also C(0,r)=0 if r>0.
Obviously
 C(n,0)=1, C(n,1)=n, C(n,n)=1.
Theorem 4.7: For 0rn, C(n,r)=p(n,r)/r! and hence
C(n,r)=n!/r!(n-r)!.
 Proof: Let S be an n-element set.
 Each r-permutation of S arises in exactly one way as
a result of carrying out the following two tasks.
 (1)Choose r elements from S. C(n,r)
 (2)Arrange the chosen r elements in some order. r!
 By the multiplication principle we have
p(n,r)=r!C(n,r). Thus C(n,r)=p(n,r)/r!. We now use
the formula p(n,r)=n!/(n-r)! and obtain
C(n,r)=n!/r!(n-r)!.

Corollary 4.1: For 0rn, C(n,r)=C(n,n-r).
 Proof: C(n,r)=n!/(r!(n-r)!)=n!/((n-(n-r))!(nr)!)=C(n,n-r).
 Example: How many different seven-person
committees can be formed each containing three
women from an available set of 20 women and four
men from an available set of 30 men?
 Task1: Choose three women from the set of 20
women. C(20,3)
 Task2: Choose four men from an the set of 30 men.
C(30,4)
 By the multiplication principle,there are
C(20,3)C(30,4).

 4.3.2 The
Binomial Coefficients and Identities
 The number C(n,r) have many important and
fascinating properties.
 C(n,r) is also called a binomial coefficient
because these numbers occur as coefficients in
the expansion of powers of binomial
expressions such as (a+b)n.
 Theorem 4.8(Binomial theorem): Let x and y
be variables, and let n be a nonnegative
n
integer. Then
( x  y ) n   C ( n, k ) x k y n  k
k 0
 Corollary
4.2: Let n be a nonnegative integer.
Then
 C(n,0)+C(n,1)+…+C(n,n)=2n
 Proof：Let x=y=1, by the Binomial theorem it
follows that
 Corollary
4.3:Let n be a positive integer. Then
 C(n,0)-C(n,1)+C(n,2)-…+ (-1)nC(n,n)=0
 Proof：Let x=-1, and y=1, by the Binomial
theorem it follows that C(n,0)-C(n,1)+C(n,2)…+ (-1)nC(n,n)=0
 Remark: Corollary 4.3 implies that
 C(n,0)+C(n,2)+ …=C(n,1)+C(n,3)+ …

Theorem 4.9: Let m,n,r, and k be nonnegative integer. Then
(1)C (n, k ) 
n
C (n  1, k  1)
k
(2)C(n,k)=C(n-1,k)+C(n-1,k-1)(杨辉公式，Pascal’s formula)；
n
(3)  kC (n, k ) 
n 2n 1
k 1
n
(4)  k 2C (n, k )  n(n  1)2n  2
k 1
(5)C(n,r)C(r,k)=C(n,k)C(n-k,r-k), where rk；
(6)C(m,0)C(n,r)+C(m,1)C(n,r-1)++C(m,r)C(n,0)=C(m+n,r)，
where rmin{m,n} (Vandermonde identity)；
(7)C(m,0)C(n,0)+C(m,1)C(n,1)++C(m,m)C(n,m)=C(m+n,m)where
n
mn。When m=n，
2
 C ( n, k )
k 0
m
(8) C (n  k , k )  C (n  m  1, m)
k 0
 C ( 2 n, n )
4.4 Permutations and Combinations of multisets
Multisets :A multiset is a set in which an item may
appear more than once. .
 Sets and multisets are quite similar: both support
the basic set operations of union, intersection, and
difference.
 item ai
ni，
 {n1•a1,n2•a2,…,nk•ak}
 Example：{a,a,a,a,b,b,c}
 {4•a,2•b,1•c}
 {•a1,•a2,…,•ak}

 4.4.1
 If
Permutations of multisets
S is a multiset, a r-permutation of S is an
ordered arrangement of r of the objects of S.
If the total number of objects of S is n，then a
n-permutation of S will also be called a
permutation of S.
 For example, if S={2•a,1•b,3•c}, then
 aacb acbc cacc are 4-permutations of S,
 “abccac” is a permutation of S.
 The multiset S has no 7-permutations since
7>2+1+3=6, the number of objects of S.
Theorem 4.10: Let S be a multiset with objects of k
different types where each has an infinite repetition
number. Then the number of r-permutations of S is
kr.
 Proof: In constructing a r-permutation of S,
 we can choose the first item can be an object of any
one of the k types.
 Similarly the second item to be an object of any one
of the k types, and so on.
 Since all repetition numbers of S are infinite, the
number of different choices for any item is always k
and does not depend on the choices of any previous
items.
 By the multiplication principle, the r items can be
chose in kr ways.

4.4: Let S={n1•a1,n2•a2,…,nk•ak}，
and ni r for each i=1,2,…,n，then the
number of r-permutations of S is kr.
 Corollary
 Theorem
4.11: Let multiset
S={n1•a1,n2•a2,…,nk•ak}, and
n=n1+n2+…+nk=|S|. Then the number of
permutations of S equals n!/(n1!n2!…nk!)。
 Proof: We can think of it this way. There are n
places, and we want to put exactly one of the
objects of S in each of the places.
 Since there are n1 a1’s in S, we must choose a
subset of n1 places from the set of n places.
 C(n,n1)
 We next decided which places are to be
occupied by the a2’.
 Example
What is the number of
permutations of the letters in the word
Mississippi?
S={n1•a1,n2•a2,…,nk•ak}, and
n=n1+n2+…+nk=|S|，then the number N of rpermutations of S equals
 (1)0
r>n
 (2)n!/(n1!n2!…nk!)
r=n
 (3)kr
ni r for each i=1,2,…,n
 (4)If r<n, there is, in general, no simple
formula for the number of r-permutations of
S.
 Nonetheless a solution can be obtained by the
technique of generating functions, and we
discuss this in 4.6 .
 Let
 Combinations
of multisets P85-86 3.2
 Inclusion-Exclusion principle and
Applications
 Exercise P83
17, 19,22,33; P86 4,5,6,8
1.In how many ways can six men and six ladies be
seated round table if the men and ladies are to sit
in alternate seats?
 2.In how many ways can 15 people be seated at a
round table if B refuse to sit next to A?What if B
only refuses to sit on A’s right?

3.Prove Theorem 4.9 (4)(7).
 4. How many ways are there to assign three jobs to
five employees if each employee can be given more
than one job?
 5.A book publisher has 3000 copies of a discrete
mathematics book . How many ways are there to store
these books in there three warehouses if the copies of
the book are indistinguishable?
