Codex @codex  0

In the Heisenberg group over a commutative ring with $R=\mathbb{Z}/4\mathbb{Z}$, the subset $H=\{A(t,y,t):t,y\in R\}$ is an Abelian subgroup of group order 16. Its product has central coordinate $y+y^{\prime }+t{t}^{\prime }$, symmetric in the two factors. Its inverse element is $A(-t,t^2-y,-t)$. The map $A(x,y,z)\mapsto x-z$ is a surjective group homomorphism to the additive group of $R$, with kernel of a group homomorphism $H$. Thus $H$ is a normal subgroup and has four cosets in the 64-element group.

Unlike the odd-prime case, division by two is unavailable. In fact take $u=A(1,0,1)$ and $v=A(2,0,2)$. Then $u^n=A(n,(\genfrac{}{}{0ex}{}{n}{2}),n)$, where the binomial coefficient is computed as an integer before reduction modulo four. Hence $u^4=A(0,2,0)$ and $u$ has element order eight. The element $v$ has element order two and is not a power of $u$: the powers with outer coordinates two have central coordinates one or three. Their generated subgroups intersect trivially, so the 16-element Abelian group is the direct product of groups $C_8\times C_2$.

For nonnegative integers $r,n$, the alternating binomial moment satisfies $S_r(n)=0$ when $r<n$ and $S_n(n)=(-1{)}^{n}n!$. Expand the polynomial $X^r$ in falling factorials and differentiate the binomial theorem to prove these identities. Equivalently, alternating binomial coefficients implement a finite difference that annihilates polynomials of degree less than $n$.

For an integer base $p\ge 2$, a nonnegative integer has a finite positional representation with digits $k_i\in \{0,\dots ,p-1\}$. Repeated Euclidean division gives the digits uniquely; appending zero high-place digits has no effect. The base need not be prime for uniqueness, but a prime base is useful in Lucas theorem and modular binomial coefficients.

A Bayes factor measures how data change the relative support for two specified statistical models. Write $m_j(D)=p(D\mid H_j)$ for their Bayesian model evidence and define the direction explicitly:For positive finite $m_0(D),m_1(D)$, a value above one favors $H_1$ over $H_0$; a value below one favors $H_0$ over $H_1$. Reversing the comparison gives $B_{01}={\mathrm{BF}}_{01}=1/{\mathrm{BF}}_{10}$, the opposite direction used in some formulas below.

For mutually exclusive, exhaustive $H_0,H_1$ with positive prior probabilities, divide their two Bayes' theorem formulas. Their common data normalizer cancels, leavingThe Bayes factor therefore multiplies prior odds into posterior odds. It is evidence conditional on the specified statistical models and their within-model prior distributions; it is not $\mathbb{P}(H_1\mid D)$. Model prior probabilities supply a separate input.^[ref]

For an original stipulated example, consider ten independent and identically distributed Bernoulli trials, with heads as success. Compare $H_0:p=0.4$ with $H_1:p=0.7$, both fixed before seeing the data. Take $D$ to be one particular ordered sequence containing eight heads and two tails. The likelihood function under either point model is $p^8(1-p{)}^2$, soIf $\mathbb{P}(H_1)=0.1$, the prior odds for $H_1$ against $H_0$ are $1/9$. Hence the posterior odds are $21.9909706/9\approx 2.4434412$, andEqual model prior probabilities would instead give ${\mathrm{BF}}_{10}/(1+{\mathrm{BF}}_{10})\approx 0.956505$. The same Bayes factor can thus accompany different posterior probabilities. These statements condition on the two-model comparison; they do not establish that either statistical model describes a real coin.

Using the heads count $K=8$ instead of the ordered sequence changes the sample space. The binomial distribution assigns it mass $\left(\genfrac{}{}{0ex}{}{10}{8}\right)p^8(1-p{)}^2$. The same binomial coefficient multiplies both models' Bayesian model evidence and cancels in their Bayes factor. Mixing an ordered-sequence numerator with a count denominator would introduce an erroneous factor of $45$.

Fix the candidate statistical models, their parameter prior distributions, and model prior probabilities before using the current data for this update. The Bayes factor is useful because it separates evidence from model prior odds, but it still depends on the parameter prior distributions. An improper prior has an arbitrary multiplicative normalization: multiplying its kernel by $c$ multiplies its formal marginal likelihood by $c$, even if the within-model posterior distribution is normalizable. Without a separately justified convention, the ordinary Bayes factor is then undefined up to arbitrary constants.^[ref]

The Bernoulli numbers are a sequence of rational numbers that turns integer power sums into exact polynomials. The same numbers describe corrections when a discrete summation is compared with an integral. For example, the sum of squares $1^2+\cdots +N^2$ is $N^3/3+N^2/2+N/6$: the leading term is an integral, while the last two terms repair the difference between area and sampled values.

We use $B_1=-\frac{1}{2}$ throughout. The defining exponential generating function isHere $e^t$ is the exponential function and $n!$ is a factorial; in particular, the coefficient of $t^2$ is $B_2/2!$, rather than $B_2$. At $t=0$ the quotient has limiting value one. The identity can be read algebraically as a formal power series, or as a convergent series for $|t|<2\pi$.^[ref]

To compute the numbers, multiply by $e^t-1$ and compare coefficients. The resulting recurrence relation, with binomial coefficients, isThus $1+2B_1=0$, $1+3B_1+3B_2=0$, and $1+4B_1+6B_2+4B_3=0$ give $B_1=-1/2$, $B_2=1/6$, and $B_3=0$. Continuing givesThe recurrence relation agrees with equation 24.5.3 after replacing its index $n$ by $m+1$.^[ref]

Why do so many values vanish? Put $F(t)=t/(e^t-1)$. Direct substitution gives $F(-t)=F(t)+t$, so $F(t)+t/2$ is an even function. Its odd power series coefficients vanish: $B_{2r+1}=0$ for every positive integer $r$. The exception $B_1$ matters. The alternative convention obtained from $t/(1-e^{-t})=F(t)+t$ has $B_1^{+}=+1/2$ and exactly the same other values. A formula copied between conventions must also retain its summation endpoints.

Historically, integer power sums were studied before the modern Bernoulli number notation. A historical study examines formulas published in 1631 and distinguishes those separate formulas from encoding all exponents using one sequence of constants. This is a useful motivation for the generating function, without assigning all discovery to a single moment. ^[ref]

Take an IID random variable source of bits with $P(X_j=1)=1/4$. Its binary entropy isA word of length $n$ containing $k$ ones has probability $(1/4{)}^k(3/4{)}^{n-k}$. Its information content per symbol isThus weakly typical sequences for this biased source have $k/n$ near $1/4$. With tolerance $\epsilon =0.1$ bits per symbol, the exact condition isFor $n=40$, this includes exactly $k=8,9,10,11,12$. There are $\left(\genfrac{}{}{0ex}{}{40}{k}\right)$ words with each count: a type class with that many possible orderings. Summing the counts and their probability masses givesThese are fewer than one percent of the $2^{40}$ possible words, yet they carry nearly 64 percent of the probability. The most likely individual word is all zeros, with probability $(3/4{)}^{40}\approx 1.006\times 10^{-5}$; it is outside this typical set. No contradiction is involved: the type classes near ten ones each contain many more individual words.

For positive real numbers $a,b$, the beta integral represents the beta function by $B(a,b)={\int }_0^1{x}^{a-1}(1-x{)}^{b-1}dx$. In particular, for nonnegative integers $m,n$, it gives ${\int }_0^1{x}^m(1-x{)}^{n}dx=m!n!/(m+n+1)!$, connecting integration to binomial coefficients.

A Bézier curve is a parametric curve specified by control points $P_0,\dots ,P_n$ in a Euclidean space and the Bernstein basis:Here $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ is a binomial coefficient. Each coordinate is a polynomial of polynomial degree at most $n$; special choices of control points can lower the polynomial degree. The ordered control points form the control polygon. A cubic Bézier curve uses four control points and has the explicit formThe curve passes through $P_0$ and $P_3$; the interior control points steer its shape and need not lie on it.^[ref]

For a worked example, chooseSubstituting these control points givesHere $y(t)=1.5-6(t-1/2{)}^2\le 1.5$, so neither interior control point, both at height $2$, lies on the curve. De Casteljau's algorithm computes the same point using only successive linear interpolations.

The endpoint tangent vectors follow from the Bézier derivative control polygon:Thus the curve leaves $P_0$ toward $P_1$ and arrives at $P_3$ from $P_2$. These nonzero derivatives determine the endpoint tangent lines; if an endpoint derivative vanishes, that formula alone does not determine its tangent direction. Endpoint handles are useful when arranging a parametric first-derivative join of Bézier curves.

The parameter $t$ is usually not arc length. For this example,Equal steps in $t$ therefore do not generally travel equal distances. Distance along the curve is instead the arc length, given by the integral $s(t)={\int }_0^t\Vert C^{\prime }(u)\Vert du$; its derivative is the norm of the tangent vector and measures the rate of travel.

Two geometric facts make Bézier curves especially convenient for design. First, the Bernstein basis weights are nonnegative and form a partition of unity, since the binomial theorem gives ${\sum }_i{b}_{i,n}(t)=((1-t)+t{)}^n=1$. Hence $C(t)$ is a convex combination of the control points and lies in their convex hull.^[ref] The convex hull is the smallest convex set containing the control points, not their axis-aligned bounding box. Here it is a trapezoid, strictly smaller than $[0,4]\times [0,2]$: the box corner $(0,2)$ is outside the convex hull. The curve need not fill or touch every edge of either enclosure. The convex hull guarantee concerns $0\le t\le 1$; outside that interval weights can be negative.

Second, applying an affine map to every control point gives exactly the same result as applying it to the entire curve. For $T(x)=Ax+b$,This is affine equivariance of a geometric basis: a translation, rotation or shear mapping can be performed on a handful of control points. For example, $T(x,y)=(2x+y,y+1)$ transforms the four control points to $(0,1),(4,3),(8,3),(8,1)$ and transforms the midpoint to $(5.5,2.5)$, also obtained from the same weights $(1,3,3,1)/8$.

These editable handles explain the usefulness of Bézier curves in computer aided geometric design, vector graphics paths and outline fonts: a small collection of points controls an entire smooth stroke, and resizing the design preserves its mathematical shape. Cambridge's computer-graphics notes describe their use in graphic design, typography and PostScript outlines. The industrial context includes Pierre Bézier's work at Renault and Paul de Casteljau's work at Citroën.^[ref]

// Target: analysis.bigb

For a positive integer $N$, all binomial coefficients $\left(\genfrac{}{}{0ex}{}{N}{j}\right)$ with $0<j<N$ are even exactly when $N$ is a power of two. Write the binary expansion $N={\sum }_{i\in I}{2}^i$. In the polynomial ring ${\mathbb{F}}_2[t]$, repeated squaring givesIf $I$ has one element, there are no interior terms. If it has more than one, the coefficient of $t^{2^{\min I}}$ is one and that exponent lies strictly between zero and $N$. This characterization gives a useful parity obstruction directly from the binary expansion.

The binomial distribution counts successes in a fixed number $n$ of independent Bernoulli trials with common success probability $p$. Equivalently,Here $n$ is a nonnegative integer and $0\le p\le 1$. The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n!/[k!(n-k)!]$ counts placements of the $k$ successes; each particular arrangement has probability $p^k(1-p{)}^{n-k}$. The binomial theorem makes the masses sum to $[p+(1-p){]}^n=1$. At $p=0$ all mass is at zero, and at $p=1$ all mass is at $n$; these endpoint laws can be read directly without interpreting $0^0$.

The linearity of expectation and addition of variances for independent random variables giveThe fixed trial count, common success probability, and joint independence are substantive model assumptions. Sampling uniformly without replacement from a finite population instead leads to a hypergeometric distribution. Independent trials with different success probabilities generally give a Poisson binomial distribution. Common marginal success probabilities alone are insufficient: if all ten indicators equal the same Bernoulli random variable with $p=0.3$, their sum is zero with probability $0.7$ or ten with probability $0.3$. Its mean is still three, but its variance is $100(0.21)=21$. The standard construction is given in Penn State STAT 504, binomial distribution.

For an exact constructed example, let each of ten independent trials choose uniformly from ten labelled tokens, with replacement, and mark three tokens as successes. Then $p=3/10$ and $K\sim \mathrm{Bin}(10,0.3)$. Exactly three successes have probabilityThe mean is $10(0.3)=3$, the variance is $10(0.3)(0.7)=2.1$, and the standard deviation is $\sqrt{2.1}\approx 1.4491$. Zero successes have probability $0.7^{10}=0.0282475249$, so at least one success has probability $1-0.7^{10}=0.9717524751$. A single count calculation replaces enumeration of all $10^{10}$ equally likely token sequences.

Each bar's height is one probability mass. Three is the most likely count, but its mass is only about $26.7\%$: a most likely outcome need not occur most of the time.

The binomial expansion expresses $(a+b{)}^n$ as ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)a^{n-k}{b}^k$ for a nonnegative integer $n$. The binomial coefficients give the number of ways to choose which $k$ factors supply $b$.

For $n\ge 0$, define $B_0(X)=1$ and $B_n(X)=X(X-1)\cdots (X-n+1)/n!$. The binomial coefficient formula shows $B_n(m)\in \mathbb{Z}$ for every nonnegative integer $m$. Since these integers are dense in the p-adic integers, continuity of the polynomial implies $B_n({\mathbb{Z}}_p)\subseteq {\mathbb{Z}}_p$, so it is an integer-valued polynomial there and $\Vert B_n{\Vert }_{\infty }=1$. The Pascal's identity gives $\Delta B_{n+1}=B_n$ for the forward difference operator.

The binomial distribution with parameters $n$ and $p$ assigns the displayed probability to $k$ successes, for integers $0\le k\le n$. Each specified sequence of independent trials has probability $p^k(1-p{)}^{n-k}$, and the binomial coefficient counts the sequences with exactly $k$ successes. Outside this range the probability is zero.

Take $N=20$ distinguishable, labeled particles and two boxes of equal volume. Retain only whether each particle is in the left or right box: use a bit $0$ for left and $1$ for right. Each length-20 string is one coarse microstate of this toy model. Assume the labels make independent side choices with equal probability, so the $2^{20}=1048576$ strings are equiprobable. Equal volumes motivate these weights for noninteracting particles with no preference for either box; equal volumes alone would not establish them for an arbitrary interacting gas.

Now retain only the number $k$ in the left box as the macrostate. Choosing which $k$ labels are left gives a binomial coefficient, soThe factorials count assignments to labels; the probability of a macrostate sums the probabilities of its constituent microstates. This is the binomial distribution with parameters $20$ and $1/2$. The same binomial coefficient appears in the counting of distinguishable two-level systems, although here the macrostate records occupancy rather than energy. ^[ref]

The largest binomial coefficient occurs at $k=10$, the balanced macrostate. All-left means $k=20$ and supplies just one string. ThusThere are $184756$ balanced strings for every all-left string, even though each individual string has the same probability. Exact balance has about $17.6\%$ of the total probability; equilibrium reasoning concerns the many macrostates near balance too, rather than certainty of exactly ten particles on each side. The diagram compares the counts with their natural logarithms.

Four fair, independent coins give a smaller worked example with the same binomial distribution. If $k$ is the number of heads, the five macrostates $k=0,1,2,3,4$ contain respectively $1,4,6,4,1$ microstates. Their probabilities are respectively $1/16,4/16,6/16,4/16,1/16$. In particular, two heads is one macrostate containing six ordered coin sequences, with Boltzmann entropy $k_B\ln 6$ in this counting analogy. A prescribed ordered sequence has one realization. The next diagram enumerates the same sixteen strings as left/right assignments.

A capture-recapture model is a statistical model for repeated observations of identifiable individuals, including those missed on some occasions. A closed-population capture-recapture model estimates a fixed population cardinality; models allowing individuals to enter or leave can instead describe survival and recruitment. The sampling assumptions determine which likelihood function is appropriate.

For the two-sample closed-population capture-recapture model, condition on the sample sizes $M$ and $C$. If the second sample selects $C$ distinct individuals from $N$ by simple random sampling, then the overlap $R$ has the hypergeometric distribution:Here $r$ is an integer and the probability mass function is zero outside these bounds. The binomial coefficients count choices of $r$ marked and $C-r$ unmarked individuals, divided by all equally likely size-$C$ subsets. The hypergeometric distribution has expected valueEquating the observed overlap with this expected value gives the Lincoln-Petersen estimator. The underlying sampling without replacement, probability mass function, and expected value are developed in Raymond P. Guiteras, MIT 14.30 hypergeometric distribution handout, §§1–4 and 8.

For the toy counts $M=20$, $C=25$, and $R=5$, hold the observations fixed and vary the unknown integer $N$. The likelihood function isValues below forty cannot contain the observed set union. Exact comparison of consecutive likelihoods gives two tied maximum-likelihood estimates, $N=99$ and $N=100$. The Lincoln-Petersen estimator returns $100$; the Chapman estimator returns $90$ and is a different rule for estimation.

The vertical scale is $L(N)/{\max }_{n\ge 40}L(n)$. This relative likelihood compares how well candidate statistical parameters explain the same observations; it is not a posterior probability. The displayed range $40\le N\le 300$ is only a plotting window. The likelihood function remains positive for every integer $N\ge 40$ and tends to zero as $N$ increases, so the curve has a continuing right tail. The data do not justify truncating statistical inference at three hundred. The conditional hypergeometric distribution formulation also appears in Louis-Paul Rivest and Mamadou Yauck, Small Sample Estimators for Two-way Capture Recapture Experiments, §3, equation (5).

Zero recaptures require care. With $R=0$ and positive $M,C$, the Lincoln-Petersen estimator has no finite ratio, but the capture-recapture model still gives a valid likelihood function:This likelihood function increases toward one as $N$ grows, so there is no finite maximum-likelihood estimate. For the same sample sizes twenty and twenty-five with zero overlap, forty-five distinct individuals would be observed. Lack of overlap supplies a lower bound but very weak information about large population cardinalities.

In more elaborate capture-recapture models, a first-recapture array $m_{ij}$ counts individuals released at occasion $i$ and next observed at $j$. A probability of survival ${\varphi }_j$ and a probability of detection $P_{j+1}$ contribute a no-observation continuation factor ${\varphi }_j(1-P_{j+1})$. The resulting likelihood function depends on both survival and detection; these probabilities need not be separately identifiable at the last observation interval. Missing-count EM for capture-recapture describes one way to fit such a model, and identifiability remains a separate issue from computing an estimator output.

Let $X_1,X_2,\dots$ be real independent and identically distributed random variables with expected value $\mu =\mathbb{E}[X_1]$ and finite, strictly positive variance ${\sigma }^2=\mathbb{E}[(X_1-\mu {)}^2]$. Write $S_n={\sum }_{j=1}^n{X}_j$ and ${\overline{X}}_n=S_n/n$ for their sum and sample mean. The central limit theorem statesPrecisely, for every real $z$,where $\Phi$ is the standard normal distribution function. The conclusion is convergence in distribution to the standard normal distribution. If the variance is zero, every observation equals $\mu$ almost surely; the displayed normalization is then undefined and there is no fluctuating error to describe.

The striking feature is that the observations need not have a normal distribution. They may be binary, bounded, or strongly skewed. Their detailed probability distribution disappears from this limit except through the expected value and variance. The subtraction removes predictable growth: $\mathbb{E}[S_n]=n\mu$. The division implements variance normalization: variance additivity for independent random variables gives $\mathrm{Var}(S_n)=n{\sigma }^2$, so every $Z_n$ has expected value zero and variance one. For nonzero $\mu$, an uncentered sum drifts; without rescaling its spread grows.

For a concrete example, let each $X_j$ have a Bernoulli distribution with success probability $p=0.2$. Then $K_n=S_n$ has a binomial distribution, with expected value $np$ and variance $np(1-p)$. Its exact probability mass function and its normalized count areHere $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is a binomial coefficient. Individual trials are conspicuously skewed, yet their centered, rescaled counts approach the same standard normal distribution as sums of fair trials.

At $n=100$, $K_n$ has expected value $20$ and standard deviation $4$. The exact binomial distribution gives $\mathbb{P}(16\le K_n\le 24)=0.740141\dots$. A normal approximation with the continuity correction uses the interval $15.5$ to $24.5$:The small discrepancy is an approximation error, not an equality supplied by the central limit theorem.

The strong law of large numbers and weak law of large numbers locate the average: ${\overline{X}}_n\to \mu$, respectively by almost sure convergence and convergence in probability. The central limit theorem magnifies that shrinking error and describes its shape. In terms of the sample mean, the resulting normal approximation is $N(\mu ,{\sigma }^2/n)$, with standard error $\sigma /\sqrt{n}$. This explains why four times as many independent observations halve the standard error. When $\sigma$ is known, ${\overline{X}}_n\pm 1.96\sigma /\sqrt{n}$ has approximately $95\%$ coverage for $\mu$ at large $n$, giving a confidence interval. This coverage refers to repeated samples, not a guarantee for an individual interval.

A useful application is the Monte Carlo method: estimate a success probability by the proportion of successful simulated trials. Nicholas Metropolis and S. Ulam's original paper, "The Monte Carlo Method" (1949), illustrates this with games of solitaire and estimation of a region's volume by randomly selected points, and discusses why estimates require probabilistic error control. The strong law of large numbers justifies convergence of such proportions for independent repetitions; the central limit theorem supplies their large-sample error scale when $0<p<1$.^[ref]

There are three useful limits to this picture:

A historical original-paper reference is J. W. Lindeberg's "Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechnung" (1922), published in Mathematische Zeitschrift 15, pp. 211–225. The Lindeberg condition and Lindeberg-Feller central limit theorem below describe a version for sums whose summands need not share a probability distribution.^[ref]

A brief proof outline uses the characteristic function of $Y=(X_1-\mu )/\sigma$. Its expected value is zero and its variance is one, so the finite second moment givesThe Taylor expansion of the complex exponential, with its remainder controlled by $Y^2$, and the dominated convergence theorem justify this step without a third-moment assumption. Independence then gives the characteristic function of $Z_n$:The limit is the characteristic function of the standard normal distribution; the Lévy continuity theorem turns this into convergence in distribution.

The central binomial coefficient satisfies $4^m/(2m+1)\le \left(\genfrac{}{}{0ex}{}{2m}{m}\right)\le 4^m$. Prime factors between $m$ and $2m$ give a dyadic upper bound for the Chebyshev theta function. The prime-power exponents in the factorial quotient are sums of zeros and ones, so the central coefficient gives a linear lower bound for the Second Chebyshev function. Higher prime powers contribute only $O(\sqrt{x}\log x)$; hence the prime-counting function has upper and lower bounds of order $x/\log x$.

Suppose a continuous map $g:S^n\times S^n\to S^n$ changes sign on negating either input. Its quotient $\bar{g}:{\mathbb{RP}}^n\times {\mathbb{RP}}^n\to {\mathbb{RP}}^n$ pulls back the real tautological line bundle to the tensor product of vector bundles $p_1^{\ast }{\gamma }_n\otimes p_2^{\ast }{\gamma }_n$. The fiber map sends $(sx)\otimes (ty)$ to $stg(x,y)$. The First Stiefel–Whitney class of a tensor product of real line bundles consequently gives ${\bar{g}}^{\ast }a=a_1+a_2$. The Künneth theorem and the mod-two cohomology ring of real projective space implyEvery interior binomial coefficient in row $n+1$ must be even. By binomial coefficients with even interior terms, $n=2^k-1$ for some $k\ge 0$. This is a necessary condition, not an assertion of existence in every such dimension.

A choice of $k$ distinct elements from a set of $n$ elements, with order ignored. Equivalently it is a $k$-element subset. The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ counts such choices; choosing with repetition instead produces a multiset.

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]