combinatorics.bigb

= Combinatorics
{wiki}

= Tree
{parent=Combinatorics}
{wiki=Tree_(graph_theory)}

A tree is a connected <graph> containing no cycle. A finite tree on $n$ vertices has $n-1$ edges.

= Breadth-first search
{parent=Tree}
{c}
{wiki}

Breadth-first search explores a graph in successive distance layers from a starting vertex. Before two exploration branches meet, the explored edges form a tree.

= Double counting
{parent=Combinatorics}
{wiki=Double_counting_(proof_technique)}

Double counting proves an identity by counting the same finite set in two different ways.

= Factorial
{title2=$n!$}
{parent=Combinatorics}
{wiki}

For a nonnegative <integer> $n$, the factorial is
$$
n!=1\cdot2\cdots n,
$$
with $0!=1$.

= Binomial coefficient
{title2=$\binom{n}{k}$}
{parent=Combinatorics}
{wiki}

The <binomial coefficient>
$$
\binom nk=\frac{n!}{k!(n-k)!}
$$
counts the $k$-element subsets of an $n$-element set. Equivalently, it counts strings containing $k$ copies of one symbol and $n-k$ copies of another.

= Pascal's identity
{c}
{parent=Binomial coefficient}
{wiki=Pascal%27s_rule}

Pascal's identity is
$$
\binom nk=\binom{n-1}k+\binom{n-1}{k-1}.
$$

= Central binomial coefficient
{title2=$\binom{2n}{n}$}
{parent=Binomial coefficient}
{wiki}

The central binomial coefficient is the largest coefficient in the expansion of $(1+1)^{2n}$:
$$
\binom{2n}{n}=\frac{(2n)!}{(n!)^2}.
$$

= Multinomial coefficient
{title2=$\binom{n}{n_1,\ldots,n_r}$}
{parent=Binomial coefficient}
{wiki}

For nonnegative integers with $n_1+\cdots+n_r=n$, the <multinomial coefficient>
$$
\binom{n}{n_1,\ldots,n_r}
=\frac{n!}{n_1!\cdots n_r!}
$$
counts arrangements of a multiset containing $n_j$ copies of symbol $j$.

= Binomial theorem
{parent=Binomial coefficient}
{wiki}

For a nonnegative integer $n$,
$$
(x+y)^n=\sum_{k=0}^n\binom nkx^ky^{n-k}.
$$

Combinatorics studies finite and discrete structures through counting, construction, and extremal arguments.

= Binomial theorem for commuting matrices
{parent=Binomial theorem}

If square matrices $A$ and $B$ commute, then
$$
(A+B)^n=\sum_{k=0}^n\binom nkA^{n-k}B^k.
$$
The usual proof works because commutativity allows words with the same numbers of $A$ and $B$ factors to be collected.

= Alternating binomial-square sum
{parent=Binomial theorem}

Coefficient extraction from $(1-x)^n(1+x)^n=(1-x^2)^n$ gives
$$
\sum_{r=0}^n(-1)^r\binom nr^2
=\begin{cases}0,&n\text{ odd},\\(-1)^{n/2}\binom n{n/2},&n\text{ even}.
\end{cases}
$$

= Alternating-permutation convolution
{parent=Combinatorics}

Splitting an alternating permutation at its maximum gives
$$
2A_{n+1}=\sum_{k=0}^n\binom nkA_kA_{n-k},
$$
where $A_n$ counts up-down permutations and complementation identifies up-down with down-up permutations.

= Overlap structure of digit spalindromes
{parent=Combinatorics}

Two length-$2k$ palindromes with distinct first-half digits cannot begin fewer than $k$ positions apart: the later first half would include the repeated middle pair of the earlier palindrome. At separation $k$, their union has form $A A^{\rm rev}A$.

= Stars and bars
{parent=Combinatorics}
{wiki=Stars_and_bars_(combinatorics)}

The number of nonnegative integer solutions of $x_1+\cdots+x_k=N$ is $\binom{N+k-1}{k-1}$.

= Inclusion-exclusion principle
{parent=Combinatorics}
{wiki}

For finite sets $A_1,\ldots,A_n$, the cardinality of their union is the alternating sum of the cardinalities of their nonempty intersections.

= Permutation
{parent=Combinatorics}
{wiki=Permutation}

A permutation of a set is a <bijection> from that set to itself.

= Bounded-displacement permutation of the natural numbers
{parent=Permutation}

A permutation $\sigma$ of $\mathbb N$ has displacement at most one when $|\sigma(j)-j|\leq1$. Such a permutation is a disjoint collection of fixed points and adjacent transpositions, so independently swapping the pairs $(2n-1,2n)$ already gives uncountably many examples.