# OGF - Cayley Formula

## Question Statement

Prove # of trees on [n] = n^{n-2}

## Solution

f:(1,2,3,...,n)\to(1,2,3,...,n)
f(1)=1,f(n)=n
Functional Digraph(directed graph) D
V(D)=[n] 编者注：V为节点集合
(i,j)\in E(D) if f(i)=j 注：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:

# Permutation: Cycle Rep

## Example Of Cycles

in (^{id=1,2,3,4,5,6,7,8,9}_{va=4,6,1,7,5,2,3,9,8})
cycles are (1,4,7,3)(5)(2,6)(8,9)

## Problem Statement

C(n,k) is the # of permutations of n with k cycles.
Prove \sum_{i=1}^nC(n,k)x^k=\prod_{i=1}^n(x+i-1)

## Solution

Let Cu(x)=\sum_{i=1}^nC(n,k)x^k=\prod_{i=1}^n(x+i-1)

\sum_{i=1}^nC(n,k)x^k=[x^k]Cu(x)
\prod_{i=1}^n(x+i-1)=x(x+1)(x+2)...(x+n-1)

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) |

# Another Problem

## Problem Statement

S(n,k)=# of partitions of n elements into k blocks(顺序不重要) (不能为空)
Prove S(n,k)=\frac{1}{k!}\sum_{i=0}^k(-1)^k\binom{k}{i}(k-i)^n

## Solution

\frac{1}{k!} 顺序不重要
\sum_{i=0}^k 枚举至少i个为空
\binom{k}{i} 选i个
(k-i)^n 随便放东西

# Prove Problem I

## Problem Statement

Prove A(n,k)=\sum_{i=0}^k\binom{n+1}{i}(k-i)^n (A(n,k) is # of permutations with k runs)

## Solution

\sum_{i=0}^k空run的个数

# Prove Problem II

## Problem Statement

Prove D(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!}
D(n):# of permutations with no fix points(错排)

## Solution

D(n)=\sum_{k=0}^n\frac{n!}{k!}\times(-1)^k
(-1)^k 容斥
\frac{n!}{k!}A^{n-k}_n
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)

YiFan Jing 荆一凡
Mail
Blog

THE END