《离散数学》杨争锋ch07-139页

Solution:
See blackboard or book.
ersion of the Product Rule
Suppose that a procedure is carried out
by performing the tasks T1, T2, …, Tm in sequence. If task Ti can be done in ni ways after tasks T1, T2, …, and Ti-1 have been done, then there are n1×n2×…×nm ways to carry out the procedure.
seeblackboardexample18page309playoff双方得分相同时的最后决赛betweentwoteamsconsistsmostfivegames
Chapter 4 Counting (计数)
§4.1 The Basics of Counting §4.2 The Pigeonhole Principle §4.3 Permutations and Combinations §4.4 Binomial Coefficients §4.5 Generalized Permutations and
these sets is the sum of the numbers of
elements in them.
|A1 ∪ A2 ∪ … ∪ An|= |A1| + |A2| + … + |Am|
2021/6/18
18
3. More Complex Counting Problems Remark (备注):
(b) How many different license plate are available if each plate contains a sequence of three letters followed by three digits (and no sequences of letters are prohibited, even if they are obscene)

complement of the set A, denoted by ~A, is the complement of A with respect to U.
~A = U-A
~A = { x | x notin A}
Please explain it via Venn Diagram.
精选课件ppt
精选课件ppt
4
(5) Definition 4 (the difference of two sets, 差集)
Let A and B be sets. The difference of A and B, denoted by A-B, is the set that containing those elements that are in A but not in B.
Proof: See page 125
精选课件ppt
10
(4) Example 12 (page 125) Prove that A∩(B∪C) = (A∩B)∪(A∩C) for all sets A, B, C.
Proof See book.
精选课件ppt
11
(4) Use a membership table to show that A∩(B∪C) = (A∩B)∪(A∩C)
Example 5 (page 87) Let A={1,3,5,7,9} and B={2,4,6,8,10}.
Since A∩B=∅ , A and B are disjoint.
精选课件ppt
3
(5) For two finite sets A and B, we have: |A∪B| = |A|+|B|-| A∩B | Please explain it via Venn Diagram.

(6) Example 11 (page 35) P(x)------” x2<10 ” universe discourse
----”the positive integers not exceeding 4” {1,2,3,4}
How about ∀x P(x) ? Solution:
∀x P(x) is the same as P(1) /\ P(2) /\ P(3) /\ P(4) --------false Example 12 N(x): Computer x is connected to the network. The domain consists of all computer on campus.
(3) “There exists an element x in the universe of discourse such that P(x) is true”
(4) --------denoted as ∃x P(x) (5) “There is an x such that P(x)” (6) “There is at least one x such that
universe of discourse------all real numbers
How about ∀x Q(x) ? Answer: ∀x Q(x) ------false
(5) Further explanation universe of discourse -----finite set {x1,x2,…,xn} ∀x P(x) is the same as P(x1) /\ P(x2) /\ ...... /\ P(xn)
(3) Example 8 (page 34) P(x)-----”x+1>x”

2021/6/18
3
(3) Example (page 328) (a) Example 2 What is the expansion of (x+y)4?
Solution: (x+y)4
= ∑j=0 n C(4,j) x4-j yj = C(4,0)x4 + C(4,1)x3y + C(4,2)x2y2
C(m+n, r) = ∑k=0r C(m, r-k) C(n,k) 这就证明了范德蒙德恒等式
2021/6/18
15
(2) Corollary 4 If n is a nonnegative integer. Then
C(2n, n) = ∑k=0n C(n,k) 2
Proof: 我们使用范德蒙德恒等式且m=r=n： C(2n, n)
n≥k. Then
C(n+1,k) = C(n,k-1) + C(n,k)
Proof:
假设T是一个含有n+1个元素的集合，令a是T中 的一个元素，且S=T-{a}。注意到T的包含k个元 素的子集有C(n+1,k)个。然而T的含k个元素的子 集或者包含a和S中的k-1个元素，或者不包含a但 包含S中的k个元素。由于S的k-1元素子集有 C(n,k-1)个，故T含a在内的k元素子集有C(n,k-1) 个。又由于S的k元素子集有C(n,k)个，故T的不 含a的k元子集有C(n,k)个。从而可得：
∑k=0 n C(n,k) 2k = 3n
Proof: (1+2)n
= ∑k=0 n C(n,k) 1n-k 2k = ∑k=0 n C(n,k) 2k
2021/6/18
10
2. Pascal’s Identity and Triangle