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

Combinatorics discrete solution:combinatorial object combinatorial≈ finite constraint:combinatorial structure Enumeration (counting): How many solutions satisfying the constraints? Existence: Does there exist a solution? Extrema: How large/small a solution can be to preserve/avoid certain structure? Ramsey: When a solution is sufficiently large, some structure must emerge. ●Optimization: Find the optimal solution. Construction (design): Construct a solution

Combinatorics • Enumeration (counting): • Existence: • Extremal: • Ramsey: • Optimization: • Construction (design): How many solutions satisfying the constraints? Does there exist a solution? When a solution is sufficiently large, some structure must emerge. How large/small a solution can be to preserve/avoid certain structure? Find the optimal solution. Construct a solution. solution: combinatorial object constraint: combinatorial structure combinatorial≈ discrete finite

Enumeration (counting) How many ways are there: ●to rank n people? ● to assign m zodiac signs to n people? ● to choose m people out of n people? to partition n people into m groups? to distribute m yuan to n people? to partition m yuan to n parts? ●

Enumeration (counting) • to rank n people? • to assign m zodiac signs to n people? • to choose m people out of n people? • to partition n people into m groups? • to distribute m yuan to n people? • to partition m yuan to n parts? • ... ... How many ways are there:

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

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

The twelvefold way f:N→M NI =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,士，r,m1y TTNOE MATCH [mlm=m×…xm JOC SS m I(m"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 In] [m] (f(1),f(2),.,f(n)∈[m]m one-one correspondence [nl→[ml台[mm

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:[m→[m one-one correspondence [n] [m] [ml→[ml台[m]" Bijection rule: finite sets S and T 6: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 one-one correspondence In] [m] [ml→[ml台[m]" l[n]→[ml=l[m]|=mn "Combinatorial proof

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

Injections count the of 1-1 functions f:[ml马[ml one-to-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 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] [n] [m]