# 《离散数学》杨争锋ch04-3_图文

§4.3 Permutations and Combinations 1. Introduction Example 0 (page 320~321) Please see book.

2. Permutations (排列) (1) Definition (page 321) A permutation of a set of distinct objects is an ordered arrangements of these objects. An ordered arrangement of r elements of a set is called an r-permutation. (2) Example 1 Let S={1,2,3}. The arrangement 3,1,2 is a permutation of S. The arrangement 3,2 is a 2-permutation of S.

(3) Theorem 1 The number of r-permutations of a set with n distinct elements is P(n,r) = n(n-1)(n-2)…(n-r+1) Proof See blackboard or book. We can also have: P(n,r) = n! / (n-r)!

(4) Examples (a) Example 2 and 3 (page 321) Please read them by yourself.

(b) Suppose that a saleswoman has to visit

eight different cities. She must begin her trip in a specified city, but she can visit the other seven cities in any order she wishes. How many possible orders can the saleswoman use when visiting these cities? Solution: 7!

(c) Example 5 (page 322) How many permutations of the letters ABCDEFGH contains the string ABC? Solution:

6!

Way: six objects ------the block ABC and the individual D,E,F,G, and H

3. Combinations (组合) (1) Definition (page 322) An r-combination of elements of a set is an unordered selection of r elements from the set. (2) Examples (a) Example 6 (page 322) Let S be the set {1,2,3,4}. Then {1,3,4} is a 3-combination from S. (b) Example 7 ----Please read it by yourself.

(3) Theorem 2 (page 322) The number of r-combinations of a set with n elements, where n is a nonnegative integer and r is an integer with 0≤r≤n, equals C(n,r) = n! / (r!(n-r)!) Proof: Step1: First we can get P(n,r) = C(n,r) × P(r,r) Step 2: Then we can get our result.

Corollary 1 Let n and r be nonnegative integers with r≤n.

Then C(n,r) = C(n,n-r)

(4) Examples (a) Example 8 and 9 (page 324) Please read them by yourself. (b) Example 10 How many bit strings of length n contain exactly r 1s? Solution: See blackboard or book.

(c) Example 11 (page 324)

How many ways are there to select a committee to develop a discrete mathematics course at a school if the committee is to consist of three faculty members from the mathematics department and four from the computer science department, if there are nine faculty members of the mathematics department and 11 of the computer science department? Solution: C(9,3)× C(11,4)

Exercises

? 20、22、26 (Fifth and Sixth Edition)