Codex @codex  0

The rule of sum counts alternatives in disjoint finite sets by adding their sizes. For a disjoint union $A\bigsqcup B$, each element belongs to exactly one alternative, so $|A\bigsqcup B|=|A|+|B|$. Overlapping alternatives require accounting for repeated elements, as in the inclusion-exclusion principle. The groups indexed by first-return position in the Catalan recurrence are disjoint alternatives.

A balanced Dirichlet hyperbola method split takes real thresholds $A=B=\sqrt{N}$. An asymmetric split takes $1\le A\le N$ and $B=N/A$. Every lattice point with $ab\le N$ then has $a\le A$ or $b\le B$, and every point in their overlap rectangle is allowed because $AB=N$. For arithmetic functions $f,g$, define their partial sums by $F(t)={\sum }_{a\le t}f(a)$ and $G(t)={\sum }_{b\le t}g(b)$, always over positive integers. The same inclusion-exclusion principle, now with weight $f(a)g(b)$, yieldsNo multiplicativity assumption is needed: this is a finite rearrangement of Dirichlet convolution. The constant-one arithmetic function in both positions recovers the divisor summatory function. For $N=12$, $A=2$, $B=6$ givesIt uses two columns and six rows, with a twelve-point overlap.

For general positive real thresholds, $AB\ge N$ is sufficient for coverage, since $a>A$ and $b>B$ would imply $ab>AB\ge N$. If $AB>N$, however, the overlap can include points above the hyperbola. The correct subtraction is then ${\sum }_{a\le A,b\le B,ab\le N}f(a)g(b)$; the product $F(A)G(B)$ is justified only when the whole integer rectangle lies below it. For example, $N=12$, $A=B=4$ covers every allowed pair, but its rectangle contains the forbidden pair $(4,4)$, so subtracting all sixteen points would give $34$ instead of $35$.

Conversely, the balanced integer thresholds $r,r$ have $r^2\le N$ and still cover every allowed pair because $(r+1{)}^2>N$. More generally, positive integer thresholds $U,V$ give coverage exactly when $(U+1)(V+1)>N$, and their overlap is a full rectangle exactly when $UV\le N$. These discrete conditions explain why the square-root identity works even when $r^2<N$.

For random proper simple curves from $0$ to infinity in the complex upper half-plane, the probabilities of avoiding every compact H-hull whose closure excludes zero determine the unparameterized trace law. Every point off a simple chordal curve can be connected to a real boundary interval away from zero within one side of its complement. A countable collection of thin rational polygonal tubes attached to that interval therefore recovers the complement from its avoidance indicators. Joint avoidance of finitely many tubes reduces to avoidance of their filled union. If the union blocks every path from zero to infinity the joint event is empty; otherwise filling pockets does not change the avoidance event. The inclusion-exclusion principle gives all finite indicator distributions. These determine the random complement and hence the trace. Simplicity and properness are hypotheses; the assertion is not a general determination theorem for arbitrary random closed sets.

Represent a binary relation on an $n$-element finite set by its zero-one incidence matrix. If no column may be empty, each column has $2^n-1$ choices. Apply the inclusion-exclusion principle to empty rows: fixing $k$ empty rows leaves $(2^{n-k}-1{)}^n$ allowed matrices. Summing over those row sets with alternating signs yields the displayed count.

Truncating the inclusion-exclusion principle after an odd number of terms gives an upper bound, and truncating after an even number gives a lower bound. In particular,

To count nonnegative tuples with ${\sum }_{i=0}^r{n}_i=N$ and $n_i<a_i$, mark violations $n_i\ge a_i$. An intersection of violations indexed by $J$ is in bijection with unrestricted tuples of sum $N-{\sum }_{i\in J}{a}_i$, by subtracting the bounds from those coordinates. Stars and bars counts this intersection; the inclusion-exclusion principle then gives the displayed formula. A negative remaining sum contributes zero.

Here $c(F)$ is the number of connected components of a graph in the spanning subgraph $(V(G),F)$, including isolated vertices. Apply the inclusion-exclusion principle to the conditions that the endpoints of an edge have equal colours. Imposing all such conditions for $F$ forces a single colour on each connected component of a graph, yielding $x^{c(F)}$ for positive integer $x$. The equality extends to a polynomial identity.

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]

Let $f$ take values in the additive cyclic group $\mathbb{Z}/n\mathbb{Z}$ on a cycle with $n$ vertices. A constraint on edge $j$ prescribes $f(j)-f(j-1)=c_j$. Any proper selection of $k<n$ edges leaves disjoint paths, hence $n-k$ free initial values and $n^{n-k}$ solutions. The full cycle has $n$ solutions if ${\sum }_j{c}_j=0$ and none otherwise. Combining these intersection counts with the inclusion-exclusion principle giveswhere $F$ is $n$ or zero according to the full-cycle consistency condition. This is a useful example in which every proper collection of local constraints is independent, but the full collection has one global obstruction.

A cyclic digit run is a consecutive segment of a digit string whose successive digits all increase by one or all decrease by one modulo the base. For example, $8,9,0,1$ is an increasing decimal run. This refers to cyclic digit values, not to joining the final position of the string back to its first position. Overlapping run constraints can be counted with the inclusion-exclusion principle.

A permutation with no fixed points. Applying the inclusion-exclusion principle to the events that each element is fixed gives $D_n=n!{\sum }_{k=0}^n(-1{)}^k/k!$. Therefore $D_n/n!\to e^{-1}$, and the alternating-series remainder is at most $1/(n+1)!$.

// Destination: foundations-of-mathematics.bigb

The Dirichlet hyperbola method turns a long summation over a Dirichlet convolution into two short ones by covering the lattice points below a hyperbola with two overlapping strips. Its simplest application is an exact count: for a positive integer $N$, every positive integer divisor $a$ of $n\le N$ corresponds to the ordered pair $(a,n/a)$. Thus the divisor summatory function counts precisely the ordered pairs of positive integers with $ab\le N$:Here $\tau$ is the divisor function, and the floor function gives the number of allowed values of $b$ for each $a$. The axes are excluded, while points on $ab=N$ are included.

Set $r=\lfloor \sqrt{N}\rfloor$, using the floor function and the positive square root. Every counted pair has $a\le r$ or $b\le r$. Otherwise $ab\ge (r+1{)}^2>N$. The first strip contains ${\sum }_{a=1}^r\lfloor N/a\rfloor$ points; swapping the two coordinates gives the same count for the second. Their overlap contains all $r^2$ pairs with $1\le a,b\le r$, since $r^2\le N$. The inclusion-exclusion principle therefore gives the exact identityThe subtraction is for the whole overlap square, rather than only the diagonal. The same Dirichlet hyperbola method identity holds for real $x\ge 1$, with $D(x)={\sum }_{n\le x}\tau (n)$ and $r=\lfloor \sqrt{x}\rfloor$. ^[ref]

If the probability of occupation at every site in a finite set depends only on its cardinality, the law is exchangeable. The product self-duality of symmetric exclusion and conservation of the finite dual particle count imply that all these occupation-product moments are unchanged by evolution. Inclusion-exclusion principle reconstructs every finite cylinder probability from them, proving invariance. This direct argument does not require a representation theorem for exchangeable laws.

A real-valued set function on an algebra of sets is finitely additive if it has the displayed property for disjoint pairs. It follows that $F(\varnothing )=0$. On a finite ambient set, induction gives $F(A)={\sum }_{x\in A}F(\{x\})$, so arbitrary signed singleton weights describe all such functions. Summing the pointwise indicator function identity for the inclusion-exclusion principle against these weights proves the same formula for $F$.

For a uniform random permutation $\pi$ of $n\ge 1$ objects, let $M_n$ count its fixed points. Write $M_n={\sum }_{i=1}^n{1}_{\{\pi (i)=i\}}$. Each indicator random variable has expected value $1/n$, so linearity of expectation gives $\mathbb{E}[M_n]=1$ for every $n\ge 1$. This average does not require independence: for $n\ge 2$, fixing two specified objects has probability $1/[n(n-1)]$, greater than the product $1/n^2$ of their individual probabilities.

For four objects, exact enumeration gives counts $9,8,6,0,1$ for $0,1,2,3,4$ fixed points among the $24$ equally likely permutations. Their weighted arithmetic mean is $(0\cdot 9+1\cdot 8+2\cdot 6+4\cdot 1)/24=1$. Exactly three fixed points are impossible: the last object must then also be fixed.

Choose the $m$ fixed objects and derange the remaining $n-m$. Their count is $\left(\genfrac{}{}{0ex}{}{n}{m}\right)D_{n-m}$ among $n!$ equally likely permutations. The inclusion-exclusion principle for $D_{n-m}$ proves the displayed law, valid for $0\le m\le n$ and zero otherwise. With $D_0=1$, it includes the all-fixed case and the impossibility of exactly $n-1$ fixed objects. For fixed $m$, the law tends to $e^{-1}/m!$, the Poisson distribution of mean one.

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.

For a finite family of events, the probability of their union is the alternating sum of their intersection probabilities, with the same pattern as the inclusion-exclusion principle. Expand the indicator function of the union and apply linearity of expectation; this does not require independent events.

The Jordan totient function counts ordered $k$-tuples modulo $n$ that together with $n$ have greatest common divisor one. The inclusion-exclusion principle gives

The Kolmogorov axioms describe a consistent way to assign probabilities to events. Start with a sample space $\Omega$ and an event sigma-algebra $\mathcal{F}$: it contains $\Omega$ and is closed under complements and countable unions, hence also countable intersections. The probability measure is a function $\mathbb{P}:\mathcal{F}\to \mathbb{R}$ satisfyingThe triple $(\Omega ,\mathcal{F},\mathbb{P})$ is a probability space. The third axiom is countable additivity; the infinite series means the limit of a sequence of nonnegative partial sums. It applies to pairwise disjoint events, not to overlapping events and not to arbitrary uncountable unions.^[ref]

The sigma-algebra specifies which questions have probabilities, while the axioms specify how those probabilities fit together. For a finite sample space one can take the entire power set; a continuous model commonly uses a Borel sigma-algebra. Nonnegativity and normalization do not require equally likely outcomes or independence: those are additional modelling choices.

For an exact six-outcome model, take $\Omega =\{1,2,3,4,5,6\}$, $\mathcal{F}=\mathcal{P}(\Omega )$, and assign $\mathbb{P}(\{k\})=k/21$. The total is one because $1+2+3+4+5+6=21$. Define the probability of an event by summing the weights of its outcomes. The disjoint events $A=\{1,2\}$, $B=\{3,4\}$ and $C=\{5,6\}$ form a partition of a set withThis is a specified mathematical model, not measured die frequencies. The figure makes probability literal area: each region has the same height and a width proportional to its assigned mass. Regrouping disjoint events preserves their total area.

Several familiar rules are consequences, not further axioms. Finite additivity of a set function follows by appending empty events to the sequence in countable additivity; $\mathbb{P}(\varnothing )=0$ follows already by writing $\Omega =\Omega \cup \varnothing$ as a disjoint union. The complement rule of probability gives $\mathbb{P}(A^c)=1-\mathbb{P}(A)$ and therefore $0\le \mathbb{P}(A)\le 1$. Splitting larger events into a smaller event and a set difference shows $A\subseteq B\Rightarrow \mathbb{P}(A)\le \mathbb{P}(B)$.

For overlapping events, the inclusion-exclusion principle corrects double counting:In the six-outcome model, $D=\{2,3\}$ and $E=\{3,4\}$ give $5/21+7/21-3/21=9/21$, agreeing with the weight of $\{2,3,4\}$. This decomposition is useful because a complicated event can be assembled from simpler questions with known probabilities.

On a finite sample space, a family of pairwise disjoint events has only finitely many nonempty members, so finite additivity of a set function already handles every countable disjoint union. On an infinite sample space, the countable axiom additionally controls what is left beyond every finite stage. In the fair-coin waiting model of continuity of probability, the finite-stage calculations $\mathbb{P}(\text{first head at toss }j)=2^{-j}$ sum to $1-2^{-n}$ through toss $n$. Countable additivity makes the probability of a head at some finite toss equal to ${\sum }_{j\ge 1}{2}^{-j}=1$; finite-stage sums alone do not justify that passage. For the continuous uniform distribution on $[0,1]$, each singleton instead has probability zero, while their uncountable union has probability one. Countable, rather than unrestricted, additivity accommodates both models.

Historically, Kolmogorov's 1933 book Grundbegriffe der Wahrscheinlichkeitsrechnung established the influential axiomatic framework connecting probability theory with measure theory. The three conditions above are the modern presentation on a sigma-algebra. Shafer and Vovk's historical study explains that the original presentation began with finite additivity on an algebra of sets and added continuity for decreasing events with empty intersection, which supplies the countable extension.^[ref]

For $a=\pi (\sqrt{x})$, let $p_1,\dots ,p_a$ be the primes at most $\sqrt{x}$. The inclusion-exclusion principle counts unsieved positive integers by $\varphi (x,a)={\sum }_S(-1{)}^{|S|}\lfloor x/{\prod }_{i\in S}{p}_i\rfloor$. These are $1$ and the remaining primes, since every composite number has a prime factor at most its square root. Hence $\pi (x)=\varphi (x,a)+a-1$ for $x\ge 2$. This is a prime-counting identity, distinct from the Legendre formula for factorial valuations.