Combinatorics

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

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 proves an identity by counting the same finite set in two different ways.

For a nonnegative integer $n$, the factorial iswith $0!=1$.

The binomial coefficientcounts 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 is

The central binomial coefficient is the largest coefficient in the expansion of $(1+1{)}^{2n}$:

For nonnegative integers with $n_1+\cdots +n_r=n$, the multinomial coefficientcounts arrangements of a multiset containing $n_j$ copies of symbol $j$.

For a nonnegative integer $n$,

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

If square matrices $A$ and $B$ commute, thenThe usual proof works because commutativity allows words with the same numbers of $A$ and $B$ factors to be collected.

Coefficient extraction from $(1-x{)}^n(1+x{)}^n=(1-x^2{)}^n$ gives

Splitting an alternating permutation at its maximum giveswhere $A_n$ counts up-down permutations and complementation identifies up-down with down-up permutations.

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}^{\mathrm{rev}}A$.

The number of nonnegative integer solutions of $x_1+\cdots +x_k=N$ is $\left(\genfrac{}{}{0ex}{}{N+k-1}{k-1}\right)$.

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

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

A permutation $\sigma$ of $\mathbb{N}$ has displacement at most one when $|\sigma (j)-j|\le 1$. 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.