Counting (labeled)trees …。. "How many different trees 3 can be formed from n distinct vertices?" 39 8 8人人
Counting (labeled) trees “How many different trees can be formed from n distinct vertices?
Cayley's formula: There are nT-2 trees on n distinct vertices. 00 八入八 83 6 P 9 足人人 Arthur Cayley
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 3 4 3 4 3 4 343434 3434 3 4 3 4 3 4 343434 1 1 12 12 2 1 2 1212 1 1 2 1 2 3 2 2 1 2 1 2 1212 1 2 1 2 1 2 121212 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 6 60 0 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 There are nn2 trees on n distinct vertices. Cayley’s formula:
Prufer Code leaf:vertex of degree 1 removing a leaf from T,still a tree Ta: T1=T; 5 for i=1 to n-1 smallest leaf in T; (ui,v):edge in Ti; T1=delete ui from Ti; :2,4,5,6,3,1 Prufer code: :4,3,1,3,1,7 (1,2,…,m-2)
Prüfer Code 4 3 6 2 5 1 7 T1 = T ; ui : smallest leaf in Ti ; (ui,vi) : edge in Ti ; Ti+1 = delete ui fromTi ; for i = 1 to n-1 Prüfer code: (v1, v2, ... , vn-2) T : ui : vi : T23145 4, 3, 1, 3, 1, 7 2, 4, 5, 6, 3, 1 T6 leaf : vertex of degree 1 removing a leaf from T, still a tree
edges of T:（u,),1≤i≤nm-l u:smallest leaf in T Un-1 =n a tree has≥2 leaves } u≠m n is never deleted T: Only need to recover 5 every ui from (v1,U1,...,Un-2). u is the smallest number not in {u1,,ua-1}U{v,.,vn-1} :2,4,5,6,3,1 :4,3,1,3,1,7 (1,2,…,vm-2）
4 3 6 2 5 1 7 T : ui : vi : 4, 3, 1, 3, 1, 7 2, 4, 5, 6, 3, 1 (v1, v2, ... , vn-2) edges of T : (ui,vi), 1≤i≤n-1 vn-1 = n a tree has ≥2 leaves ui : smallest leaf in Ti } ui ≠ n n is never deleted Only need to recover every ui from (v1, v1, ... , vn-2). {u1,...,ui1} {vi,...,vn1} ui is the smallest number not in
u is the smallest number not in {u1,,u-1}U{v,,vn-1} V vertex v in T, occurrences of v in u1,u2,...un-1,Un-1:1 occurrences of v in edges (ui,v),1<i<n-1:degr(v) T: 2 occurrences of v in Prufer code:(Ⅵ，2，…，vm-2) degr(v)-1 :2,4,5,6,3,1 :4,3,1,3,1,7 (1,2,.,m-2)
4 3 6 2 5 1 7 T : ui : vi : 4, 3, 1, 3, 1, 7 2, 4, 5, 6, 3, 1 (v1, v2, ... , vn-2) {u1,...,ui1} {vi,...,vn1} ui is the smallest number not in ∀ vertex v in T, # occurrences of v in u1, u2, ... , un-1, vn-1 : 1 # occurrences of v in edges (ui,vi), 1≤i≤n-1: degT(v) # occurrences of v in Prüfer code: (v1, v2, ... , vn-2) degT(v)-1
u is the smallest number not in {u1,,u-1}U{v,,vn-1} V vertex v in Ti, #occurrences of v in ui,uit1,..un-1,Un-1 1 occurrences of v in edges (ui,v),i<j<n-1:degr:(v) T: occurrences of v in (vi,...Un-2) degr,(v)-1 leaf v of Ti: :2,4,5,6,3,1 in {ui,Uitl,...Un-1,Un-1 :4,3,1,3,1,7 not in {vi,Vit1,...Un-2 (1,2,.,Vm-2 smallest leaf in T
4 3 6 2 5 1 7 T : ui : vi : 4, 3, 1, 3, 1, 7 2, 4, 5, 6, 3, 1 (v1, v2, ... , vn-2) {u1,...,ui1} {vi,...,vn1} ui is the smallest number not in ∀ vertex v in Ti, # occurrences of v in ui, ui+1, ... , un-1, vn-1 : 1 # occurrences of v in edges (uj,vj), i≤j≤n-1: # occurrences of v in (vi, ... , vn-2) LMOTi (v) LMOTi (v) 1 leaf v of Ti : in {ui, ui+1, ... , un-1, vn-1} not in {vi, vi+1, ... , vn-2} ui : smallest leaf in Ti
u is the smallest number not in {u1,,u-1}U{v2,,vn-1} T: ② 5 T=empty graph; Un-1 =n; for i=1 to n-1 i:smallest number not in {u1,,1}lU{i,m-1} :2,4,5,6,3,1 add edge (ui,v:)to T; :4,3,1,3,1,7 (1,2,…,vm-2）
4 3 6 2 5 1 7 T : ui : vi : 4, 3, 1, 3, 1, 7 2, 4, 5, 6, 3, 1 (v1, v2, ... , vn-2) {u1,...,ui1} {vi,...,vn1} ui is the smallest number not in T = empty graph; ui : smallest number not in add edge (ui,vi) to T ; for i = 1 to n-1 {u1,...,ui-1}∪{vi,...,vn-1} vn-1 = n ;
Prufer code is reversible > 1-1 every(1,v2,,m-2)∈{1,2，，n}n-2 is decodable to a tree > onto T: 2 5 T=empty graph; Un-1 =n; for i=1 to n-1 u:smallest number not in {1,…,1}U{z,…,n-1} :2,4,5,6,3,1 add edge (ui,v:)to T; :4,3,1,3,1,7 (1,2,.,Vm-2
4 3 6 2 5 1 7 T : ui : vi : 4, 3, 1, 3, 1, 7 2, 4, 5, 6, 3, 1 (v1, v2, ... , vn-2) T = empty graph; ui : smallest number not in add edge (ui,vi) to T ; for i = 1 to n-1 {u1,...,ui-1}∪{vi,...,vn-1} vn-1 = n ; Prüfer code is reversible 1-1 every (v1, v2,...,vn2) {1, 2,...,n}n2 is decodable to a tree onto
Prufer code is reversible > 1-1 every(1,v2,,m-2)∈{1,2，.，n}n-2 is decodable to a tree > onto Cayley's formula: There are n"-2 trees on n distinct vertices
Prüfer code is reversible 1-1 every (v1, v2,...,vn2) {1, 2,...,n}n2 is decodable to a tree onto There are nn2 trees on n distinct vertices. Cayley’s formula:
Double Counting of sequences of adding directed edges to an empty graph to form a rooted tree
# of sequences of adding directed edges to an empty graph to form a rooted tree Double Counting