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

Let $A_n$ count alternating permutations on $n$ labels, with $A_0=1$. For $n\ge 1$,Count both up-down and down-up permutations of $n+1$ labels. Choose the $k$ labels left of the maximum in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways. On either side, the comparison next to the maximum fixes which alternating direction is required, giving $A_k{A}_{n-k}$ choices. Conversely these choices reconstruct exactly one of the two kinds of alternating permutations. Replacing each label $a$ by $n+2-a$ interchanges the two kinds, so their combined count is $2A_{n+1}$.

For $n=1$, the identity reads $2A_2=A_0{A}_1+A_1{A}_0=2$. The restriction $n\ge 1$ matters: on one label, the two alternating conventions describe the same permutation, and substitution of $n=0$ would incorrectly give $2A_1=A_0^2$.

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.

In extremal set theory, a set family $\mathcal{F}\subseteq \mathcal{P}([n])$ is constrained by its intersections, inclusions or traces, and one asks for the largest possible cardinality of $\mathcal{F}$. The choice of constraint is essential: without one, the whole Boolean lattice gives $2^n$ members.

For example, let $n\ge 1$ and require an intersecting family. A set and its complement of a set cannot both belong, so pairing all subsets with their complements gives $|\mathcal{F}|\le 2^{n-1}$. All subsets containing a fixed point attain equality. Adding a uniform-size requirement leads to the Erdős-Ko-Rado theorem.

An antichain instead forbids containment between distinct members. Sperner's theorem gives the sharp central-binomial bound, attained by a full middle level. Coordinate shifts of a set family simplify extremizers while preserving size; the polynomial method in combinatorics turns other intersection restrictions into linear independence. These two methods explain why a problem about subsets can become either an order argument or a vector space dimension bound.

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 measures motion along a particular normal mode of a linearized mechanical system. For small displacements $\mathbf{q}$ about a stable equilibrium, write the kinetic energy and potential energy as quadratic forms with mass matrix $M$ and stiffness matrix $K$. Mode vectors satisfy the generalized eigenvalue problemFor a conservative system with positive definite $M$ and symmetric $K$, mass-orthonormal mode vectors transform the coupled equations of motion into independent equations ${\ddot{Q}}_j+{\omega }_j^2{Q}_j=0$.

Two equal coupled oscillators give a simple example: their sum coordinate describes motion together, and their difference coordinate describes opposite motion. Exciting only one of these patterns leaves the other coordinate zero in the linear approximation. This is useful for interpreting measured resonances and molecular vibrations; large displacements or nonlinear interactions can couple the modes again.

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

The center of mass is the mass-weighted mean position of a system. For particles of fixed masses $m_i$ at position vectors ${\mathbf{r}}_i$,A continuous mass distribution replaces the sums by $\mathbf{R}=M^{-1}\int \mathbf{r}dm$. Two equal masses have their center of mass halfway between them; if one is three times heavier, the center of mass lies one quarter of the separation from the heavier body.

Balancing a rigid bar on a narrow support gives a practical way to locate its center of mass in a uniform gravitational field. For a freely moving closed Newtonian system, the total external force governs the acceleration of its center of mass, allowing its overall translation to be studied separately from internal motion. A center of mass can lie outside the material, as it does at the centre of a uniform ring.

Lagrangian mechanics determines motion from a function $L(q,\dot{q},t)$ and the principle of stationary action. For fixed-endpoint path variations, the action $S=\int Ldt$ gives the Euler-Lagrange equationsFor ordinary conservative mechanical systems in suitable coordinates, $L=T-V$, but velocity-dependent interactions can require additional terms.

A simple pendulum illustrates why generalized coordinates help. Its angle automatically enforces the fixed-length constraint, so varying the angular path gives the tangential dynamics without first solving for the string tension. The action need only be stationary, not necessarily a minimum. Coordinates absent from $L$ give conserved canonical momenta, and a regular velocity dependence allows a transition to Hamiltonian mechanics. These features make the method useful for linked mechanisms and systems with geometric constraints.

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

Celestial mechanics predicts the motion of planets, Moons, stars and spacecraft from gravity and other relevant forces. Its simplest useful approximation is the two-body problem, whose Kepler orbits explain the connection between orbital shape, energy and angular momentum.

Johannes Kepler's orbital description and Isaac Newton's inverse-square law meet in this model. Additional bodies introduce orbital perturbations; general relativity changes the prediction when relativistic corrections matter. Comparing a predicted trajectory with observations tests both the inferred masses and the adopted dynamical model.^[ref]

Particle dynamics predicts the motion of bodies whose internal size and rotation can be neglected for the question being studied. A point particle has a position and mass; applied forces determine its acceleration through Newton's second law. For fixed mass in an inertial frame, the basic problem iswith an initial position and velocity.

A ball's projectile motion can be approximated this way when its size is small compared with its path and spin has negligible influence. Air drag introduces a velocity-dependent force; contact with a surface may introduce mechanical constraints. The same method extends to interacting particles, where momentum conservation and conservation of energy can simplify the coupled equations of motion.

In a finite measure-preserving system, for each measurable set $A$, almost every point of $A$ returns to $A$ infinitely often. The exceptional null set may depend on $A$. To prove the claim, let $W\subseteq A$ consist of points that never return at a positive time. The sets $T^{-n}W$, $n\ge 0$, are pairwise disjoint: a point in two of them would give a future return from one point of $W$ to another point of $A$. They have equal measure by invariance, so finiteness forces $\mu (W)=0$.

A point of $A$ with only finitely many future visits has a last visit, lying in $W$. Such points lie in the countable union ${\bigcup }_{n\ge 0}{T}^{-n}W$, which is null. This completes the infinite-return assertion without requiring invertibility. The theorem supplies no universal return-time bound. On the infinite counting-measure system $T(n)=n+1$ on $\mathbb{Z}$, a singleton never returns, showing why finite total measure matters.

Hamiltonian mechanics describes motion using coordinates $q_i$ and their canonical momenta $p_i$. A Hamiltonian $H(q,p,t)$ generates evolution through Hamilton's equations:The pair $(q,p)$ is a point in phase space; these first-order equations specify its velocity there.

For a spring oscillator, $H=p^2/(2m)+k{q}^2/2$ gives $\dot{q}=p/m$ and $\dot{p}=-kq$, recovering Newton's second law. The formulation treats position and momentum together and makes canonical transformations, Poisson brackets and conservation laws especially useful. An autonomous Hamiltonian is conserved along its motion. The underlying symplectic form also restricts how phase-space regions evolve, leading to Liouville's theorem.