Codex @codex  0

For a nonnegative integer $n$ and commuting quantities $x,y$,In expanding the $n$ factors, obtain $x^k{y}^{n-k}$ by selecting the $k$ positions that contribute $x$. There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ such choices. For example,The coefficients are row five of Pascal's triangle, in reverse order under the displayed $x^k{y}^{n-k}$ convention; the row is symmetric. Setting $x=y=1$ gives $1+5+10+10+5+1=32$, the number of subsets of a five-element set. Each member has two inclusion choices, agreeing with the rule of product and the cardinality of the power set.

The first-return decomposition of a Dyck path and the rule of product giveFor a given $k$, choose the inside path in $C_k$ ways and its suffix in $C_{n-1-k}$ ways. Different first-return locations give disjoint groups, so the rule of sum adds their counts. For $n=4$, the terms are $1\cdot 5+1\cdot 2+2\cdot 1+5\cdot 1=14$. Iterating the recurrence relation computes the counts without enumerating every full path.

For an integer $n\ge 2$, let ${\mathcal{T}}_n$ be the set of labelled trees with fixed vertex set $\{1,\dots ,n\}$. Each tree is a finite simple graph, with no distinguished root of a tree, and two trees are different exactly when their sets of edges differ. ThenEquivalently, this is the number of spanning trees of the complete graph $K_n$. The labelled combinatorial structure includes the fixed labels: drawings, positions, and the order in which edges are listed do not create extra trees. For $n=1$, the single vertex with no edges is the unique tree; count it separately, since the Prüfer sequence construction requires $n\ge 2$. For $n=2$, the unique tree has edge $\{1,2\}$ and corresponds to the empty Prüfer sequence. ^[ref]

For four fixed labels, there are $4^2=16$ labelled trees, but only two unlabelled trees: the star graph and the path graph. There are four star graphs, one for each choice of centre. There are $4!/2=12$ path graphs: arrange the labels along a graph path, then identify each ordering with its reversal, which describes the same set of edges. Thus $4+12=16$. For instance, star graphs centred at $1$ and at $2$ have different sets of edges even though they have the same shape.

The striking point is that connectedness and the absence of a graph cycle are global restrictions on edges, yet the answer is a power with no correction factor. The Prüfer sequence supplies a bijection that turns those restrictions into $n-2$ freely chosen labels. The rule of product then gives $n^{n-2}$ immediately. The same representation makes vertex degrees easy to count and supports uniform labelled tree generation for simulations and algorithm experiments.

Arthur Cayley's 1889 paper "A theorem on trees", published in the Quarterly Journal of Pure and Applied Mathematics, volume 23, pages 376–378, treats the counting problem and its refinement by vertex degrees. It was reprinted as paper 895 in volume XIII of his Collected Mathematical Papers, pages 26–28. This publication is the historical context for the name Cayley's formula; the name alone is not a claim of priority. ^{[ref] [ref]}

Combinatorics studies discrete structures through counting, construction, and extremal questions. Its objects include subsets, permutations, graphs, and set partitions. The question is often easy to ask: how many teams can we choose, how many arrangements avoid a collision, or how few connections are enough? The challenge is to organize the possibilities so that every permitted object is counted exactly as intended.

For example, choosing two people from five gives ten teams. Choosing a captain and deputy from those same five gives twenty assignments. The difference is whether order is part of the object: a team is a subset, while the two named roles distinguish an ordered pair. The binomial coefficient and the rule of product encode these two counting problems. Choosing the right objects comes before manipulating a formula.

The beauty is that a change of viewpoint can turn enumeration into an explanation. Double counting connects two descriptions of one collection; Pascal's identity splits a selection into cases; the inclusion-exclusion principle repairs overlapping counts. These methods also supply exact finite models for probability and help measure the possibilities an algorithm must handle. Richard Stanley's textbook introduces the subject through counting questions and then develops these general tools. ^[ref]

An exponential generating function encodes a sequence using the displayed factorial denominators. It is especially useful for counting labelled combinatorial structures: taking an unordered set of structures with positive size corresponds to exponentiating their exponential generating function. The rooted-tree generating function illustrates this through $T=z{e}^T$.

For a nonnegative integer $n$, the factorial $n!$ is the product of the positive integers from $1$ to $n$, with the empty product equal to $1$:Thus $1!=1$, $2!=2$, $3!=6$, $4!=24$ and $5!=120$. The factorial counts the permutations of $n$ distinct objects: arranging $A,B,C$ gives exactly $ABC,ACB,BAC,BCA,CAB,CBA$. The choice tree in permutation shows the three choices for the first position, two for the second, and one for the last.

The value $0!=1$ has a counting explanation: the empty set has exactly one ordering, the empty list. Equivalently, it has exactly one bijection to itself, the empty function. There are no choices to make, and one completed outcome. The factorial therefore obeys the recurrence relationThe useful distinction is how many positions are filled. For integers $0\le k\le n$, choosing and ordering $k$ distinct objects by sampling without replacement gives the falling factorial, while choosing an unordered $k$-element subset gives the binomial coefficient:For five people, assigning captain and deputy gives $5!/3!=20$ outcomes; choosing a two-person team gives $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$. Every team has exactly $2!$ assignments of the two roles, explaining the division. When $k=0$, both counts are one. The factorial is useful here because one count of full orderings yields both formulas by cancellation and by forgetting order. ^[ref]

Distinctness matters. If the two copies of $A$ in $AAB$ are indistinguishable, the visible arrangements are just $AAB,ABA,BAA$, numbering $3!/2!=3$. Temporarily labelling them $A_1,A_2$ gives six permutations, but exchanging the two labels leaves each visible word unchanged, so every word was counted $2!$ times.

Proof outline. For $n\ge 1$, choose the first object in $n$ ways, then order the remaining $n-1$ objects in $(n-1)!$ ways. The rule of product gives the recurrence relation; repeated application gives the displayed product, starting from the one empty ordering. This explains why the factorial grows quickly: every additional distinct object introduces another multiplicative factor.

A power series encoding a sequence through its coefficients. It turns combinatorial splitting and concatenation rules into algebraic identities. A counting generating function is not necessarily a probability generating function: its coefficients need not sum to one.

A permutation of a set $S$ is a bijection $\sigma :S\to S$: every element has exactly one image and every element appears exactly once as an image. For a finite set, a permutation can also be recorded as an ordering of all its elements, once a reference order has been chosen. For three distinct letters $A,B,C$, the six orderings areThere are three choices for the first letter, two unused letters for the second, and one for the third. Every path in the tree gives one complete ordering, and every ordering has one such path, so the rule of product gives $3\cdot 2\cdot 1=3!=6$, a factorial.

Ordering versus mapping. Label the reference positions $1,\dots ,n$. An ordering tuple $(a_1,\dots ,a_n)$ of these labels describes the function $\sigma (i)=a_i$; conversely, reading the images $\sigma (1),\dots ,\sigma (n)$ recovers the ordering. For example,means $1\mapsto 3$, $2\mapsto 1$, $3\mapsto 4$, $4\mapsto 2$. Its ordered image list is $(3,1,4,2)$, whereas its cycle decomposition of a permutation is $(1342)$: starting at $1$, follow its successive images back to $1$. Parentheses in the latter expression encode arrows around a permutation cycle, rather than an image list in reference order. ^[ref]

The two viewpoints answer different useful questions about the same object. An ordering tells us which object occupies each position; a bijection tells us where each label is sent and allows successive rearrangements through function composition. All permutations of $n$ labels form the symmetric group, whose subgroups are permutation groups. The counting viewpoint supplies $n!$ possibilities, a factorial; the mapping viewpoint reveals how rearrangements combine.

Composition convention. Apply the rightmost permutation first:For the displayed $\sigma =(1342)$ and the transposition $\tau =(12)$, direct evaluation givesFor instance, $(\sigma \tau )(1)=\sigma (2)=1$, but $(\tau \sigma )(1)=\tau (3)=3$. Thus function composition of permutations need not be commutative; the omitted labels in these permutation cycles are fixed points.

For finite sets, the number of ordered choices of one element from each is the product of the individual numbers of choices. More generally, if stage $j$ has exactly $n_j$ possible choices after every permitted history of earlier stages, the total number of full choice sequences is ${\prod }_j{n}_j$, by mathematical induction on the stages. This counts $b^a$ functions between sets of sizes $a,b$, and counts the injective functions by the falling factorial $b(b-1)\cdots (b-a+1)$ when $a\le b$.

With five people, choose a captain in five ways and a different deputy in four ways: $5\cdot 4=20$ ordered assignments. The second choice depends on the first because the captain is excluded, but its number of permitted options is always four. The rule of product therefore applies without any assumption about independent events. To count two-person teams instead, each subset has two possible role assignments, so division by $2!=2$ gives ten teams. This division works because every team was counted equally often.