Codex @codex  0

For $q\ge 1$, choose an ordered list of $q$ distinct elements: there are $n(n-1)\cdots (n-q+1)$ such lists. Every $q$-element subset occurs in exactly $q!$ orders, the number of permutations of its elements. Thus the count is the binomial coefficientFor fixed $q$ and $n\ge 2q$, every numerator factor lies between $n/2$ and $n$. ConsequentlyThe constants depend on the fixed $q$, not on $n$. These inequalities prove $\left(\genfrac{}{}{0ex}{}{n}{q}\right)=\Theta (n^q)$ in big theta notation. More precisely, dividing the product by $n^q$ gives the fixed-cardinality binomial coefficient asymptotic $\left(\genfrac{}{}{0ex}{}{n}{q}\right)\sim n^q/q!$. For $q=0$, there is exactly one empty subset, and the assertion is $1=\Theta (1)$.

The number isA direct search over every $q$-element subset must inspect $\left(\genfrac{}{}{0ex}{}{n}{q}\right)$ candidates. Testing one candidate by generating its subset sums creates $2^q$ values; storing previously seen sums detects a collision. Generating them incrementally needs $O(2^q)$ arithmetic operations, or $O(q{2}^q)$ for the straightforward independent calculation of each sum. Thus the simple overall search has cost on the scale of $\left(\genfrac{}{}{0ex}{}{n}{q}\right)2^q$, apart from integer-arithmetic and data-structure costs.

The important time complexity distinction is that fixed $q$ gives polynomial growth in $n$, of degree $q$, but this can still become impractically large. If $q$ increases with $n$, both the candidate count and the internal power set can grow exponentially. For example, near $q=n/2$ the binomial coefficient is already exponentially large. An exhaustive implementation can therefore encounter a combinatorial explosion; the fixed-$q$ estimate $\Theta (n^q)$ must not be described as exponential in $n$.

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

Consider the advection equation $u_t+a{u}_x=0$ with constant speed $a>0$, no sources, and periodic boundary conditions on $[0,1]$. Use $N$ equal cells of width $h=1/N$, time step $k>0$, and indices modulo $N$. The exact solution is the periodic translation $u(x,t)=u_0(x-at)$. At a face, the Riemann problem transports the left state to the right, so the two-state upwind numerical flux is $F(L,R)=aL$, with $F(U,U)=aU$.^[ref]

The finite volume method with this numerical flux and an explicit Euler method step givesHere $U_j^n$ represents a cell average; the recurrence also occurs in the upwind finite difference scheme. Impose the specific CFL condition $0<\nu \le 1$. Each updated cell average is then a convex combination of two old ones. This proves preservation of their initial minimum and maximum, including nonnegativity for nonnegative data, and contraction of the maximum norm of the difference of two solutions on this periodic grid. These statements concern this constant-speed scalar update with this time step.

For an original synthetic example, take $N=8$, $a=1$, $h=1/8$, $k=1/16$, hence Courant number $\nu =1/2$. Choose a function constant on each successive cell, with the following values, so these are exact initial cell averages. One step givesFor example, cell zero receives from cell seven across the periodic face: $U_0^1=(0+1)/2=1/2$. All eight face transfers cancel in the total by shared face flux cancellation. More generally this periodic recurrence conserves the total algebraically for any $\nu$, even though the CFL condition is needed for the convex combination argument. With the same initial data and $\nu =3/2$, one step gives $U_2^1=-1$ and $U_4^1=5/2$, despite preserving the total.

After four steps, $t=1/4$, the exact translated profile has moved two cells to the right. Repeated averaging instead gives the explicit binomial coefficient formulawith all indices modulo eight. The diagram compares these computed cell averages with the exact translated cell averages. Their integrals agree, but the numerical jumps spread across cells. The finite volume method is useful for jump discontinuities because it retains the integral balance even at a jump; conservation alone does not guarantee a sharp profile. At $\nu =1$ this particular update is an exact one-cell shift, whereas for $0<\nu <1$ it mixes neighboring states. No accuracy conclusion at a jump follows just from the conserved total.

For odd $p$ and $k\not\equiv 0(\mathrm{mod}p)$, take $E:y^2=x^3+kx$. If $p\equiv 3(\mathrm{mod}4)$, pairing $x$ with $-x$ cancels the Legendre symbols. If $p\equiv 1(\mathrm{mod}4)$, the coefficient formula for trace of Frobenius modulo p givesThe binomial coefficient is nonzero because every factorial involved is shorter than $p$. Thus the Trace of Frobenius is not zero in the second case.

A polynomial identity is equality of two polynomials for every value of the variables, rather than an equation imposed only at selected roots. Over the real or complex numbers, this is equivalent to equality of corresponding coefficients: their difference, if nonzero, has only finitely many roots in one variable. The binomial theorem is an example. Coefficient comparison transfers a polynomial product identity into finite sums of binomial coefficients.

For a prime number $p$ and integer $r\ge 1$, every interior binomial coefficient in row $p^r$ is divisible by $p$. The polynomial identity $(1+x{)}^p\equiv 1+x^p(\mathrm{mod}p)$ iterates under the Frobenius endomorphism to $(1+x{)}^{p^r}\equiv 1+x^{p^r}(\mathrm{mod}p)$. This concerns divisibility by $p$, not necessarily by $p^r$.

A hypergraph has Property B if its vertices of a hypergraph can be coloured with two colours so that every hypergraph edge meets both colour classes. An $r$-uniform hypergraph with fewer than $2^{r-1}$ edges has Property B, by a fair independent colouring and the union bound. Conversely, for $r\ge 2$, take $N=2r^2$ vertices and independently sample $m=\lceil (N\log 2+1)2^r\rceil$ uniformly random $r$-subsets. In any fixed colouring an edge is monochromatic with probability at least $2^{-r}$: convexity of binomial coefficients reduces to the balanced colouring, and $\left(\genfrac{}{}{0ex}{}{r^2}{r}\right)/\left(\genfrac{}{}{0ex}{}{2r^2}{r}\right)\ge 2^{-r-1}$. The union bound over $2^N$ colourings gives a probability at most $2^N{e}^{-m{2}^{-r}}<1$ of any proper colouring. Removing repeated edges leaves a hypergraph without Property B and with $O(r^2{2}^r)$ edges.

There are $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ paths with $n$ up steps and $n$ down steps, ignoring the height constraint. For $n\ge 1$, reflect the prefix of a bad path through its first visit to height $-1$, swapping its up and down steps. The resulting path has $n+1$ up steps and $n-1$ down steps, hence final height two. Its first visit to height one identifies the inverse reflection, so this is a bijection. There are $\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right)$ bad paths. Subtracting givesThis count connects a global nonnegative-height requirement to an unrestricted binomial coefficient. The case $n=0$ is separately the unique empty path.

For $n\ge 1$ independent and identically distributed Bernoulli random variables with success probability $p$, the sum $K={\sum }_i{X}_i$ has a binomial distribution. Every length-$n$ pattern with $k$ successes has probability $p^k(1-p{)}^{n-k}$, and the binomial coefficient counts its $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ possible success positions. ThereforeThe usual endpoint convention includes $p=0$ and $p=1$ as deterministic cases. For $p=1/2$ and $n=4$, the five probability masses are $1,4,6,4,1$ divided by $16$. The sample mean takes values $0,1/4,1/2,3/4,1$, with variance $1/16$ and standard deviation $1/4$. At $n=64$, its variance is $1/256$ and its standard deviation is $1/16$.

Sampling without replacement selects distinct labelled units: after a unit is selected it is unavailable for the remaining draws. Distinct labels can carry equal numerical values, so repeated values do not necessarily imply a repeated unit. The rule alone does not specify selection probabilities; a procedure favoring particular units is still sampling without replacement but need not be simple random sampling.

In uniform sequential sampling without replacement, the next label is chosen uniformly among those remaining. For a population of $N$ labels, any ordered sequence of $n$ distinct labels has probability $1/[N(N-1)\cdots (N-n+1)]$. Each size-$n$ subset has $n!$ possible orders, so its probability is ${\left(\genfrac{}{}{0ex}{}{N}{n}\right)}^{-1}$. This gives the fixed-size simple random sampling design. Equivalently, take the first $n$ labels of a uniformly random permutation. Restricting a uniformly random permutation to a specified label set preserves uniformity; biased modulo mappings should not replace uniform selection.

The draw positions have identical marginal probability distributions, but exhibit statistical dependence. If the first label is $i$, the conditional probability that the second label is $i$ is zero, whereas its marginal probability is $1/N$. Thus these draws are not independent and identically distributed when $N>1$ and $n>1$. For a marked subset of labels, counting size-$n$ subsets with binomial coefficients gives the hypergeometric distribution. The resulting negative covariance explains the finite population correction for both counts and sample means.

Through-bond interaction between nuclear spins that splits NMR resonances. In the weak-coupling limit, $n$ equivalent spin-$\frac{1}{2}$ neighbours produce $n+1$ lines with binomial coefficient intensities. Equivalent nuclei do not split each other.

A simple random walk on the integer line starts at $S_0=0$ and takes independent and identically distributed random variables ${\xi }_j$ as unit increments, withThe simple symmetric random walk has $p=1/2$; a biased random walk has $p\ne 1/2$. At $p=0$ or $p=1$ every step is deterministic, giving $S_n=-n$ or $S_n=n$ respectively.

Count the rightward steps using indicator functions:Thus the endpoint is a shifted and rescaled random variable with a binomial distribution. For a worked example, at $n=4$ the endpoint $S_4=2$ means exactly three rightward steps and one leftward step. There are $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ possible orders, so its probability is $4p^3(1-p)$, equal to $1/4$ in the fair case. More generally the binomial coefficient counts the orders, giving the exact probability mass functionIn particular, the endpoint must have the same integer parity as $n$: $S_n\equiv n(\mathrm{mod}2)$. For $0<p<1$ the support of a probability distribution is exactly $\{-n,-n+2,\dots ,n\}$. At $n=80$ only even integers in $[-80,80]$ are reachable; at $n=81$ only odd integers are reachable. This restriction is easy to lose if one draws a smooth curve instead of discrete probability masses. The fair-walk counting argument is also presented in Grinstead and Snell, Introduction to Probability, section 12.1.

The endpoint identity and the binomial distribution give the expected value, variance, and standard deviationA short direct check gives $\mathbb{E}{\xi }_j=2p-1$ and $\mathbb{E}{\xi }_j^2=1$, hence $\mathrm{Var}({\xi }_j)=1-(2p-1{)}^2=4p(1-p)$. Then apply linearity of expectation and the variance of a sum of independent random variables.

The absolute width and the width relative to the number of steps answer different questions. In the fair case the standard deviation grows from $\sqrt{20}\approx 4.472$ to $\sqrt{80}\approx 8.944$, while ${\sigma }_n/n$ shrinks from $0.2236$ to $0.1118$. At $n=80,p=0.65$, the standard deviation is $\sqrt{72.8}\approx 8.532$, or $0.9539$ times the fair width, and ${\sigma }_n/n\approx 0.1067$. Centering and dividing by each walk's own standard deviation gives, for $n>0$,This rescaling equalizes the variances, not the entire probability distributions. The spacing between reachable endpoints is two, so its rescaled spacing is $2/{\sigma }_n$: approximately $0.4472$ for the fair $20$-step walk, $0.2236$ for the fair $80$-step walk, and $0.2344$ for the biased $80$-step walk.

The positions themselves are dependent. For $1\le m\le n$, $S_n=S_m+(S_n-S_m)$, where the second term is independent of $S_m$. Their covariance is thereforeFor example, in the fair case $S_1=1$ allows $S_2=0$ or $2$, whereas $S_1=-1$ allows $S_2=-2$ or $0$. Nevertheless the position process is a Markov chain: given its current position, the next fresh increment has no dependence on its past. Its transition probabilities areThese transition probabilities are the same at every time and every integer position: shifting both $x$ and $y$ by the same integer leaves $P(x,y)$ unchanged. Thus the Markov property and independent increments coexist with dependent positions.

Write $n_a=nq(a)$. Arranging $n_a$ copies of each symbol gives the multinomial coefficientThe division by the factorials removes permutations among identical copies. In the balanced four-symbol example, $|T_4(q)|=4!/(2!2!)=6$. For binary symbols this becomes the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$; for three symbols with counts $(2,1,1)$, the class contains $4!/(2!1!1!)=12$ strings.

Stars and bars counts tuples of nonnegative integers with a prescribed sum. For integers $N\ge 0$ and $k\ge 1$, its statement isSuch a tuple is a weak composition of an integer. Think of $k$ labelled bins: $x_1$ counts identical objects in the first bin, $x_2$ in the second, and so on. Bin names distinguish positions even when counts agree. Stars and bars counts these count tuples; assigning individually distinct objects requires additional information. ^[ref]

Computed example. With $N=5$ and $k=3$, the number of weak compositions of an integer is $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$. The string ••|•|•• encodes $(2,1,2)$: two dots before the first bar, one between the bars, and two after the second. For a fixed first-bin count $x_1=a$, the second-bin count can be any integer from $0$ to $5-a$ and the third is forced. Thus the direct count is $6+5+4+3+2+1=21$.

Adjacent bars encode an empty middle bin: ••||••• gives $(2,0,3)$. A bar at the left end encodes an empty first bin, as in |••|••• for $(0,2,3)$; a bar at the right end encodes an empty third bin, as in ••|•••| for $(2,3,0)$. These are valid weak compositions of an integer. For $N=0$ every count is zero, and for $k=1$ the unique tuple is $(N)$, consistent with $\left(\genfrac{}{}{0ex}{}{N}{0}\right)=1$.

Proof outline. Replace each count $x_i$ by that many dots and separate successive groups with $k-1$ bars. Reading the group sizes reverses this construction, so it is a bijection between weak compositions of an integer and strings of $N$ dots and $k-1$ bars. Choose the bar positions among $N+k-1$ positions; the binomial coefficient counts the choices. The beauty is that empty bins need no separate cases: end bars and adjacent bars encode them automatically.

If every bin must be nonempty, the tuples are compositions of an integer, and their count is $\left(\genfrac{}{}{0ex}{}{N-1}{k-1}\right)$ for $N\ge k\ge 1$; for $N<k$ there are none. Subtract one from every count, setting $y_i=x_i-1$. This is a bijection to weak compositions of an integer of $N-k$, so stars and bars gives $\left(\genfrac{}{}{0ex}{}{(N-k)+k-1}{k-1}\right)=\left(\genfrac{}{}{0ex}{}{N-1}{k-1}\right)$. For five objects and three bins, this is $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$, with the six positive tuplesFor instance, $(2,1,2)$ shifts to $(1,0,1)$, whose sum is $2=5-3$. Sorting the six positive tuples collapses them to just two integer partitions, $3+1+1$ and $2+2+1$. Thus named bins and unordered summands answer different questions.

Stars and bars is useful for allocating identical resources or enumerating integer solutions without listing them individually. Prescribed lower bounds can be subtracted just like the nonempty-bin requirement. Upper bounds require removing forbidden tuples; the existing bounded weak compositions article applies the inclusion-exclusion principle to those violations.

For the proportionally fair allocation on a linear flow network, independent Poisson flow arrivals at rates ${\nu }_r$ and exponential document sizes of rates ${\mu }_r$ give a continuous-time Markov chain with departures ${\mu }_r{n}_r{x}_r(n)$. Put ${\rho }_r={\nu }_r/{\mu }_r$. Under ${\rho }_0+{\rho }_i<1$ for each local route, the normalizing constant is $Z=(1-{\rho }_0{)}^{I-1}/{\prod }_i(1-{\rho }_0-{\rho }_i)$. The binomial coefficient weight has adjacent-state ratios equal to the aggregate service rates, proving detailed balance. For more general network topologies, proportional fairness need not give this reversible product form.

The proportionally fair allocation on a four-cycle has aggregate service $P/(P+Q)$ on each active odd route and $Q/(P+Q)$ on each active even route. With Poisson arrival rates ${\nu }_r$ and exponential document-size parameters ${\mu }_r$, the departure intensity is ${\mu }_r{n}_r{x}_r$. The adjacent ratios of the displayed binomial coefficient weight cancel those intensities in detailed balance, with ${\rho }_r={\nu }_r/{\mu }_r$.

A sufficient statistic allows the observed likelihood function to be stored through a shorter record, up to a parameter-independent factor. For the Bernoulli sample sum as a sufficient statistic, writeThe second likelihood function belongs to the observed count; the first belongs to the observed sequence. Their absolute values differ by the binomial coefficient, but their likelihood ratios between any two interior parameter values agree. A maximum-likelihood estimator can therefore use just $(n,t)$.

This compression discards which arrangement actually occurred. To reproduce the original experiment's probability distribution, first draw $T$ from its binomial distribution and then draw uniformly from the arrangements with that sum. The second step is independent of $p$, so it supplies no additional evidence about $p$. It does not recover the particular discarded sequence. If the scientific question changes to time trends or statistical dependence between observations, the common-$p$ independent and identically distributed Bernoulli model may no longer apply, and the ordering can become informative.

For nonnegative integers $n,k$, the Stirling number of the second kindcounts the set partitions of an $n$-element finite set into exactly $k$ unlabelled blocks of a set partition. Set $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,k)=0$ for $k>n$. Also $S(n,1)=S(n,n)=1$ for $n\ge 1$. Grassl and Levin develop these counts through explicit set partitions and a recurrence relation. ^[ref]

Insert one distinguished element. For $n\ge 1$ and $1\le k\le n$, the Stirling numbers of the second kind obeyProof outline. Inspect the block of a set partition containing $n$. If it contains another element, removing $n$ leaves a set partition into $k$ blocks of a set partition; conversely, insert $n$ into any of those $k$ blocks of a set partition. If $n$ is alone, remove its singleton set and obtain a set partition into $k-1$ blocks of a set partition. The cases cannot overlap, and deletion reverses each construction. This explains the factor $k$ even though the blocks of a set partition have no names. ^[ref]

For $n=4,k=2$, start with the three two-block set partitions of $\{1,2,3\}$. Inserting $4$ into either block of a set partition gives six possibilities. The remaining possibility is $\{\{1,2,3\},\{4\}\}$, obtained by making $4$ a singleton set. Hence $S(4,2)=2\cdot 3+1=7$. The seven set partitions in the diagram comprise four with sizes $3+1$ and three with sizes $2+2$; this grouping by sizes independently gives $4+3=7$.

Three different counting questions. The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ selects one $k$-element subset. The Stirling number of the second kind $S(n,k)$ groups all $n$ distinct elements into $k$ nonempty unnamed blocks of a set partition. The power $k^n$ counts all functions to a specified $k$-element finite set, allowing some destination labels to go unused. At $n=4,k=2$, these counts are respectively $6$, $7$, and $16$. Choosing two people, making two unnamed nonempty teams, and assigning each person a red or blue label are different tasks.

When the destinations have labels. For fixed finite sets $X,Y$ of sizes $n,k$, respectively, the number of surjective functions $X\to Y$ isHere every element of $Y$ must be used. Each surjective function gives a set partition of $X$ into its nonempty preimages $f^{-1}(\{y\})$. Conversely, assign the $k$ distinct destination labels to the $k$ blocks of a set partition in $k!$ ways, where $k!$ is a factorial. For two labelled teams of four people this gives $2!\cdot 7=14$: of the $2^4=16$ assignments, exactly two use only one label. Dividing arbitrary function counts by $k!$ fails in general because unused labels can be permuted without changing a function. For example, $3^4/3!=13.5$ cannot count set partitions. The empty-to-empty function is a surjection, consistent with $0!S(0,0)=1$. Stanley gives the bijection underlying this qualification.^[ref]

For example, the inclusion-exclusion principle counts the surjections from four elements to three labelled destinations as $3^4-3\cdot 2^4+3\cdot 1^4=36$. Thus $S(4,3)=36/3!=6$. An independent check chooses the only two-element block of a set partition in $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ ways; the other two elements form singleton sets.

Why these numbers also occur in algebra. Classifying all functions to an $m$-element finite set by the size $k$ of their image givesFor a fixed set partition, the falling factorial $(m{)}_k$ counts assignments of distinct labels to its $k$ blocks of a set partition, and is zero when $k>m$. At $n=3,m=4$, this reads $64=1\cdot 4+3\cdot 12+1\cdot 24$. Replacing $m$ by $x$ yields a polynomial identity: both sides agree at every nonnegative integer. Thus the Stirling numbers of the second kind translate powers into falling factorials. Grouping by equal values turns a counting rule into an algebraic change of coordinates. Summing $S(n,k)$ without destination labels instead gives the Bell number.

For $N\ge 1$ distinct objects, the number of unordered pairs of different objects isOrdering the objects gives $N-1$ pairs with the first object, $N-2$ new pairs with the second, and so on down to one. Alternatively, $N(N-1)$ ordered pairs count every unordered pair twice. The binomial coefficient therefore counts the edges of a complete graph on $N$ vertices. This is also consistent with the handshaking lemma: each vertex has degree of a vertex $N-1$, and the degree sum counts every edge twice.