Introduction to Algebraic Combinatorics
Algebraic combinatorics is a field that uses algebraic methods to solve counting problems and, conversely, applies combinatorial techniques to understand algebraic structures. It sits at the intersection of several mathematical disciplines including combinatorics, algebra, representation theory, and geometry.
Key areas of study include:
- Enumerative combinatorics
- Symmetric functions and symmetric groups
- Representation theory
- Combinatorial species
- Poset theory
- Polytopes and arrangements
- Matroids and combinatorial geometry
- Combinatorial aspects of quantum groups
Fundamental Counting Principles
Basic Counting Formulas
| Concept | Formula | Description |
|---|---|---|
| Multiplication Principle | $n_1 \times n_2 \times \cdots \times n_k$ | If a task consists of $k$ sequential steps, where the $i$-th step can be performed in $n_i$ ways, then the entire task can be performed in $n_1 \times n_2 \times \cdots \times n_k$ ways |
| Addition Principle | $n_1 + n_2 + \cdots + n_k$ | If a task can be done in $k$ different ways, where the $i$-th way can be performed in $n_i$ ways, then the task can be performed in $n_1 + n_2 + \cdots + n_k$ ways |
| Inclusion-Exclusion Principle | $ | A_1 \cup A_2 \cup \cdots \cup A_n |
| Pigeonhole Principle | If $n$ objects are placed into $m$ containers and $n > m$, then at least one container must contain more than one object | Used to prove existence of certain patterns |
Permutations and Combinations
| Concept | Formula | Description |
|---|---|---|
| Permutation of $n$ elements | $P(n) = n!$ | Number of ordered arrangements of $n$ distinct elements |
| Permutation of $n$ elements taken $k$ at a time | $P(n,k) = \frac{n!}{(n-k)!}$ | Number of ordered arrangements of $k$ elements selected from $n$ distinct elements |
| Combination of $n$ elements taken $k$ at a time | $C(n,k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$ | Number of unordered selections of $k$ elements from $n$ distinct elements |
| Multiset coefficient | $\binom{n}{k_1, k_2, \ldots, k_m} = \frac{n!}{k_1! k_2! \cdots k_m!}$ | Number of ways to divide $n$ distinct objects into $m$ groups with $k_i$ objects in group $i$ |
| Multiset permutation | $\binom{n}{k_1, k_2, \ldots, k_m} = \frac{n!}{k_1! k_2! \cdots k_m!}$ | Number of distinct permutations of $n$ elements where element $i$ appears $k_i$ times |
| Combinations with repetition | $\binom{n+k-1}{k} = \binom{n+k-1}{n-1}$ | Number of ways to select $k$ elements from a set of $n$ elements, with repetition allowed |
Binomial Coefficients Properties
| Property | Formula |
|---|---|
| Symmetry | $\binom{n}{k} = \binom{n}{n-k}$ |
| Pascal’s Identity | $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ |
| Binomial Theorem | $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$ |
| Hockey Stick Identity | $\sum_{j=r}^{n} \binom{j}{r} = \binom{n+1}{r+1}$ |
| Vandermonde’s Identity | $\sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k} = \binom{m+n}{r}$ |
| Upper Negation Formula | $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ |
Generating Functions
Types of Generating Functions
| Type | Definition | Usage |
|---|---|---|
| Ordinary Generating Function (OGF) | $G(x) = \sum_{n=0}^{\infty} a_n x^n$ | Counts objects where order matters |
| Exponential Generating Function (EGF) | $G(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$ | Counts labeled objects |
| Probability Generating Function (PGF) | $G(x) = \sum_{n=0}^{\infty} p_n x^n$ | Encodes probability distributions |
Common Generating Functions
| Sequence | Ordinary Generating Function |
|---|---|
| $1, 1, 1, \ldots$ | $\frac{1}{1-x}$ |
| $1, r, r^2, r^3, \ldots$ | $\frac{1}{1-rx}$ |
| $0, 1, 2, 3, \ldots$ | $\frac{x}{(1-x)^2}$ |
| $1, 2, 3, 4, \ldots$ | $\frac{1}{(1-x)^2}$ |
| $1, 0, 1, 0, 1, \ldots$ | $\frac{1}{1-x^2}$ |
| $0, 1, 0, 1, 0, \ldots$ | $\frac{x}{1-x^2}$ |
| $1, C_0, C_1, C_2, \ldots$ | $\frac{1-\sqrt{1-4x}}{2x}$ (Catalan) |
| $F_0, F_1, F_2, \ldots$ | $\frac{x}{1-x-x^2}$ (Fibonacci) |
Exponential Generating Functions
| Sequence | Exponential Generating Function |
|---|---|
| $1, 1, 1, \ldots$ | $e^x$ |
| $1, r, r^2, r^3, \ldots$ | $e^{rx}$ |
| $0, 1, 2, 3, \ldots$ | $xe^x$ |
| $0, 0, 1, 2, 3, \ldots$ | $x^2e^x$ |
| $B_0, B_1, B_2, \ldots$ | $\frac{x}{e^x-1}$ (Bernoulli) |
| $1, 1, 2, 5, 15, \ldots$ | $\frac{1}{2-e^x}$ (Bell) |
Generating Function Operations
| Operation | Effect on Sequence | Effect on OGF |
|---|---|---|
| $a_n + b_n$ | Sum of sequences | $A(x) + B(x)$ |
| $c \cdot a_n$ | Scaling | $c \cdot A(x)$ |
| $a_{n-m}$ (for $n \geq m$) | Shift right | $x^m \cdot A(x)$ |
| $a_{n+m}$ | Shift left | $\frac{A(x) – a_0 – a_1x – \cdots – a_{m-1}x^{m-1}}{x^m}$ |
| $\sum_{k=0}^{n} a_k b_{n-k}$ | Convolution | $A(x) \cdot B(x)$ |
| $n \cdot a_n$ | Differentiation | $x \cdot \frac{d}{dx}A(x)$ |
| $\frac{a_n}{n+1}$ | Integration | $\int_0^x \frac{A(t)}{t} dt$ |
| $a_0 + a_1 + \cdots + a_n$ | Partial sums | $\frac{A(x)}{1-x}$ |
Symmetric Functions
Elementary Symmetric Functions
$e_k(x_1, x_2, \ldots, x_n) = \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} x_{i_1} x_{i_2} \cdots x_{i_k}$
Example: $e_2(x_1, x_2, x_3) = x_1 x_2 + x_1 x_3 + x_2 x_3$
Complete Homogeneous Symmetric Functions
$h_k(x_1, x_2, \ldots, x_n) = \sum_{1 \leq i_1 \leq i_2 \leq \cdots \leq i_k \leq n} x_{i_1} x_{i_2} \cdots x_{i_k}$
Example: $h_2(x_1, x_2) = x_1^2 + x_1 x_2 + x_2^2$
Power Sum Symmetric Functions
$p_k(x_1, x_2, \ldots, x_n) = \sum_{i=1}^{n} x_i^k$
Example: $p_2(x_1, x_2, x_3) = x_1^2 + x_2^2 + x_3^2$
Monomial Symmetric Functions
$m_\lambda(x_1, x_2, \ldots, x_n) = \sum x_1^{\alpha_1} x_2^{\alpha_2} \cdots x_n^{\alpha_n}$
where the sum is over all distinct permutations $(\alpha_1, \alpha_2, \ldots, \alpha_n)$ of the partition $\lambda$.
Schur Functions
$s_\lambda(x_1, x_2, \ldots, x_n) = \frac{\det(x_i^{\lambda_j + n – j}){1 \leq i,j \leq n}}{\det(x_i^{n-j}){1 \leq i,j \leq n}}$
Newton’s Identities
Relations between elementary symmetric functions and power sums:
$ke_k = \sum_{i=1}^{k} (-1)^{i-1} e_{k-i} p_i$
Representation Theory of the Symmetric Group
Cycle Structure and Conjugacy Classes
Conjugacy classes in $S_n$ correspond to partitions of $n$, representing cycle structures.
Example: In $S_4$, the permutation $(1,2)(3,4)$ has cycle structure $2+2=4$, corresponding to partition $[2,2]$.
Character Table Properties
- Number of irreducible representations equals number of conjugacy classes
- Sum of squares of dimensions equals order of group
- Characters are constant on conjugacy classes
- Different irreducible characters are orthogonal
Young Diagrams and Tableaux
- Young Diagram: Visual representation of a partition $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_k)$
- Young Tableau: Filling of a Young diagram with entries $1, 2, \ldots, n$
- Standard Young Tableau: Entries increase along rows and columns
Hook-Length Formula
Number of standard Young tableaux of shape $\lambda$:
$f^\lambda = \frac{n!}{\prod_{(i,j) \in \lambda} h_{ij}}$
where $h_{ij}$ is the hook length at position $(i,j)$.
Dimension Formula for Irreducible Representations
$\dim(V_\lambda) = \frac{n!}{\prod_{(i,j) \in \lambda} h_{ij}}$
Murnaghan-Nakayama Rule
For calculating character values:
$\chi^\lambda_\mu = \sum_{\nu} (-1)^{ht(\nu/\lambda)} \chi^{\nu}_{\mu – (r)}$
where the sum is over all partitions $\nu$ such that $\nu/\lambda$ is a border strip of size $r$.
Posets and Lattices
Basic Definitions
- Poset: Partially ordered set $(P, \leq)$
- Chain: Totally ordered subset of a poset
- Antichain: Subset where no two elements are comparable
- Hasse Diagram: Graphical representation of a poset
Important Posets in Combinatorics
| Poset | Description |
|---|---|
| Boolean Lattice $B_n$ | Subsets of ${1,2,\ldots,n}$ ordered by inclusion |
| Divisor Lattice $D_n$ | Positive divisors of $n$ ordered by division |
| Young’s Lattice $Y$ | Partitions ordered by inclusion of Young diagrams |
| Partition Lattice $\Pi_n$ | Partitions of ${1,2,\ldots,n}$ ordered by refinement |
Möbius Function and Möbius Inversion
For a locally finite poset $(P, \leq)$, the Möbius function $\mu(x,y)$ is defined recursively:
- $\mu(x,x) = 1$ for all $x \in P$
- $\mu(x,y) = -\sum_{x \leq z < y} \mu(x,z)$ for $x < y$
Möbius Inversion Formula: If $f(y) = \sum_{x \leq y} g(x)$, then $g(y) = \sum_{x \leq y} \mu(x,y) f(x)$
Notable Möbius Functions
| Poset | Möbius Function |
|---|---|
| Boolean Lattice $B_n$ | $\mu(X,Y) = (-1)^{ |
| Divisor Lattice $D_n$ | $\mu(d,n) = \begin{cases} (-1)^k & \text{if } n/d \text{ is a product of } k \text{ distinct primes} \ 0 & \text{if } n/d \text{ is divisible by a square of a prime} \end{cases}$ |
| Partition Lattice $\Pi_n$ | $\mu(\pi, \hat{1}) = (-1)^{n-b} (b-1)!$ where $b$ is the number of blocks in $\pi$ |
q-Analogs and Quantum Combinatorics
q-Numbers and q-Factorials
- q-Number: $[n]_q = 1 + q + q^2 + \cdots + q^{n-1} = \frac{1-q^n}{1-q}$
- q-Factorial: $[n]_q! = [1]_q [2]_q \cdots [n]_q$
- q-Binomial Coefficient: $\binom{n}{k}_q = \frac{[n]_q!}{[k]_q! [n-k]_q!}$
Gaussian Binomial Coefficient Interpretations
- Number of $k$-dimensional subspaces of an $n$-dimensional vector space over $\mathbb{F}_q$
- $q$-analog of the binomial coefficient
q-Binomial Theorem
$(x+y)^n_q = \sum_{k=0}^{n} \binom{n}{k}_q x^{n-k} y^k$
where $(x+y)^n_q$ denotes the $q$-analog of $(x+y)^n$.
Matroids and Combinatorial Geometry
Matroid Definition
A matroid $M$ is a pair $(E, \mathcal{I})$ where $E$ is a finite set and $\mathcal{I}$ is a collection of subsets of $E$ (independent sets) such that:
- $\emptyset \in \mathcal{I}$
- If $I \in \mathcal{I}$ and $I’ \subseteq I$, then $I’ \in \mathcal{I}$
- If $I_1, I_2 \in \mathcal{I}$ and $|I_1| < |I_2|$, then $\exists e \in I_2 \setminus I_1$ such that $I_1 \cup {e} \in \mathcal{I}$
Examples of Matroids
| Type | Ground Set | Independent Sets |
|---|---|---|
| Graphic Matroid | Edges of a graph | Forests (acyclic subgraphs) |
| Vector Matroid | Vectors in a matrix | Linearly independent subsets |
| Uniform Matroid $U_{k,n}$ | ${1,2,\ldots,n}$ | All subsets of size at most $k$ |
Tutte Polynomial
For a matroid $M$ on ground set $E$:
$T_M(x,y) = \sum_{A \subseteq E} (x-1)^{r(E)-r(A)} (y-1)^{|A|-r(A)}$
where $r(A)$ is the rank function of $M$.
Characteristic Polynomial
For a matroid $M$:
$\chi_M(t) = \sum_{X \subseteq E} (-1)^{|X|} t^{r(E) – r(X)}$
Enumerative Combinatorics
Important Counting Sequences
| Sequence | Formula | OEIS | Description |
|---|---|---|---|
| Catalan Numbers | $C_n = \frac{1}{n+1}\binom{2n}{n}$ | A000108 | Counts various structures including Dyck paths, binary trees |
| Bell Numbers | $B_n = \sum_{k=0}^{n} S(n,k)$ | A000110 | Number of partitions of an $n$-element set |
| Stirling Numbers of 1st Kind | $s(n,k)$ | A008275 | Counts permutations of $n$ elements with $k$ cycles |
| Stirling Numbers of 2nd Kind | $S(n,k)$ | A008277 | Counts partitions of $n$ elements into $k$ non-empty subsets |
| Eulerian Numbers | $A(n,k)$ | A008292 | Counts permutations of $n$ elements with $k$ ascents |
| Narayana Numbers | $N(n,k) = \frac{1}{n}\binom{n}{k}\binom{n}{k-1}$ | A001263 | Refines Catalan numbers by various statistics |
Stirling Numbers Recurrence Relations
- First Kind: $s(n+1,k) = s(n,k-1) – n \cdot s(n,k)$
- Second Kind: $S(n+1,k) = k \cdot S(n,k) + S(n,k-1)$
Eulerian Numbers Recurrence Relation
$A(n,k) = (n-k) \cdot A(n-1,k-1) + (k+1) \cdot A(n-1,k)$
Polytopes and Arrangements
Face Numbers and f-Vectors
For a $d$-dimensional polytope $P$, the $f$-vector is $(f_0, f_1, \ldots, f_{d-1})$ where $f_i$ counts the number of $i$-dimensional faces.
Euler’s Formula for Polytopes
For a $d$-dimensional convex polytope:
$\sum_{i=0}^{d-1} (-1)^i f_i = 1 + (-1)^{d-1}$
Hyperplane Arrangements
- Region: Connected component of the complement of an arrangement
- Characteristic Polynomial: $\chi(A,t) = \sum_{X \in L(A)} \mu(\hat{0}, X) \cdot t^{\dim(X)}$
Zaslavsky’s Theorem
Number of regions formed by a hyperplane arrangement $A$ in $\mathbb{R}^d$:
$r(A) = (-1)^d \chi(A, -1)$
Combinatorial Species
Definition
A combinatorial species $F$ is a functor from the category of finite sets and bijections to the category of finite sets and functions.
Operations on Species
| Operation | Description | Generating Function |
|---|---|---|
| Sum $(F + G)$ | Disjoint union | $F(x) + G(x)$ |
| Product $(F \cdot G)$ | Cartesian product | $F(x) \cdot G(x)$ |
| Composition $(F \circ G)$ | Substitution | $F(G(x))$ |
| Derivative $(F’)$ | Remove marked element | $\frac{d}{dx}F(x)$ |
| Pointing $(F^\bullet)$ | Mark an element | $x \cdot \frac{d}{dx}F(x)$ |
Common Species
| Species | Description | EGF |
|---|---|---|
| $X$ | Singleton | $x$ |
| $E$ | Set | $e^x$ |
| $E_k$ | $k$-element set | $\frac{x^k}{k!}$ |
| $C$ | Cycle | $\log(\frac{1}{1-x})$ |
| $L$ | Linear order | $\frac{1}{1-x}$ |
| $B$ | Binary tree | $T$ where $T = x + T^2$ |
Important Theorems and Results
Ramsey’s Theorem
For any integers $r, s \geq 2$, there exists a smallest integer $R(r,s)$ such that any graph on $n \geq R(r,s)$ vertices contains either a clique of size $r$ or an independent set of size $s$.
The Matrix-Tree Theorem
The number of spanning trees of a graph $G$ equals any cofactor of its Laplacian matrix.
Sperner’s Theorem
The largest antichain in the Boolean lattice $B_n$ has size $\binom{n}{\lfloor n/2 \rfloor}$.
The Robinson-Schensted-Knuth (RSK) Correspondence
Bijection between permutations in $S_n$ and pairs of standard Young tableaux of the same shape with $n$ boxes.
The Littlewood-Richardson Rule
For partitions $\lambda, \mu, \nu$:
$c_{\lambda\mu}^\nu = $ number of Littlewood-Richardson tableaux of shape $\nu/\lambda$ and weight $\mu$.
The Hook-Content Formula
For a partition $\lambda$:
$s_\lambda(1,q,q^2,\ldots,q^{n-1}) = q^{b(\lambda)} \prod_{u \in \lambda} \frac{1-q^{n+c(u)}}{1-q^{h(u)}}$
where $b(\lambda) = \sum (i-1)\lambda_i$, $c(u)$ is the content, and $h(u)$ is the hook length.
Combinatorial Algorithms
Algorithms for Generating Combinatorial Objects
| Object | Algorithm | Complexity |
|---|---|---|
| Permutations | Heap’s Algorithm | $O(n!)$ |
| Combinations | Next Combination | $O(n \cdot \binom{n}{k})$ |
| Partitions | Next Partition | $O(p(n))$ where $p(n)$ is the partition function |
| Standard Young Tableaux | Hook Walk Algorithm | $O(n^2)$ per tableau |
Algorithms for Computational Problems
| Problem | Algorithm | Complexity |
|---|---|---|
| Matrix Permanent | Ryser’s Formula | $O(n \cdot 2^n)$ |
| Counting Linear Extensions | Dynamic Programming | #P-complete in general |
| Tutte Polynomial Evaluation | Deletion-Contraction | Exponential in general |
Resources for Further Learning
Core Textbooks
- Richard P. Stanley. “Enumerative Combinatorics, Volumes 1 & 2”
- Gian-Carlo Rota. “Studies in Combinatorics”
- Anders Björner and Richard P. Stanley. “A Combinatorial Miscellany”
- Ian G. Macdonald. “Symmetric Functions and Hall Polynomials”
- Sergey Fomin. “Duality of Graded Graphs”
Research Journals
- Journal of Algebraic Combinatorics
- The Electronic Journal of Combinatorics
- Discrete Mathematics
- European Journal of Combinatorics
- Annals of Combinatorics
Online Resources
- The On-Line Encyclopedia of Integer Sequences (OEIS)
- Combinatorial Object Server
- MathOverflow (algebraic-combinatorics tag)
- SAGE Mathematical Software