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 $A(z)={\sum }_{n\ge 0}{a}_n{z}^n/n!$. For labelled counting, $a_n$ is the number of structures on a fixed set of $n$ distinct labels. Labels distinguish otherwise similar objects: changing which person belongs to a group can change the structure. Recover the count by coefficient extraction as $a_n=n![z^n]A(z)$. The raw coefficient is $a_n/n!$, not $a_n$.

The factorial makes multiplication account automatically for distributing labels. To combine an $A$-structure on $k$ labels and a $B$-structure on the remaining $n-k$, choose the first label subset in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways, then choose the two structures. The binomial coefficient counts how the two groups of labels interleave within the full label set. ThusThe normalization works because $1/(k!(n-k)!)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)/n!$. This explains the usefulness of exponential generating functions for labelled counting: an ordinary Cauchy product would omit the choices of labels. See Peter Magyar, Math 482, notes for 2/7, labelled product principle.

For a concrete example, there is one undecorated set on any given collection of labels. Its exponential generating function is the exponential function $E(z)=e^z={\sum }_{n\ge 0}{z}^n/n!$. Combine a red set and a blue set, allowing either to be empty:Every label independently receives one of two colours, giving $2^n$ assignments by the rule of product. With three labels, the counts by number of red labels are $1,3,3,1$, totalling eight. Choosing only the two group sizes would give the four possibilities $(0,3),(1,2),(2,1),(3,0)$; it would forget which labels are red.

Indeed, the ordinary generating function for the constant sequence $a_n=1$ is the geometric series $1/(1-z)$. Its square has coefficient $[z^n](1-z{)}^{-2}=n+1$, counting pairs of nonnegative sizes. Both encodings are correct for their respective questions. The decision is whether identity matters when objects are combined.

For unordered sets of labelled components of positive size, an exponential generating function $B(z)$ becomes $e^{B(z)}$: the term $B(z{)}^m/m!$ forgets the ordering of $m$ components. The existing rooted-tree generating function develops the richer example $T=z{e}^T$. A labelled rooted tree consists of its root of a tree and an unordered set of smaller labelled rooted trees, connecting the same label-distribution mechanism to recursive counting.

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 generating function packages a sequence into a series so that operations on objects become operations on their encodings. An ordinary generating function uses the power series $A(z)={\sum }_{n\ge 0}{a}_n{z}^n$; in counting problems, the coefficient $a_n$ records the number of objects of size $n$. The variable $z$ initially marks size: it need not be assigned a numerical value. Coefficient extraction writes this recovery as $[z^n]A(z)=a_n$. One compact expression can therefore answer infinitely many counting questions, while explaining how their answers fit together.

Start with two contributions: choose $i$ from $\{0,1,2\}$ and $j$ from $\{0,1\}$, with exactly one option at each allowed value. Their individual ordinary generating functions are the polynomials $P(x)=1+x+x^2$ and $Q(x)=1+x$. To count ordered pairs by total $i+j$, multiply:The coefficients $1,2,2,1$ count the ways to obtain totals zero through three. For total two, the possibilities are $(1,1)$ and $(2,0)$; the two corresponding monomials both contribute $x^2$. There are six ordered pairs altogether, agreeing with $P(1)Q(1)=3\cdot 2=6$.

If the first contribution has two distinguishable choices when $i=1$, replace $P(x)$ by $1+2x+x^2$. Its product with $Q(x)$ becomes $1+3x+3x^2+x^3$. The coefficients now carry multiplicities as well as possible totals; the exponent still records cost. This lets the same construction handle several actions with identical costs without losing their separate identities.

In general, the Cauchy product givesFor each split of the total size, the rule of product counts the choices of the two components; summing over those splits counts all possibilities. This requires each combined object to have a unique decomposition into the two components. The same idea works for costs, lengths, or other additive measures, not just the number of pieces. See MIT 18.310, generating functions, sections 1–2.

Now cover a board of length $n$ with tiles of lengths one and two, without gaps or overlaps. Let $t_n$ count these tilings. There is exactly one empty tiling, so $t_0=1$, and $t_1=1$. Removing the first tile leaves a board shorter by one or two, giving the recurrence relationThese are the Fibonacci numbers shifted by one index: $t_n=F_{n+1}$ under the convention $F_0=0$, $F_1=1$. Keeping the empty tiling is essential to both the counting rule and the resulting ordinary generating function.

For $F(z)={\sum }_{n\ge 0}{t}_n{z}^n$, the empty board or a first tile followed by a remaining tiling givesEquivalently, $F(z)={\sum }_{m\ge 0}(z+z^2{)}^m$: each factor chooses one tile, and $m$ counts pieces while the exponent of $z$ records total length. The same ordinary generating function counts ordered histories of two repeatable actions costing one and two units. Histories $(1,2)$ and $(2,1)$ differ despite having the same total cost. MIT's notes use dots and dashes with these costs, including the empty message. ^[ref]

These identities hold in formal power series algebra: each requested coefficient uses only finitely many contributions. The repeated-choice expansion is legitimate because $z+z^2$ has zero constant term; a zero-cost repeatable action would allow infinitely many histories of the same size. Numerical evaluation separately requires a convergent series. Here the radius of convergence is $(\sqrt{5}-1)/2$, the reciprocal of the golden ratio. At $z=1$, the rational function equals $-1$, but the counting series diverges: that value cannot represent its sum.

Other generating functions change the encoding: an exponential generating function divides by factorials, while a Dirichlet series uses $n^{-s}$. A counting generating function also differs from a probability generating function, whose coefficients must be nonnegative and sum to one.

Row $n$ of Pascal's triangle consists of the binomial coefficients $\left(\genfrac{}{}{0ex}{}{n}{0}\right),\dots ,\left(\genfrac{}{}{0ex}{}{n}{n}\right)$, beginning with row $0$. Boundary entries are one, and Pascal's identity says each interior entry is the sum of the two entries above it. The hockey-stick identity evaluates sums along its diagonals.

The highlighted entry in the binomial coefficient illustration is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$. Split two-person teams according to whether they contain the fifth person: six choose both members from the other four, and four contain the fifth person together with one of those four. Thus $10=6+4$. All entries can be generated by the same local rule, so a large table of counts needs no repeated enumeration of its subsets.

Reading row seven. Label the entries in each row from $k=0$ on the left through $k=n$ on the right. Rows zero through seven are shown below. The highlighted entry $T_{7,3}=35$ comes from $T_{6,2}=15$ and $T_{6,3}=20$. Starting with row zero $(1)$, the edges remain one and Pascal's rule determines every interior entry, so mathematical induction uniquely determines the whole array.

The triangular and rectangular layouts describe the same entries. For a north-east lattice path ending at $(a,b)$, set $n=a+b$ and $k=b$, so $P(a,b)=T_{n,k}$. The predecessor $(a-1,b)$ has indices $(n-1,k)$, while $(a,b-1)$ has indices $(n-1,k-1)$. Thus the grid's west and south arrivals are exactly the triangle's two parents. This change of indices explains why the north-east lattice path recurrence and Pascal's rule agree.

There is also a global check on the local construction: row $n$ sums to $2^n$. Every subset of an $n$-element set appears exactly once among the classes of sizes $0,\dots ,n$, and each element has two inclusion choices by the rule of product. In row seven, $1+7+21+35+35+21+7+1=128=2^7$. Replacing every subset by its complement reverses the row, explaining $T_{n,k}=T_{n,n-k}$. The binomial theorem packages the whole row as the coefficients of $(1+x{)}^n$.

Blaise Pascal's Traité du triangle arithmétique, published in 1665, presents an arithmetic array and connects it to combinations, games of chance, and powers of binomial expressions. This makes the connection between a counting table and several applications visible in the original work. ^[ref] The University of Cambridge's account of the treatise explains its 1654 composition and the organization of these applications. ^[ref]

The conventional worst-case estimate is the backtracking leaf bound given by the product of the initial constraint domain sizes. Before exploiting any attacking-queen constraints, the three models give respectivelyModel 1 has $N^2$ binary choices. Model 2 has $N$ labeled queens with $N^2$ possible cells each. Model 3 has $N$ row variables with $N$ possible columns each. The rule of product gives the displayed bounds; assigning variables in one prescribed order avoids multiplying again by the number of variable orderings.

With $k$ mutually nonattacking prescribed queens incorporated as singleton constraint domains, the corresponding bounds improve toIn Model 1 only the $k$ prescribed occupied cells have been fixed in this estimate; immediate deletion of attacked cells tightens it further. In Model 3 consistent clues occupy $k$ distinct rows. If the clues are inconsistent, preprocessing can reject the instance immediately.

These are upper bounds on leaves, rather than exact attained counts for a fully specified pruning implementation. Ordinary backtracking rejects inconsistent partial assignments and often creates far fewer leaves; a stopped branch is itself a leaf even if not all variables were assigned. Such early leaves still obey the backtracking leaf bound, since distinct leaves describe disjoint nonempty families of full domain assignments when constraints are ignored. Counting only possible complete nonattacking assignments is a different question. For example, row/column restrictions alone reduce full assignments to at most $N!$ in Model 3, but that number does not directly count failed partial leaves. Exact counts depend on variable ordering and constraint propagation, neither of which is specified.

A subset is determined uniquely by deciding, for each of the $n$ elements, whether to include it. Each decision has two possibilities. By the rule of product, there are $2\cdot 2\cdots 2=2^n$ decision strings. The correspondence between such binary strings and subsets is a bijection, so $|\mathcal{P}(\mathcal{U})|=2^n$. The all-zero string corresponds to the empty subset.

The rule of product says that a sequence of $k$ choices, with $n_i$ possibilities at stage $i$ regardless of earlier choices, has ${\prod }_{i=1}^k{n}_i$ possible outcomes. Applied to the Cartesian product of finite sets, it gives $|A\times B|=|A||B|$. Here independence means that the available choices do not restrict one another; no probability assumption is needed.

The rule of product counts $7^4$ unrestricted passwords and $6^4$ passwords containing no A. By the rule of subtraction, the answer is

Each of the $n$ elements is either included or excluded, so the rule of product gives $|\mathcal{P}(\{1,\dots ,n\})|=2^n$. Alternatively, partition the power set into disjoint families according to cardinality. The family of $k$-element subsets has size equal to the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. The rule of sum therefore gives

The rule of product says that if a construction has $r$ stages, with exactly $a_j$ choices at stage $j$ after every permitted earlier history, then it has ${\prod }_{j=1}^r{a}_j$ possible outcomes. The later choices need not be identical sets after different histories; their numbers must have the stated values.

For a permutation of $n$ distinct objects, choose the first object in $n$ ways, the second in $n-1$ ways, and continue until only one remains. Thus the number isEvery ordered arrangement is produced exactly once by its successive choices, so this counts permutations without omissions or repetitions. For $n=0$, the unique empty arrangement agrees with $0!=1$.

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.