Enumerative Combinatorics - Core Definitions

Enumerative combinatorics is the branch of mathematics concerned with counting the number of elements in finite sets. The fundamental problem is to determine the cardinality of a set that satisfies certain properties, often expressed through explicit formulas, generating functions, or recurrence relations.

DefinitionCombinatorial Function

A combinatorial function $f: \mathbb{N} \to \mathbb{N}$ is a function that counts discrete structures. The most fundamental examples are:

Factorial: $n! = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1$ with $0! = 1$
Binomial coefficient: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ for $0 \leq k \leq n$
Multinomial coefficient: $\binom{n}{k_1, k_2, \ldots, k_m} = \frac{n!}{k_1! k_2! \cdots k_m!}$ where $k_1 + k_2 + \cdots + k_m = n$

The binomial coefficient $\binom{n}{k}$ counts the number of ways to choose $k$ objects from $n$ distinct objects without regard to order. This function satisfies Pascal's identity: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ , which reflects the recursive structure of combinatorial counting.

DefinitionPermutation and Combination

Let $S$ be a finite set with $|S| = n$ .

A $k$ -permutation of $S$ is an ordered sequence of $k$ distinct elements from $S$ . The number of $k$ -permutations is $P(n,k) = \frac{n!}{(n-k)!}$ .
A $k$ -combination of $S$ is an unordered subset of $k$ elements from $S$ . The number of $k$ -combinations is $\binom{n}{k}$ .
A $k$ -permutation with repetition allows repeated elements, counted by $n^k$ .
A $k$ -combination with repetition (also called multiset) is counted by $\binom{n+k-1}{k}$ .

ExampleCounting Poker Hands

A standard deck has 52 cards. The number of 5-card poker hands is: $\binom{52}{5} = \frac{52!}{5! \cdot 47!} = 2{,}598{,}960$

The number of full house hands (3 cards of one rank, 2 of another) is: $13 \cdot \binom{4}{3} \cdot 12 \cdot \binom{4}{2} = 13 \cdot 4 \cdot 12 \cdot 6 = 3{,}744$ where we choose the rank for the triple, select 3 of 4 suits, choose the rank for the pair, and select 2 of 4 suits.

The power of enumerative combinatorics lies in recognizing structural patterns. Two sets are in bijection if there exists a one-to-one correspondence between them, allowing us to transfer counting problems to simpler domains.

Remark

The fundamental principle of counting states that if a process can be broken into $k$ independent steps with $n_1, n_2, \ldots, n_k$ ways to perform each step, then the total number of ways to complete the process is $n_1 \cdot n_2 \cdot \ldots \cdot n_k$ . This multiplicative principle, together with the additive principle for disjoint cases, forms the foundation of all combinatorial enumeration.

DefinitionStirling Numbers

Two families of combinatorial numbers arise frequently in enumeration:

Stirling numbers of the first kind $s(n,k)$ : the number of permutations of $n$ elements with $k$ cycles (signed version denoted $s(n,k)$ , unsigned $|s(n,k)|$ ).
Stirling numbers of the second kind $S(n,k)$ : the number of ways to partition a set of $n$ elements into $k$ non-empty subsets.

These satisfy recurrences: $s(n,k) = s(n-1,k-1) - (n-1)s(n-1,k)$ and $S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k)$ .

The Bell numbers $B_n = \sum_{k=0}^n S(n,k)$ count all partitions of an $n$ -element set, while the Catalan numbers $C_n = \frac{1}{n+1}\binom{2n}{n}$ count numerous equivalent structures including balanced parentheses, binary trees, and triangulations of convex polygons.