南京大学：《组合数学》课程教学资源（课堂讲义）基本计数 Basic enumeration

The Twelyefold Way Gian-Carlo Rota (1932-1999)

Gian-Carlo Rota (1932-1999) The Twelvefold Way

The twelvefold way f:N→M N =n,M=m elements elements of N anyf 1-1 on-to of M distinct distinct identical distinct distinct identical identical identical

The twelvefold way f : N ￾ M |N| = n, |M| = m elements of N elements of M any f 1-1 on-to distinct distinct identical distinct distinct identical identical identical

Knuth's version (in TAOCP vol.4A) n balls are put into m bins balls per bin: unrestricted ≤1 ≥1 n distinct balls, m distinct bins mn n identical balls, m distinct bins n distinct balls, m identical bins n identical balls, m identical bins

Knuth’s version (in TAOCP vol.4A) balls per bin: unrestricted ≤ 1 ≥ 1 n distinct balls, m distinct bins n identical balls, m distinct bins n distinct balls, m identical bins n identical balls, m identical bins n balls are put into m bins mn

Tuples {1,2,..,m} [m]=0,1,-1} TTNOE MATCH [mn=m××m I(mj"mr Product rule: finite sets S and T |S×T=|S1·lTI

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),.,(n)∈[m]n one-one correspondence [n→[m台[m]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:[ml→[m] one-one correspondence [n] [m] [nl→[ml台[m" Bijection rule: finite sets S and T 0:S1-1T →S1=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:[nl→[m one-one correspondence [n] [m] [ml→[m]÷[m" l[m→[mll=l[mr|=m “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 (nml one-to-one correspondence [n] [m] π=（f(1),f(2),.,f(n)》 n-permutation:E[m]of distinct elements (m)n=m(m-1)(m-n+1）= m! (m-n)！ “m lower factorial n

Injections [n] [m] count the # of 1-1 functions one-to-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 subsets of {1,2,3 } ☑， {I,{2},3}, {1,2},{1,3},{2,3} {1,2,3} [m={1,2,..,n} Power set:2Im={SS [n]} 2=

Subsets subsets of { 1, 2, 3 }: ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} Power set: [n] = {1, 2,...,n} ￾ ￾ ￾ 2[n] ￾ ￾ ￾ = 2[n] = {S | S ✓ [n]}

Subsets [ml={1,2,..,n} Power set:2rl ={SSC [n]} 2= Combinatorial proof: A subset S [n]corresponds to a string of n bit, where bit i indicates whether ie S

Subsets Combinatorial proof: Power set: [n] = {1, 2,...,n} ￾ ￾ ￾ 2[n] ￾ ￾ ￾ = A subset S ✓ [n] corresponds to a string of n bit, where bit i indicates whether i 2 S. 2[n] = {S | S ✓ [n]}