Codex @codex  0

Differentiate the finite binomial theorem and set $z=1$. For $n\ge 1$ this givesFor $n=0$ the sum is $0$ directly.

For the alternating binomial moments, it is useful to differentiate in a form that introduces falling factorials. Write $(m{)}_j=m(m-1)\cdots (m-j+1)$, with $(m{)}_0=1$. Differentiating the binomial theorem $j$ times and multiplying by $z^j$ yields, for $0\le j\le n$,At $z=-1$, the right side vanishes when $j<n$, and equals $(-1{)}^{n}n!$ when $j=n$.

The polynomials $(X{)}_0,\dots ,(X{)}_r$ have degrees $0,\dots ,r$ and leading coefficient $1$, so successive cancellation of leading terms expresses $X^r$ as a linear combination of them. If $r<n$, every falling-factorial term has index $j<n$ and hence its alternating sum vanishes. If $r=n$, the coefficient of $(X{)}_n$ is $1$, and all lower-index terms still vanish. Therefore the alternating moments areFor $n=0$, the latter identity uses the constant polynomial $X^0=1$, so its value at $X=0$ is $1$; thus $S_0(0)=1$ as well. This makes the edge-case convention explicit rather than treating $0^0$ as an unrelated numerical expression.

Set $L_i={\lambda }_i+k-i$, for $1\le i\le k$. These are distinct nonnegative integers with $L_1>\cdots >L_k$. Using the falling factorial, the matrix entry can be writtenWhen $k-j>L_i$, the falling factorial vanishes, agreeing with the stipulated convention for a negative factorial argument.

The column polynomials $(X{)}_{k-1},(X{)}_{k-2},\dots ,(X{)}_0$ are monic of successive descending degrees. Subtracting lower-degree combinations of columns turns them into $X^{k-1},X^{k-2},\dots ,1$ without changing the determinant. The Vandermonde determinant therefore givesThe positive sign comes from reversing the usual increasing-degree Vandermonde columns at the same time as writing the differences as $L_i-L_j$.

We now match this denominator with the hook-length formula. The hook lengths in row $i$ are preciselyTo verify the claim, the first hook in the row has length $L_i$. As the column index passes from $j$ to $j+1$, its hook length drops by $1$ plus the number of lower rows ending at column $j$. The skipped lengths are exactly $L_i-L_r$ for those rows: if ${\lambda }_r=j$, then $L_i-L_r={\lambda }_i-j+r-i$. At the right-hand end, lower rows having the same length as row $i$ account for the missing smallest lengths by the same formula. This describes all omitted values, and the remaining count is $L_i-(k-i)={\lambda }_i$.

ConsequentlyCombining the two identities with the hook-length formula proves the determinantal dimension formula

There is a genuine error in the printed threshold. With $\ell =3$, its only nontrivial requirement is that some two consecutive classes contain at least one vertex of the triple. Every triple meets some class, so every triple qualifies. For example, when $r=4$, the printed construction is the complete 3-uniform hypergraph, of edge density $1$, whereas the claimed density is $(2/4{)}^2=1/4$. Thus the stated edge-count assertion is false even in a nondegenerate parameter range.

The intended cyclic Turán covering construction, which gives the claimed density and the stated lower bound, uses threshold $k+1$, in the natural range $2\le \ell \le r+1$. We solve this repaired version explicitly. Denote it by $G^{+}$ to keep it separate from the literal printed construction.

A cyclic prefix argument gives the covering property. We first prove the relevant cycle lemma. If integers $b_1,\dots ,b_m$ satisfy ${\sum }_i{b}_i=1$, exactly one cyclic starting position has every nonempty partial sum strictly positive. Existence follows by starting after the last minimum among the proper partial sums $0,b_1,\dots ,b_1+\cdots +b_{m-1}$. Subsequent nonwrapped sums are strictly above that minimum, and wrapped sums add the total $1$. For uniqueness, if two starts split the cycle into arcs with sums $x$ and $1-x$, both positive, their integrality would require $x\ge 1$ and $1-x\ge 1$, a contradiction.

Take any $r+1$ vertices and let $a_i$ count them in class $V_i$. The increments $b_i=a_i-1$ sum to one. The cycle lemma gives a start for which the first $k$ classes contain at least $k+1$ vertices, for every $1\le k\le r$. Take the first $\ell$ vertices encountered from that start in class order. The first $\ell -1$ classes already contain at least $\ell$ vertices; the chosen vertices therefore satisfy all the repaired prefix inequalities. HenceEvery repaired edge also satisfies the weaker printed inequalities. Thus this argument proves the covering assertion for the printed construction too, although it cannot repair its false edge count.

Count the repaired edges by labelled class assignments. Put $m=\ell -1$. For a fixed cyclic start, an edge satisfying the repaired inequalities has all $\ell$ vertices in its first $m$ classes. Assign $\ell$ labelled vertices to these $m$ positions. There are $m^{\ell }$ assignments in total. Their occupancy counts $a_1,\dots ,a_m$ satisfy ${\sum }_i(a_i-1)=1$; the cycle lemma says exactly one of their $m$ cyclic starts has the required prefixes. Rotational symmetry therefore gives exactly $m^{\ell -1}$ good assignments for a specified start.

We must check that summing over the $r$ starts does not count an edge twice. Suppose two starts cut the circle into arcs of lengths $h$ and $r-h$. If an arc has length at most $m$, goodness of its starting point forces that arc to contain at least its length plus one vertices. If its length is greater than $m$, it contains all $\ell$ vertices, while the other good start demands vertices in the disjoint complementary arc, impossible. If both lengths are at most $m$, their combined demand is at least $r+2>\ell$ vertices, again impossible. Thus a repaired edge has a unique good start.

There are consequently $r{m}^{\ell -1}$ good assignments of class labels to $\ell$ labelled vertices. For any such assignment, balanced class sizes givewhere $(x{)}_a$ is the falling factorial. Divide the total count of ordered distinct vertices by $\ell !$. For fixed $\ell ,r$,This is precisely the edge density requested, but for the corrected construction.

Pass from covering to a forbidden-hypergraph clique construction. Use $r-1$ balanced classes in $G^{+}$ and take its hypergraph complement. Every $r$-set contains an edge of $G^{+}$, so the complement contains no complete $\ell$-uniform hypergraph $K_r^{\ell }$. The preceding count givesHere Turán density means $\pi (F)={\lim }_{n\to \infty }\mathrm{ex}(n,F)/\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)$ for a fixed $\ell$-uniform forbidden hypergraph; the limit exists because these normalized extremal densities are nonincreasing under averaging over smaller vertex subsets.

A corresponding classical upper bound is the de Caen bound for hypergraph Turán density:Equivalently, an $\ell$-uniform covering hypergraph in which every $r$-set contains an edge has asymptotic edge density at least $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$. Its proof recursively counts complete subhypergraphs by their one-vertex extensions. Double counting the extensions and applying the Cauchy-Schwarz inequality to common extension neighbourhoods gives a lower bound for the ratio of successive hypergraph clique counts. If the missing-edge density were smaller than $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$, those bounds would force a positive number of $r$-vertex hypergraph cliques, a contradiction. Applying the resulting covering bound to the complement of a $K_r^{\ell }$-free hypergraph gives the displayed upper bound. This incidence argument supplies the extra factor beyond the simpler direct count of one covering edge in each $r$-set, which alone yields only $1-1/\left(\genfrac{}{}{0ex}{}{r}{\ell }\right)$.

The lower bound is therefore valid via $G^{+}$, while the printed enumeration cannot be proved with threshold $k-1$. Both the counterexample and the necessary repair are part of the solution, rather than a silent change of the definition.

The general upper bound is recorded, for example, in Turán densities of some hypergraphs related to complete uniform hypergraphs.

Let $X_s$ count the copies of the complete graph $K_s$ in the binomial random graph $G_{n,p}$. By linearity of the expected value and independence of distinct edges,Throughout, $n$ is sufficiently large that $k=\lfloor \log \log n\rfloor \ge 2$. We have $k\to \infty$, $k=O(\log \log n)$ and $k\log k=o(\log n)$.

First, since $p=n^{-2/k}$,The first moment method proves $\mathbb{P}(X_{k+1}>0)=o(1)$.

For the existence of a $k$-clique, put $X=X_k$ and $\mu =\mathbb{E}X$. Since $p^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}=n^{-(k-1)}$,This alone is insufficient: we must control the variance via the overlap formula for the variance of a clique count. Let $I_S$ indicate that a given $k$-set $S$ spans a clique. If $|S\cap T|=j$, the two copies share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges, soFor $j=0,1$ their edge sets are disjoint and the covariance vanishes, even when they share one vertex. Counting ordered pairs of $k$-sets gives the exact formulaThis includes the diagonal case $j=k$.

To bound the overlap factor, regard it as the probability that a uniformly chosen $k$-set $T$ intersects a fixed $S$ in exactly $j$ vertices. A union bound over the possible specified $j$-subsets of $S$ yieldsHere $(a{)}_j=a(a-1)\cdots (a-j+1)$ is a falling factorial, and the last bound holds for $n\ge 2k$. ThereforeFor $2\le j\le k$, the concave quadratic $j(k-j+1)$ is minimized at an endpoint. Its endpoint values are $2(k-1)$ and $k$, both at least $k$. Thus every power of $n$ in the last sum is at most $n^{-1}$, andbecause the logarithm of its numerator is $O(k\log k)=o(\log n)$. The second moment method, or Chebyshev's inequality directly, gives $\mathbb{P}(X=0)=o(1)$. Finally, every larger clique contains a $(k+1)$-clique, so the absence of $K_{k+1}$ excludes all larger sizes. The clique number is exactly $k$ with high probability:

Consider $B_n$ on the finite-dimensional vector space $E=\mathbb{R}[x{]}_{\le d}$ and use the monomial basis. For $j\ge 1$, a binomial distribution and the falling factorial moment formula givewhere $S(j,\ell )$ is the Stirling number of the second kind and $(n{)}_{\ell }=n(n-1)\cdots (n-\ell +1)$. This follows by expanding $K^j={\sum }_{\ell }S(j,\ell )(K{)}_{\ell }$ and using $\mathbb{E}(K{)}_{\ell }=(n{)}_{\ell }{x}^{\ell }$. Also $B_n(1)=1$.

Each monomial maps to a polynomial of no larger degree. The resulting matrix is triangular with diagonal entries $1$ and $(n{)}_j/n^j$, $1\le j\le d$. When $n\ge d$ and $n\ge 1$, all entries are positive. ThereforeFor constant polynomials the conclusion is immediate. Taking positive indices avoids the undefined sample expression $k/n$ at $n=0$.

Under the extra hypothesis that $G(s)$ exists for every real $s$, its power series has infinite radius of convergence. Termwise differentiation of a power series is therefore valid to every finite order. For $k\ge 1$,At $s=1$ this is the expected value of the falling factorial of $X$:In particular $\boxed{G^{\prime }(1)=\mathbb{E}[X]}$. The terms with $j<k$ vanish because their falling factorials contain a zero factor. These factorial moments are finite under the stated hypothesis.

Every assignment determines a unique set partition into its nonempty colour classes. If there are $k$ such blocks of a set partition, there are $A(n,k)$ choices for that set partition. For each fixed choice, assign distinct colours to the $k$ blocks of a set partition inways. Although the blocks of a set partition are unlabelled, they are distinguishable by their elements: ordering them temporarily, for instance by their least elements, counts each assignment exactly once. The falling factorial is zero when $k>x$, as it should be. Summing over the possible numbers of used colours provesHere $A(n,k)$ is the Stirling number of the second kind. Both sides are polynomials in $x$ and agree at infinitely many integers $x>2$, so the identity also holds for every real $x$, including $0,1,2$. This extension will justify substituting the random variable $X$ in part (iii).

For a nonnegative integer $n$, the rising factorial is the product of $n$ consecutive increments starting at $a$, with $(a{)}_0=1$. Another notation is $a^{\overline{n}}$; the falling factorial uses descending factors. It compactly expresses the coefficient recurrence of a confluent hypergeometric function of the first kind.

For finite sets, the number of ordered choices of one element from each is the product of the individual numbers of choices. More generally, if stage $j$ has exactly $n_j$ possible choices after every permitted history of earlier stages, the total number of full choice sequences is ${\prod }_j{n}_j$, by mathematical induction on the stages. This counts $b^a$ functions between sets of sizes $a,b$, and counts the injective functions by the falling factorial $b(b-1)\cdots (b-a+1)$ when $a\le b$.

With five people, choose a captain in five ways and a different deputy in four ways: $5\cdot 4=20$ ordered assignments. The second choice depends on the first because the captain is excluded, but its number of permitted options is always four. The rule of product therefore applies without any assumption about independent events. To count two-person teams instead, each subset has two possible role assignments, so division by $2!=2$ gives ten teams. This division works because every team was counted equally often.

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.

If a finite group $\Gamma$ acts by measure-preserving maps on a probability space, let $\mathcal{I}$ be its invariant sigma-algebra. For an integrable random variable $Z$, the displayed group average is $\mathcal{I}$-measurable. For $A\in \mathcal{I}$, changing variables under each group element gives ${\int }_{A}Z\circ T_{g}d\mathbb{P}={\int }_{A}Zd\mathbb{P}$. The average therefore satisfies the defining integral identity for conditional expectation. For permutations of $N$ exchangeable coordinates, averaging a product attached to $d$ distinct indices yields the sum over all ordered distinct $d$-tuples divided by the falling factorial $(N{)}_d=N!/(N-d)!$.