OGF - Cayley Formula

Question Statement

Prove # of trees on [n] =

Solution

Functional Digraph(directed graph)

编者注:V为节点集合
if 注:E为边集合

Example
| x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| -- |
| f(x) | 1 | 5 | 3 | 11 | 10 | 12 | 5 | 15 | 12 | 7 | 1 | 7 | 15 | 3 | 15 |
The graph looks like follows:
blob.jpg
将环用最小的点表示并且拆环,得:
blob.jpg

Permutation: Cycle Rep

Example Of Cycles

in
cycles are

Problem Statement

C(n,k) is the # of permutations of n with k cycles.
Prove

Solution

Let

将最小数设为Cycle的代表:如上例

按最小数逆序排序Cycle

Example
| step | choose | cycles |
| -- |
| 1 | x | (1) |
| 2 | x | (1)(2) |
| 2 | 1 | (1,2) |
| 3 | x | (3)(2)(1) |
| 3 | 2 | (2,3)(1) or (2)(1,3) |
即,若取x=newCycle
取常数=加到原来的一个环中

Another Problem

Problem Statement

S(n,k)=# of partitions of n elements into k blocks(顺序不重要) (不能为空)
Prove

Solution

顺序不重要
枚举至少i个为空
选i个
随便放东西

Prove Problem I

Problem Statement

Prove (A(n,k) is # of permutations with k runs)

Solution

空run的个数
两次容斥

Prove Problem II

Problem Statement

Prove
D(n):# of permutations with no fix points(错排)

Solution

容斥

k枚举多少个在自己位置上

Homework

Q1

find # of planar graph (labelled) on N nodes.
(Please see the O.Gimenei and M.Noy Asymptotic enumeration and limit laws of planar graphs J.A.M.S,2009 for answers.)

Q2

find # of unlabelled planar graphs on N nodes. Problems Open(Unsolved By Everyone)

Contact the teacher

YiFan Jing 荆一凡

Mail

Blog