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
Counting (labeled)trees 八八八 "How many different trees 8 can be formed from n distinct vertices?" 9 6 及又品人
Counting (labeled) trees “How many different trees can be formed from n distinct vertices?
Cayley's formula: There are n"-2 trees on n distinct vertices. 0 33g 99 及又又人 Arthur Cayley (1821-1895)
Cayley’s formula for the number of trees Chapter 30 Arthur Cayley One of the most beautiful formulas in enumerative combinatorics concerns the number of labeled trees. Consider the set N = {1, 2,...,n}. How many different trees can we form on this vertex set? Let us denote this number by Tn. Enumeration “by hand” yields T1 = 1, T2 = 1, T3 = 3, T4 = 16, with the trees shown in the following table: 434 34 34 343434 3 4 3434 34 34 343434 3 4 1 1 12 12 2 1 2 1212 12 1 1 2 3 2 21212 1212 12 12 121212 1 2 1 3 3 3 Note that we consider labeled trees, that is, although there is only one tree of order 3 in the sense of graph isomorphism, there are 3 different labeled trees obtained by marking the inner vertex 1, 2 or 3. For n = 5 there are three non-isomorphic trees: 5 60 60 For the first tree there are clearly 5 different labelings, and for the second and third there are 5! 2 = 60 labelings, so we obtain T5 = 125. This should be enough to conjecture Tn = nn−2, and that is precisely Cayley’s result. Theorem. There are nn−2 different labeled trees on n vertices. This beautiful formula yields to equally beautiful proofs, drawing on a variety of combinatorial and algebraic techniques. We will outline three of them before presenting the proof which is to date the most beautiful of them all. Arthur Cayley (1821-1895) There are nn2 trees on n distinct vertices. Cayley’s formula:
Algorithmic Enumeration 0-0 enumeration algorithm: for i =1,2,3,...nm-2 output the i-th tree; 及又又又 counting algorithm: input:undirected graph G(V,E) t(G):"The number of different spanning trees of G(V,E)
Algorithmic Enumeration “The number of different spanning trees of G(V,E).” input: undirected graph G(V, E) t(G) : for i =1,2,3,... nn-2 output the i-th tree; enumeration algorithm: counting algorithm:
Graph Laplacian Graph G(V,E) adjacency matrix A A6,)= 1}e {i,}年E diagonal matrix D di d2 m-{0 i卡j 0 dn graph Laplacian L 3 -1 -1 -1 -1 2 0 L-D-A L= -1 -1 -1 0 -1 2
Graph Laplacian 1 2 4 3 Graph G(V,E) adjacency matrix A A(i, j) = ( 1 {i, j} 2 E 0 {i, j} 62 E D(i, j) = ( deg(i) i = j 0 i 6= j diagonal matrix D D = 2 6 6 6 4 d1 d2 ... dn 3 7 7 7 5 0 0 graph Laplacian L L = D A L = 2 6 6 4 3 1 1 1 1 2 1 0 1 1 3 1 1 0 1 2 3 7 7 5
Li.:submatrix of L by removing ith row and ith collumn Gustav Kirchhoff (1824-1887) t(G):number of spanning trees in G Kirchhoff's Matrix-Tree Theorem: Vi,t(G)=det(Li.i)
Li,i : submatrix of L by removing ith row and ith collumn i i t(G) : number of spanning trees in G Kirchhoff ’s Matrix-Tree Theorem: 8i, t(G) = det(Li,i) Gustav Kirchhoff (1824-1887)