# 《离散数学》杨争锋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)

2019《离散数学》杨争锋ch04-4.ppt_图文.ppt
2019《离散数学》杨争锋ch04-4.ppt - §4.4 Binomial
2019《离散数学》杨争锋ch04-2.ppt_图文.ppt
2019《离散数学》杨争锋ch04-2.ppt - §4.2 The Pigeo
《离散数学》杨争锋ch02-4_图文.ppt
《离散数学》杨争锋ch02-4 - §2.4 Cardinality(基数) (
《离散数学》杨争锋ch01-1-精选文档_图文.ppt
《离散数学》杨争锋ch01-1-精选文档 - Chapter 1 The Fou
2019《离散数学》杨争锋ch06-5.ppt_图文.ppt
2019《离散数学》杨争锋ch06-5.ppt - §7.5 Inclusion
《离散数学》杨争锋ch4-5_图文.ppt
《离散数学》杨争锋ch4-5 - §4.5 Generalized Permut
2019《离散数学》杨争锋ch06-1.ppt_图文.ppt
2019《离散数学》杨争锋ch06-1.ppt - §7.1 Recurrenc
2019《离散数学》杨争锋ch2-2.ppt.ppt
2019《离散数学》杨争锋ch2-2.ppt - §2.2 Set Operat
《离散数学》杨争锋ch01-2.ppt
《离散数学》杨争锋ch01-2 - §1.3 Predicates (谓词) a

ch01_图文.ppt
1.3 鼠标和键盘操作鼠标和键盘作为电脑最基本的输入和控制设备,方便了用户操控电脑...《离散数学》杨争锋ch01... 暂无评价 28页 20.00 ch01建立数学模型...
2019《离散数学》杨争锋ch01-1.ppt_图文.ppt
2019《离散数学》杨争锋ch01-1.ppt - Chapter 1 The