Combinatorics

Contents

Enumerative Combinatorics

Graph Enumeration

Twelvefold Way

Permutation

S_n, p, q : S_n ⇒ p q : S_n (closure). p, q, r : S_n ⇒ (p q) r = p (q r) (associative). 1_n p = p 1_n = p (identity). p^-1 p = p p^-1 = 1_n (invertible). Generally p q = q p (non-commutative). Cycle notation. p(1) = 2, p(2) = 5, p(3) = 4, p(4) = 3, p(5) = 1 ⇔ p = (1 2 5)(3 4)p^-1 = (5 2 1)(4 3)

Permutation matrix

(a_p)_{i, j} = 1 if i = p(j) | 0 otherwise.

Parity

Riffle Shuffle Permutation

Shuffle Algebra

Matroid

References