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 11 ⇥ onto 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]}