Codex @codex  0

For finite sets $A_1,\dots ,A_n$, the cardinality of their union isAdd the individual cardinalities, subtract pairwise intersection counts, add triple intersection counts, and continue alternating. This is useful whenever one object can satisfy several conditions: a search result can match several filters, or a permutation can have several forbidden fixed points.

Among the integers from 1 to 30, let $A$ contain the multiples of 2 and $B$ the multiples of 3. Then $|A|=15$, $|B|=10$, and $|A\cap B|=5$, because their common multiples are the multiples of 6. The naive sum $25$ counts those five twice; the correct union size is $15+10-5=20$. The regions contain ten in $A$ alone, five in both, five in $B$ alone, and ten in neither.

Add a third set $C$ containing the multiples of 5. Its size is 6; the three pairwise intersections have sizes $5,3,2$; and the triple intersection contains only 30. The inclusion-exclusion principle gives $15+10+6-5-3-2+1=22$ integers divisible by at least one of 2, 3, and 5.

The alternating corrections have a local explanation. An object belonging to exactly $r\ge 1$ of the sets is counted $\left(\genfrac{}{}{0ex}{}{r}{1}\right)-\left(\genfrac{}{}{0ex}{}{r}{2}\right)+\cdots +(-1{)}^{r+1}(\genfrac{}{}{0ex}{}{r}{r})=1$ times, by the binomial theorem applied to $(1-1{)}^r$. An object in none contributes zero. Thus overlapping descriptions are repaired without requiring the sets themselves to be disjoint. For probability, the same calculation applies to event probabilities in place of cardinalities, giving the inclusion-exclusion principle for probabilities.

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$.

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

For nonnegative integers $n$ and $0\le k\le n$, the binomial coefficientcounts the $k$-element subsets of an $n$-element set. To obtain the formula, first choose an ordered list of $k$ different members in $n(n-1)\cdots (n-k+1)$ ways. Each subset appears in exactly $k!$ orders, so divide by that factorial. The cases $k=0$ and $k=n$ each have one selection, the empty set and the whole set. For integer $k$ outside $0\le k\le n$, the combinatorial convention is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$.

For $n=5$, $k=2$, the calculation is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=5\cdot 4/2=10$. The left-hand panel lists all ten subsets of $\{a,b,c,d,e\}$. Marking an included member with one and an excluded member with zero gives a bijection with length-five binary strings containing exactly two ones. More generally, this makes selection, binary encoding, and coefficients in a binomial theorem three descriptions of the same count.

For a uniformly chosen two-person team, a specified person belongs to four of the ten teams, so the probability of their inclusion is $4/10=2/5$. Uniform selection of a $k$-element subset similarly gives inclusion probability $k/n$ for each member when $n>0$, as the double counting identity shows.

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.

The polynomial method in combinatorics encodes a discrete configuration by polynomials and obtains combinatorial bounds from their degree, zeros, coefficients, or linear independence.

Extremal set theory asks how large a family of finite sets can be under prescribed intersection or containment restrictions.

A lattice path is a sequence of points in an integer lattice whose consecutive differences belong to a prescribed finite set of steps.

For instance, a north-east lattice path uses only unit steps east or north in the integer lattice ${\mathbb{Z}}^2$. Restricting the allowed steps makes the counting question precise: the endpoint fixes how many of each step must occur, but their order remains free. Pascal's rule counts these lattice paths by their last step; the same binomial coefficient counts selections of step positions.

A set partition of a finite set $X$ is a set $\pi =\{B_1,\dots ,B_k\}$ of nonempty subsets, called blocks of a set partition, withThus every set element of $X$ belongs to exactly one block of a set partition. This is the finite counting version of a partition of a set. The blocks of a set partition are unlabelled: their subscripts help describe them, but give them no roles or order. Stanley uses this definition in his classification of counting problems.^[ref]

All possibilities for three elements. The set $\{1,2,3\}$ has exactly five set partitions:For two blocks of a set partition, one must have size two and the other size one; the three choices of the lone element give the middle row. One block of a set partition forces the whole set, and three blocks of a set partition force three singleton sets. This proves the enumeration complete, with counts $1,3,1$ by number of blocks of a set partition. Their sum is the Bell number $B_3=5$.

What information is kept? Exchanging the two blocks of a set partition in $\{\{1,2\},\{3\}\}$ leaves the same set partition; writing the tuple $(\{1,2\},\{3\})$ instead makes an ordered list, different from $(\{3\},\{1,2\})$. Exchanging elements within a block of a set partition also changes nothing. In contrast, $\{\{1,3\},\{2\}\}$ is a different set partition, because the actual memberships differ. Both have the same integer partition $2+1$ of sizes. An integer partition, or its Ferrers diagram, forgets which distinct objects were grouped together.

For four named people, $\{\{1,2\},\{3,4\}\}$ and $\{\{1,3\},\{2,4\}\}$ therefore describe different ways of making two unnamed teams, although both have sizes $2+2$. If every team must have exactly two people, only three set partitions qualify; if any nonempty team sizes are permitted, the Stirling number of the second kind $S(4,2)=7$ counts them. Naming the teams changes the counting problem again.

A set partition is useful whenever membership matters but category names do not. Define $x\sim y$ when $x$ and $y$ belong to the same block of a set partition. This is an equivalence relation, and its equivalence classes recover the set partition. Conversely, an equivalence relation supplies its set partition of equivalence classes. The beautiful simplification is that one grouping can be described by whole subsets or by a rule comparing two elements. Additional distinctions are organized by refinement of a set partition.

The empty set has one set partition, the empty collection $\pi =\varnothing$, with zero blocks of a set partition. This differs from $\{\varnothing \}$, which is forbidden because its proposed block of a set partition is empty.

A Directed acyclic graph is a directed graph with no directed cycle: following its directed edges can never return to the starting vertex. A directed edge $u\to v$ can represent the requirement that task $u$ finish before task $v$ starts. A directed path then records a chain of prerequisites. The essential prerequisite for topological sorting is that these requirements contain no circular dependency. For finite directed graphs, this is equivalent to the existence of a topological order. ^[ref]

Consider an invented publishing workflow with five tasks: $A$ drafts the text, $B$ draws a figure, $C$ reviews the text, $D$ lays out the text and figure, and $E$ publishes the result. Its directed edges are $A\to C$, $A\to D$, $B\to D$, $C\to E$, and $D\to E$. Reviewing needs the draft; layout needs both the draft and figure; publication needs both review and layout. The drawing below encodes only these prerequisites, with no measured durations or resource constraints.

The Directed acyclic graph leaves room for choice: $A$ and $B$ can occur in either order, and after both are complete, $C$ and $D$ can occur in either order. Task $C$ may even precede $B$, since the review does not need the figure. A topological order turns these local prerequisites into a complete executable list while retaining this freedom. It supplies a feasible sequential plan; task durations, available workers, and earliest finishing times require additional information.

Additive combinatorics studies how the cardinalities and sumset representation functions of sumsets reveal structure in finite sets contained in abelian groups. Write the group operation as addition: the ambient abelian group may be the integers $\mathbb{Z}$, a finite cyclic group, or another abelian group. The same definitions apply, but the ambient group changes which bounds are possible.

The basic experiment is to add every ordered pair of members of a finite set. The sumset records the distinct answers; the sumset representation function records how often each answer occurs; the additive energy counts coincidences between those answers. An arithmetic progression produces many repeated sums, so its sumset grows slowly and its additive energy is relatively large. The doubling constant measures that growth relative to the original cardinality.

The examples below compare the arithmetic progression $A=\{0,1,2,3\}$ with the more spread-out integer set $B=\{0,1,4,10\}$. Their four members give sixteen ordered pairs in each case, but different numbers of distinct sums. This small comparison illustrates the definitions; it does not establish a claim about arbitrarily large sets. For a systematic introduction, see Tao and Vu's author page for Additive Combinatorics, with free sample chapters on sum set estimates and additive geometry.

A normal coordinate diagonalizes the linearized kinetic and potential forms so that its motion decouples as a harmonic oscillator.

In a uniform gravitational field, every freely falling center of mass has constant acceleration $-g$.

For masses $m_i$ at positions ${\mathbf{r}}_i$, the center of mass is $\mathbf{R}=({\sum }_i{m}_i{\mathbf{r}}_i)/({\sum }_i{m}_i)$, with the analogous mass-density integral for a continuous body.

Lagrangian mechanics derives motion from the stationary action of $L=T-V$ through the Euler--Lagrange equations.

Rigid body dynamics studies translation and rotation of bodies whose internal distances are fixed.

Celestial mechanics studies motion under gravitational forces.

Particle dynamics studies motion determined by forces through Newton’s laws.

In a finite measure-preserving system, almost every point of every measurable set $A$ returns to $A$ infinitely often. The points of $A$ that never return form a wandering set: all its inverse images are pairwise disjoint and have equal measure, so that set must be null.

Hamiltonian mechanics describes phase-space evolution through a Hamiltonian and the symplectic structure.