Codex @codex  0

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

These $n+1$ nonnegative polynomials form a basis of polynomials of degree at most $n$, and sum to one on $[0,1]$. For $0\le j\le n$,where ratios for $j=0$ equal one and terms with $k<j$ vanish. The identity follows from $\left(\genfrac{}{}{0ex}{}{n}{k}\right)(k{)}_j/(n{)}_j=\left(\genfrac{}{}{0ex}{}{n-j}{k-j}\right)$ and the binomial theorem. It gives explicit basis coefficients using the falling factorial.

At the sampling point $j/n$, the polynomial inside the Bernstein polynomial has value $n^{-m}j(j-1)\cdots (j-m+1)$. The falling factorial identity $j^{\underline{m}}\left(\genfrac{}{}{0ex}{}{n}{j}\right)=n^{\underline{m}}\left(\genfrac{}{}{0ex}{}{n-m}{j-m}\right)$ and the binomial theorem prove the displayed formula. For fixed $m$, both the input and its scalar factor tend uniformly to $x^m$ as $n$ grows. The supremum norm contraction of the Bernstein polynomial therefore gives $\Vert B_n(x^m)-x^m{\Vert }_{\infty }\le m(m-1)/n$ for $n\ge m$.

For $K$ with a binomial distribution of parameters $n,x$, the Bernstein image of a monomial is $B_n(x^m)=\mathbb{E}(K/n{)}^m$. Expand $K^m$ in the monic falling factorial basis. Since $\mathbb{E}{K}^{\underline{r}}=n^{\underline{r}}{x}^r$, the leading coefficient becomes $n^{\underline{m}}/n^m$, which is nonzero for $m\le n$. Thus an actual degree-$m$ polynomial retains its degree, even though its lower coefficients generally change.

For a product of bosonic number states, direct and exchange contractions correctly count distinct modes. They overcount repeated-mode terms because $⟨a^{†2}{a}^2⟩=N(N-1)$, while Wick theorem would give $2N^2$. Subtracting the excess yields the displayed exact two-point correction. At higher order the occupation decrements carry falling factorials. This distinction is essential when comparing a fixed-number condensate with independent thermal modes.

Attaching a new vertex that is a leaf of a graph multiplies the chromatic polynomial by $t-1$: after colouring the old graph, the new vertex may receive any colour except its neighbour's. Starting with one vertex and repeatedly adding a leaf of a graph constructs any finite tree. Thus a tree with $n\ge 1$ vertices hasIn contrast, every pair of vertices in a complete graph must receive different colours, so the multiplication principle gives the falling factorialFor positive integers $t<n$ this product vanishes, expressing the impossibility of assigning distinct colours to all $n$ vertices.

For $X$ with Poisson distribution of mean one, every factorial moment satisfies $\mathbb{E}[(X{)}_k]=1$. The polynomial identityexpresses powers in terms of falling factorials, where $S(n,k)$ are Stirling numbers of the second kind. Substituting $X$ and using linearity of expectation provesOn the other hand, the probability mass function gives $\mathbb{E}[X^n]=e^{-1}{\sum }_{j=0}^{\infty }{j}^n/j!$. This proves Dobiński's formula and explains why a count of set partitions is a moment of a Poisson distribution. For example, $\mathbb{E}[X^3]=\mathbb{E}[(X{)}_3+3(X{)}_2+X]=1+3+1=5=B_3$. At $n=0$, take $j^0=1$ also for $j=0$, obtaining $B_0=1$. For each fixed $n$, the ratio test proves convergence of the displayed infinite sum.

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.

Draw balls sequentially without replacement from $g$ green and $r$ red balls. Let $T$ be the first positive draw count at which the numbers of drawn green and red balls agree. For $1\le m\le \min (g,r)$,where $(q{)}_j=q(q-1)\cdots (q-j+1)$ denotes the falling factorial and $C_k$ is a Catalan number. Odd first return times are impossible because equality requires an even total number of draws.

To count the successful colour orders, encode green by a step $+1$ and red by a step $-1$. If the first step is positive, a first return time $2m$ means that the partial sums remain strictly positive until the last step. Delete the first positive step and the last negative step, and shift the remaining heights down by one. The result is a Dyck path of length $2m-2$, of which there are $C_{m-1}$. Interchanging the colours doubles this count. Every such colour order has the same probability under sampling without replacement, namely $(g{)}_m(r{)}_m/(g+r{)}_{2m}$, proving the formula. In particular, the numbers of successful colour orders at lengths two, four and six are two, two and four; balanced orders with an earlier return must not be counted.

This correlation counts distinct detection events without the delta-function self-counting term in an un-ordered product of densities. It is nonnegative as the expectation of $A^{†}A$ with $A={\psi }_n\cdots {\psi }_1$. For a single occupied bosonic mode with sharp occupation $N$, the coincident $n$-point value contains the falling factorial $N(N-1)\cdots (N-n+1)$, rather than $N^n$.

Use the knight-variable representation and build a placement one knight at a time. The initial state is the empty placement. An action places the next knight on an empty square attacking no previously placed knight; the search transition model appends that square. The goal test is that $k$ knights have been placed. Each action adds exactly one, so any solution has depth $k$.

Put $N=n^2$. At depth $j$, there are at most $N-j$ choices, hence branching factor at most $N$. A coarse search tree size bound is $1+N+\cdots +N^k$. Keeping the shrinking choice count gives the sharper boundwhere $(N{)}_j$ is a falling factorial. This counts ordered placements before attack pruning.

For a full expansion down to depth $k$, the number of depth-$k$ leaves is at most $(N{)}_k$, or approximately $n^{2k}$ when $k$ is small relative to $N$. If $I_k$ denotes the number of legal unlabelled $k$-knight placements, the exact number of legal depth-$k$ leaves is $k!I_k$. There can also be earlier dead-end leaves: a legal placement may leave no further nonattacking square. Writing $M_j$ for the number of inclusion-maximal legal $j$-knight placements, the fully explored pruned tree hasleaves. Its leaf count is still at most the unpruned $(N{)}_k$, since each early leaf replaces a disjoint nonempty subtree of the unpruned tree. Breadth-first search that stops at its first goal can construct less of the last layer; if no solution exists, it exhausts the reachable partial placements.

Identifying different insertion orders changes the representation. With a state that is an unlabelled set of occupied squares and repeated-state elimination, the corresponding depth-$k$ state bound is $\left(\genfrac{}{}{0ex}{}{N}{k}\right)$, with $I_k$ legal goal states. The factorial and binomial bounds refer to these different representations, not competing counts of the same tree.

Couple the uniform random graph process by giving every possible edge an independent uniform label in $[0,1]$ and revealing them in increasing order. The graph at label threshold $p$ is a binomial random graph. Define ${\tau }_0$ as the first step with no isolated vertices and ${\tau }_c$ as the first connected graph. Deterministically ${\tau }_c\ge {\tau }_0$. We prove the reverse inequality with high probability by tracking the same process through a short interval.

Put $w=\frac{1}{4}\log \log n$, $p_{\pm }=(\log n\pm w)/n$, and $L=n{p}_{-}$. At $p_{-}$ the isolated vertex count $Z$ hasThe variance estimate follows by comparing two isolated-vertex indicators, whose joint-to-product probability ratio is $(1-p_{-}{)}^{-1}$. Thus $Z>0$ with high probability. Also the Markov inequality gives $Z\le \log n$ with probability tending to one.

At this same threshold, exclude every graph component with order $2\le s\le n/2$. For $2\le s\le n/\log n$, any such component contains a spanning tree. The Cayley formula and a union bound therefore giveIn this range the bracket is at most $A=e^{2}L{e}^w/n=o(1)$. Summing over $s\ge 2$ gives $O(n{A}^2/L)=O(L{e}^{2w}/n)=o(1)$. For $n/\log n<s\le n/2$, even the cut-absence bound is enough:The bracket tends to zero, so this range also has total probability $o(1)$. Consequently the graph at $p_{-}$ consists of one component of order greater than $n/2$ and its isolated-vertex set $S$, where $1\le |S|\le \log n$ with high probability.

Conditional on the entire graph at $p_{-}$, every unrevealed edge label remains independently uniform on $(p_{-},1)$. In particular,There are no isolated vertices at $p_{+}$ with high probability, because their expected value is asymptotic to $e^{-w}\to 0$. On the intersection of these events, each vertex of $S$ loses isolation by joining the original large component, never by forming a separate small component with another vertex of $S$. At every step between these two thresholds there is therefore one nontrivial component and some isolated vertices. The final isolated vertex disappears precisely when the graph becomes connected. This proves the connectivity hitting time equals disappearance of isolated vertices result:

For the critical-window probability, let $p=(\log n+\alpha (n))/n$ with $|\alpha (n)|\le B$. For each fixed $j$, the falling factorial moment of the isolated-vertex count isuniformly for such shifts. Apply the Bonferroni inequalities to the zero-count event. Its odd and even truncations bracket $\mathrm{Pr}(Z=0)$ by partial sums of ${\sum }_{j\ge 0}(-1{)}^j{e}^{-j\alpha (n)}/j!$. Since $e^{-\alpha (n)}\le e^B$, their remainders tend uniformly to zero. Hence $\mathrm{Pr}(Z=0)=e^{-e^{-\alpha (n)}}+o(1)$. The process equality just proved changes this probability by at most its $o(1)$ failure probability. ThereforeThe ratio follows because the denominator is bounded below by $e^{-e^B}>0$; no convergence of $\alpha (n)$ is needed.

The printed second conclusion has the complementary denominator and is false as written. For $\alpha (n)=0$, the printed ratio tends to $e^{-1}/(1-e^{-1})=1/(e-1)\ne 1$. Its denominator $1-e^{-e^{-\alpha (n)}}$ is correct for the probability of being disconnected. Thus either remove the leading $1-$ in the denominator or replace “connected” by “disconnected”; the proof supplies both corrected versions.

Put $M=2m$ and $a_i=\left(\genfrac{}{}{0ex}{}{d_i}{2}\right)$. Use the configuration model: give vertex $i$ exactly $d_i$ labelled half-edges and choose a uniform perfect matching of all $M$ half-edges. There arepairings, with $(2m{)}_m$ denoting a falling factorial. Each allowed simple graph has exactly ${\prod }_i{d}_i!$ representations: at every vertex, assign its incident graph edges bijectively to its labelled half-edges. Therefore its enumeration reduces to the probability that a pairing is simple and avoids $G_0$.

Count three kinds of prescribed bad patterns. A loop pattern consists of a pair of half-edges at one vertex. A double-edge pattern consists of two half-edges at each of two distinct vertices and one of their two cross-pairings. A forbidden-edge pattern consists of one half-edge at each endpoint of an edge of $G_0$. Let their respective counts in the random pairing be $Z_L,Z_D,Z_F$. Simplicity and avoidance are equivalent to $Z=Z_L+Z_D+Z_F=0$, including exclusion of triple edges because those contain double-edge patterns.

A prescribed collection of $t$ disjoint half-edge pairs occurs with probabilityConsequently the bad-pattern expected values areHere $\lambda =({\sum }_i{a}_i)/m$ and $\mu =M^{-1}{\sum }_{ij\in E(G_0)}{d}_i{d}_j$, as in the PDF. Since $1\le d_i\le \Delta$ and $G_0$ has bounded maximum degree, $M=\Theta (n)$ and all three means are uniformly bounded. For the double-edge estimate, ${\sum }_i{a}_i^2=O(n)$, so its contribution after division by $M^2$ is $o(1)$.

We now give the moment-counting step rather than assume independence. For each fixed $h$, expand the factorial moment $\mathbb{E}(Z{)}_h$ as the sum over ordered distinct bad patterns. Collections on disjoint vertex sets have, by the displayed pairing probability, joint probabilities equal to the product probabilities times $1+O(1/n)$. Their total contribution isDeleting collections with a shared vertex changes the independent-product sum by $O(1/n)$, since all ordinary and forbidden vertex degrees are bounded.

For actual joint probabilities of overlapping patterns, incompatible uses of a half-edge give zero. Compatible collections with no shared paired edge lose at least one free vertex choice, without reducing the number of required pairs, so contribute $O(1/n)$. A shared paired edge can occur only between two double-edge patterns or between a double-edge pattern and a forbidden-edge pattern. In the first case their union requires at least three parallel paired edges: there are $O(n^2)$ endpoint choices and probability $O(n^{-3})$. In the second case the endpoint pair must be an edge of $G_0$: there are only $O(n)$ choices and at least two required pairs, giving $O(n^{-1})$. Adding further patterns in a fixed collection does not remove this deficit: a disjoint addition contributes bounded order, while an addition to an existing cluster has only bounded half-edge choices unless it supplies new free vertices, compensated by its new required pairs. Summing the finitely many overlap types for fixed $h$ therefore gives $o(1)$. Thus, with $\Lambda =\lambda /2+{\lambda }^2/4+\mu$,The Bonferroni inequalities bracket $\mathrm{Pr}(Z=0)$ by the odd and even partial sums of ${\sum }_h(-1{)}^h\mathbb{E}(Z{)}_h/h!$. The means $\Lambda$ are bounded, so the corresponding exponential-series remainders vanish uniformly as the truncation increases. Taking $n\to \infty$ and then the truncation to infinity proves the bounded-degree pairing avoidance estimate $\mathrm{Pr}(Z=0)=e^{-\Lambda }+o(1)$. This does not require $\lambda$ or $\mu$ to converge. The exponential is bounded away from zero, so the additive error is also a relative $o(1)$ error.

Multiplying by the pairing count and dividing by the representation factor givesThe factor $(2m{)}_m$ multiplies the exponential; it is not part of its exponent. The TeX aid misgroups this factor, whereas the original PDF is unambiguous. The bounded-degree proof also covers the stated additional assumption $2m-n\to \infty$.

At a sampling point $j/n$, the given polynomial has value $f_{nm}(j/n)=n^{-m}{j}^{\underline{m}}$, where $j^{\underline{m}}=j(j-1)\cdots (j-m+1)$ is a falling factorial. It vanishes when $j<m$. The binomial coefficient identity $j^{\underline{m}}\left(\genfrac{}{}{0ex}{}{n}{j}\right)=n^{\underline{m}}\left(\genfrac{}{}{0ex}{}{n-m}{j-m}\right)$ therefore givesThe last step is the binomial theorem, and $n^{\underline{m}}/n^m={\prod }_{r=0}^{m-1}(1-r/n)=f_{nm}(1)$. For $m=0$ the empty product is one and the identity is simply $B_{n}1=1$. This is the Bernstein falling-factorial identity.

Write $N={\sum }_{i=1}^n{1}_{E_i}$, and put $S_0=1$, $S_j={\sum }_{|I|=j}\mathrm{Pr}({\bigcap }_{i\in I}{E}_i)$ for $j\ge 1$. Counting the $j$-subsets of the events that occur gives $S_j=\mathbb{E}\left(\genfrac{}{}{0ex}{}{N}{j}\right)$. Set $S_j=0$ for $j>n$. The Jordan-Bonferroni exact-occurrence inequalities areHere $k\ge 0$ is an integer. To prove both bounds, evaluate the truncated expression before taking its expectation. At an integer value $N=j\ge k$ it equalsFor $j=k$ this is one. For $j>k$, Pascal's identity, or an induction on $m$, givesFor $j<k$ the original expression is zero. Thus its difference from $1_{\{N=k\}}$ is everywhere nonnegative for even $m$ and nonpositive for odd $m$. Taking expectations proves the inequalities, including $k=0$.

For a general nonnegative integer-valued random variable, define its factorial moment by ${\mathbb{E}}_r(X)=\mathbb{E}(X{)}_r$, where $(X{)}_r$ is the falling factorial and ${\mathbb{E}}_0(X)=1$. The same pointwise calculation applies to $X$, so putEvery required moment is finite under the given limit assumption: eventual finiteness of higher factorial moments implies finiteness of the lower ones. The neighbouring upper and lower bounds differ in absolute value byThe last ratio tends to one, and the first factor involving the moment tends to zero. Since $\mathrm{Pr}(X=k)$ lies between every two such neighbouring bounds, each $T_m$ tends to it. Consequently the factorial-moment inversion isThis proves convergence of the signed series without an unjustified interchange with an expectation.

For any prescribed $r\ge 1$, take $\mathrm{Pr}(X=j)=C_r{j}^{-(r+2)}$ for $j=1,2,\dots$, with $C_r=[{\sum }_{j\ge 1}{j}^{-(r+2)}{]}^{-1}$. Since $(j{)}_r\sim j^r$ and $(j{)}_{r+1}\sim j^{r+1}$, the two moment sums have tails comparable respectively to $\sum j^{-2}$ and $\sum j^{-1}$. Thus ${\mathbb{E}}_r(X)<\infty$ but ${\mathbb{E}}_{r+1}(X)=\infty$, as required.

Let $Y$ be the number of isolated vertices and set $\lambda =e^{-c}$. For fixed $k\ge 1$, the falling factorial $(Y{)}_k$ counts ordered $k$-tuples of distinct isolated vertices. A specified tuple is isolated exactly when all edges incident to its vertices are absent. There are $k(n-k)+\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ such edges, soSince $np=\log n+c$ and $n{p}^2=o(1)$, taking logarithms givesThus every fixed factorial moment tends to ${\lambda }^k$. We use the standard factorial-moment criterion for Poisson convergence: nonnegative integer-valued random variables whose factorial moments converge, for every fixed order, to ${\lambda }^k$ converge in distribution to $\mathrm{Poisson}(\lambda )$. Consequently $Y$ has that limiting distribution, and its mass at each fixed integer converges. In particular,This establishes the limiting probability of at least one isolated vertex, rather than merely a bound based on its expectation.

For $n\ge 1$, the Bernstein polynomial isThe weights sum to one by the binomial theorem. Equivalently, if $K$ has the binomial distribution with parameters $n,x$, then $B_n(f;x)=\mathbb{E}f(K/n)$. This interpretation makes the cancellation of apparent high-degree terms transparent.

For the falling factorial $u^{\underline{r}}=u(u-1)\cdots (u-r+1)$, with $u^{\underline{0}}=1$, direct cancellation in the binomial weights givesThe polynomials $u^{\underline{0}},\dots ,u^{\underline{m}}$ form a monic triangular basis of the degree-at-most-$m$ polynomials. Hence $u^m=u^{\underline{m}}+{\sum }_{r<m}{c}_r{u}^{\underline{r}}$, andFor $m\le n$, its leading coefficient is $n^{\underline{m}}/n^m\ne 0$. If $p$ has actual degree $m$ and leading coefficient $a_m\ne 0$, linearity shows that the leading coefficient of $B_{n}p$ is $a_m{n}^{\underline{m}}/n^m$; lower-degree terms cannot cancel it. Thus the Bernstein polynomial degree preservation property givesThis includes the requested $m<n$, and also explains why the property cannot simply be extended to $m>n$.

The same moments give $\mathbb{E}K=nx$ and $\mathbb{E}{K}^2=n(n-1)x^2+nx$. ThereforeThe first two approximation errors vanish identically, whileAll three convergences are consequently uniform convergence on $[0,1]$.

Enumerate $A$ as $a_1,\dots ,a_a$. A function is specified by choosing the image of each of these elements independently, with $b$ possibilities each. The multiplication principle gives $\boxed{b^a\text{ functions}}$.

For an injective function, successive images must be distinct. If $a\le b$, there are $b$ choices for the first, $b-1$ for the second, and so on. If $a>b$, the pigeonhole principle makes injectivity impossible. Thus the number of injective functions isThe product in the first case is a falling factorial.

Put $N=m+1$ and $d=p+1$. Average $V={\prod }_{k=0}^p{1}_{A_k}(X_k)$ over all permutations of the first $N$ coordinates, as justified in part (a). For any prescribed ordered tuple of $d$ distinct images $({\ell }_0,\dots ,{\ell }_p)$, exactly $(N-d)!=(m-p)!$ permutations produce that tuple. ThereforeThe denominator is the falling factorial $(N{)}_d=N!/(N-d)!$, with exactly $p+1$ factors. The sum must be over ordered distinct tuples: its $k$th coordinate is attached to $A_k$, and these sets need not be equal. This is the finite-sample version of symmetrization as conditional expectation.

The original PDF, as well as the TeX, prints the final factor as $m+1-p+1$. That is an off-by-one error: it must be $m+1-p$. With every $A_k=\mathbb{R}$, the conditional expectation is one and the numerator counts exactly $(N{)}_d$ ordered distinct tuples. This forces the normalization above and immediately detects the printed error. Interpreting the sum as unordered subsets would likewise give the wrong normalization and would lose the assignments to the different $A_k$.

Write $j^{\underline{m}}=j(j-1)\cdots (j-m+1)$ for the falling factorial. At the sampling points, $f_{nm}(j/n)=n^{-m}{j}^{\underline{m}}$, which vanishes for $j<m$. For $j\ge m$, cancellation of the factorials givesInsert this into the Bernstein polynomial and set $\ell =j-m$:The binomial theorem evaluates the remaining sum. For $m=0$, both sides equal one. This proves the Bernstein falling-factorial identity $B_n(f_{nm},x)=f_{nm}(1)x^m$.