# OGF - Cayley Formula

## Question Statement

Prove # of trees on [n] =

## Solution

Functional Digraph(directed graph)

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:

# Permutation: Cycle Rep

in
cycles are

## Problem Statement

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

## Solution

Let

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

# Prove Problem I

## Problem Statement

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

# Prove Problem II

## Problem Statement

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

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