Combinatorics combinatoriala≈ iscrete solution:combinatorial object 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 Enumerative Combinatorics RICHARD P.STANLEY Stanley, Enumerative Combinatorics, Gian-Carlo Rota Volume I (1932-1999)
Gian-Carlo Rota (1932-1999) The Twelvefold Way Stanley, Enumerative Combinatorics, Volume 1
The twelvefold way f:N→M |N|=n,|M=m elements elements any f 1-1 on-to of N 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 n identical balls, m distinct bins n distinct balls, m identical bins n identical balls, m identical bins
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 Knuth’s version (in TAOCP vol.4A) n balls are put into m bins