南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Basic Enumeration（主讲：尹一通）

Basic Enumeration

Basic Enumeration

Enumeration (counting) Sample questions: How many character strings of length n? How many trees of n vertices? How many ways of returning homeworks to n students so that no one receives his/her own homework. How many ways to change n yuan? f(n)=Sn

Enumeration (counting) • How many character strings of length ? • How many trees of vertices? • How many ways of returning homeworks to students so that no one receives his/her own homework. • How many ways to change yuan? Sample questions: n n n n n f(n) = |Sn|

Tuples {1,2,,m} [m]=9,1,m-1} TTNOE MATCH [mn=m×…×m JO C SS m Im=mr Product rule: finite sets S and T S×T=S1·T

Tuples mn |[m] n| = Product rule: |S ⇥ T| = |S|·|T| finite sets S and T [m] ⇥ ··· ⇥ [m] ⇤ ⇥￾ ⌅ n [m] n = [m] = {0, 1,...,m ￾ 1} {1, 2,...,m}

Functions count the of functions f:[ml→[m [n] [m] (f(1),f(2),.,f(n)∈[m]n one-one correspondence [ml→[ml今[m

Functions [n] [m] f : [n] ￾ [m] count the # of functions ￾ [m] n one-one correspondence [n] ￾ [m] ⇥ [m] n (f(1), f(2),...,f(n))

Functions count the of functions f:[nl→[m one-one correspondence [n] [m] [nl→[ml台[mln Bijection rule: finite sets S and T 0:S1-1T →S=T on-to

Functions [n] [m] f : [n] ￾ [m] count the # of functions one-one correspondence [n] ￾ [m] ⇥ [m] n Bijection rule: finite sets S and T ⇤￾ : S 1￾1 ￾￾￾￾⇥ on￾to T =￾ |S| = |T|

Functions count the of functions f:[m→[m X one-one correspondence [n] [m] [m]→[m]台[m]n l[m→[m=lmlm|=mm "Combinatorial proof

Functions [n] [m] f : [n] ￾ [m] count the # of functions one-one correspondence [n] ￾ [m] ⇥ [m] n |[n] ￾ [m]| = |[m] n| = mn “Combinatorial proof

Injections count the of 1-1 functions f (n(m] one-one correspondence [n] [m] π=(f(1),f(2),.,f(n) n-permutation::元∈[m]of distinct elements m! (m)m=m(m-1).(m-n+1)= (m-n)！ “m lower factorial n

Injections [n] [m] count the # of 1-1 functions one-one correspondence ￾ ￾ [m] n of distinct elements ￾ = (f(1), f(2),...,f(n)) n-permutation: = m! (m ￾ n)! (m)n = m(m ￾ 1)···(m ￾ n + 1) “m lower factorial n” f : [n] 1-1 ￾￾ [m]

Subsets S={1,2,3} subsets of S: ☑， {I,2,{3}, {1,2,{1,3},{2,3, {1,2,3} S={1,c2,,xn} Power set:25-{TT S) 121=

Subsets S = { 1, 2, 3 } subsets of S: ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} S = {x1, x2,...,xn} Power set: ￾ ￾2S￾ ￾ = 2S = {T | T ￾ S}

Subsets S={c1,c2,,xn} Power set:25 ={T TCS) 121= Combinatorial proof: A subset TS corresponds to a string of n bit, where bit i indicates whether xiET

Subsets S = {x1, x2,...,xn} Power set: ￾ ￾2S￾ ￾ = Combinatorial proof: A subset T ￾ S corresponds to a string of n bit, where bit i indicates whether xi ⇥ T. 2S = {T | T ￾ S}

Subsets S={x1,c2,.,xn} Power set:25 ={TT C S} |2=I{0,1}m1=2m Combinatorial proof: -日 c∈T φ：2s→{0,1}n ,庄T is 1-1 correspondence

Subsets S = {x1, x2,...,xn} Power set: ￾ ￾2S￾ ￾ = Combinatorial proof: ￾ : 2S ￾ {0, 1}n ￾(T)i = ￾ 1 xi ￾ T 0 xi ⇥￾ T ￾ is 1-1 correspondence |{0, 1}n| = 2n 2S = {T | T ￾ S}