User:Natalia L. Skirrow/an introduction to Stirling numbers

foreword

This page is called introductory, and the intention is to require only familiarity with ideas of generating functions and linear algebra, but the subject has some extremely interesting parts that require more advanced methods. An elementary formulation is given for #Ramanujan's master theorem, but in #asymptotics and properties as statistical distributions, Hayman's saddle point method from ^[1] is used without duplicating its (quite involved) explanation. #recurrence relations lies at the very end, because an important part of it requires the Bernoulli/Gregory theory established first.

tools

Let $((\binom{n}{k})) = (\binom{n + k - 1}{k})$ be the number of ways to form a $k$ -multiset from an $n$ -set by drawing with repetition.

We use generating functions; these encode sequences as functions to represent operations on them; in particular, the ordinary g.f. is $o g f (a) = \sum_{n = 0}^{\infty} a (n) x^{n}$ , and the exponential g.f. $e g f (a) = \sum_{n = 0}^{\infty} a (n) \frac{x^{n}}{n!}$ .

Multiplying g.f.s convolves their sequences in different ways; $\underset{o g f}{c o n v} (\binom{f}{g}) (n) = \sum_{k = 0}^{n} f (k) g (n - k)$ and $\underset{e g f}{c o n v} (\binom{f}{g}) (n) = \sum_{k = 0}^{n} (\binom{n}{k}) f (k) g (n - k)$

$k!$ and $H_{k}^{(n)}$ are treated as complex functions, $Γ (k + 1)$ and $\frac{(- 1)^{n - 1}}{(n - 1)!} ψ_{n - 1} (k + 1) + ({\begin{cases} γ & n = 1 \\ ζ (n) & e l s e \end{cases})$

The notations used here ( $[\binom{n}{k}]$ and ${\binom{n}{k}}$ ) are due to Jovan Karamata from 1935

The l'hospital theorem is used implicitly; specifically, when dividing two functions at a point where both have simple poles (which is done a lot in #Ramanujan's master theorem), we consider the quotient of their residues

calculus of finite differences

We define $Δ (f) (x) = f (x + 1) - f (x)$ and $\nabla (f) (x) = f (x) - f (x - 1)$ , and the falling and rising factorials $x^{\underline{n}} = \frac{x!}{(x - n)!}$ and $x^{\overline{n}} = \frac{(x + n - 1)!}{(x - 1)!}$ .

In particular, these operators $Δ$ and $\nabla$ are o.g.f. convolutions with $\frac{1}{x} - 1$ and $1 - x$ , respectively, so by binomial-expanding their exponents, their higher-order iterates are $Δ^{n} (f) (x) = \sum_{i = 0}^{n} (\binom{n}{i}) (- 1)^{n - i} f (x + i)$ and $\nabla^{n} (f) (x) = \sum_{i = 0}^{n} (\binom{n}{i}) (- 1)^{i} f (x - i)$ (with negative iterates $Δ^{- n} (f) (k) = \sum_{i = 0}^{k - n} (\binom{k - 1 - i}{n - 1}) f (i)$ ).

Similarly to how a holomorphic function is converged to by the evaluation of its power series $f (x) = \sum_{n = 0}^{\infty} f^{(n)} (0) \frac{x^{n}}{n!}$ , sequences are 'converged' to (eventually matched at all indexes by) the evaluation of their inverse binomial transforms; $f (k) = \sum_{n = 0}^{k} Δ^{n} (f) (0) (\frac{x^{\underline{n}}}{n!} : = (\binom{x}{n}))$ and $f (k) = \sum_{n = 0}^{k} \nabla^{n} (f) (0) (\frac{x^{\overline{n}}}{n!} : = (\binom{x + n - 1}{n}))$ ; as such, one can write $Δ^{n} (f) (0) = [(\binom{x}{n})] f (x)$ and $\nabla^{n} (f) (0) = [((\binom{x}{n}))] f (x)$

We as such define a quartet of analogues,

\begin{aligned} o g f (a) & = \sum_{n = 0}^{\infty} a (n) x^{n} & e g f (a) & = \sum_{n = 0}^{\infty} a (n) \frac{x^{n}}{n!} \\ f g f (a) & = \sum_{n = 0}^{\infty} a (n) x^{\underline{n}} & b g f (a) & = \sum_{n = 0}^{\infty} a (n) (\binom{x}{n}) \\ r g f (a) & = \sum_{n = 0}^{\infty} a (n) x^{\overline{n}} & m g f (a) & = \sum_{n = 0}^{\infty} a (n) ((\binom{x}{n})) \end{aligned}

The 'factorial powers' (Pochhammer symbols) are joined by $x^{\underline{n}} = (x - n + 1)^{\overline{n}}$ , $x^{\underline{n}} = (- 1)^{n} (- x)^{\overline{n}}$ and $x^{\underline{- n}} = \frac{1}{(x + 1)^{\overline{n}}}$ , and work similarly to monomials in that (see Concrete Mathematics, page 53, eq. (2.53))

\begin{aligned} Δ x^{\underline{n}} & = n x^{\underline{n - 1}} & \frac{d}{d x} x^{n} & = n x^{n - 1} & \nabla x^{\overline{n}} & = n x^{\overline{n - 1}} \\ \sum_{x = a}^{b - 1} x^{\underline{n}} & = {\begin{cases} H_{b} - H_{a} & n = - 1 \\ \frac{b^{\underline{n + 1}} - a^{\underline{n + 1}}}{n + 1} & n \neq - 1 \end{cases} & \int_{x = a}^{b} x^{n} & = {\begin{cases} \log (b) - \log (a) & n = - 1 \\ \frac{b^{n + 1} - a^{n + 1}}{n + 1} & n \neq - 1 \end{cases} & \sum_{x = a + 1}^{b} x^{\overline{n}} & = {\begin{cases} H_{b} - H_{a} & n = - 1 \\ \frac{b^{\overline{n + 1}} - a^{\overline{n + 1}}}{n + 1} & n \neq - 1 \end{cases} \end{aligned}

(in fact, the rules for the calculus of infinitesimal differences comes from 'zooming out' in both the input and output axes on this calculus of finite differences)

finally, the binomial theorem has falling and rising analogues; $\sum_{k = 0}^{n} (\binom{n}{k}) x^{\underline{k}} y^{\underline{n - k}} = n! \sum_{k = 0}^{n} (\binom{x}{k}) (\binom{y}{n - k}) = (\binom{y}{n})_{2} F_{1} (\binom{- n, - x}{1 - n + y}; 1) = (x + y)^{\underline{n}}$ (using Gauss's hypergeometric theorem; the falling-rising joining identity directly brings it to the equivalent rising factorial identity)

power-analogue notations

It is useful to bear in mind the combinatorial definitions of these powers (and some more that we will variously see along the way);

$x^{n}$ counts functions from $[n]$ to $[x]$
$x^{\underline{n}} = n! (\binom{x}{n})$ counts injective functions
$x^{\overline{n}} = n! ((\binom{x}{n}))$ counts functions with preimages totally ordered into lists
$x^{{n}} = x! {\binom{n}{x}}$ counts surjective functions (a proposal from ^[2])
$x^{[n]} = x! [\binom{n}{x}]$ counts surjections with preimages cyclically ordered
$x^{(n)} = x! L a h (\binom{n}{x}) = n! (\binom{n - 1}{x - 1})$ counts surjections with preimages totally ordered (note this deviates from some sources (like the Wikipedia page) which use this notation to mean $x^{\overline{n}}$ )

while the product definition lets us evaluate Pochhammer symbols like $x^{\overline{a}}$ on noninteger $x$ , the gamma function lets us compute them on noninteger $a$ ! ^[3] provides the inequality $1 \leq \frac{x^{a}}{x^{\overline{a}}} \leq {(1 + \frac{a}{x})}^{1 - a}$ for $a \in [0, 1]$ , with equality at boundaries; taking series expansions shows that as $x \to \infty$ , the logarithms of the bounds' error ratios converge; $\log (\frac{x^{a}}{x^{\overline{a}}}) \sim \log (\frac{{(\frac{a}{x} + 1)}^{1 - a}}{x^{a} / x^{\overline{a}}})$ , so the lower inequality is about as good as the upper one; the inequalities both flip into $\leq$ s for $a \geq 1$ and the now-upper bound continues to work as an approximately-as-good counterpart to the obvious one. (see also Gautschi's inequality)

binomial transforms

the sequence $\overline{f} (n) = Δ^{n} (f) (0)$ (the inverse binomial transform, analogous to the power series) can be considered as a linear transformation on vector spaces $(\begin{matrix} \overline{f} (0) \\ \overline{f} (1) \\ \overline{f} (2) \\ ⋮ \end{matrix}) = (\begin{matrix} 1 & 0 & 0 & \dots \\ - 1 & 1 & 0 & \dots \\ 1 & - 2 & 1 & \dots \\ ⋮ & ⋮ & ⋮ & ⋱ \end{matrix}) \cdot (\begin{matrix} f (0) \\ f (1) \\ f (2) \\ ⋮ \end{matrix})$ , we can take its inverse, $(\begin{matrix} f (0) \\ f (1) \\ f (2) \\ ⋮ \end{matrix}) = (\begin{matrix} 1 & 0 & 0 & \dots \\ 1 & 1 & 0 & \dots \\ 1 & 2 & 1 & \dots \\ ⋮ & ⋮ & ⋮ & ⋱ \end{matrix}) \cdot (\begin{matrix} \overline{f} (0) \\ \overline{f} (1) \\ \overline{f} (2) \\ ⋮ \end{matrix})$

can be represented as an e.g.f. convolution, $e g f (\overline{f}) (x) = e^{- x} e g f (f) (x)$ , and as an o.g.f. $o g f (\overline{f}) (x) = \frac{o g f (f) (\frac{x}{1 + x})}{1 + x}$ (so $o g f (f) (x) = \frac{o g f (\overline{f}) (\frac{x}{1 - x})}{1 - x}$ )

since (when computing $x^{n}$ ) we can choose $k$ outputs to have preimages, we have $x^{n} = \sum_{k = 0}^{x} (\binom{x}{k}) k^{{n}}$ ; that is, $λ n . x^{n}$ is the binomial transform of $λ n . x^{{n}}$ . By the same reasoning elsewhere, we have

\begin{aligned} x^{n} & = \sum_{k = 0}^{x} (\binom{x}{k}) k^{{n}} & x^{{n}} & = \sum_{k = 0}^{x} (- 1)^{x - k} (\binom{x}{k}) k^{n} = Δ^{x} (λ k . k^{n}) (0) \\ x^{\tilde{n}} & = \sum_{k = 0}^{x} (\binom{x}{k}) k^{[n]} & x^{[n]} & = \sum_{k = 0}^{x} (- 1)^{x - k} (\binom{x}{k}) k^{\tilde{n}} = Δ^{x} (λ k . k^{\tilde{n}}) (0) \\ x^{\overline{n}} & = \sum_{k = 0}^{x} (\binom{x}{k}) k^{(n)} & x^{(n)} & = \sum_{k = 0}^{x} (- 1)^{x - k} (\binom{x}{k}) k^{\overline{n}} = Δ^{x} (λ k . k^{\overline{n}}) (0) \end{aligned}

Faà di Bruno's formula

In this case, is the statement "if you have two sequences $a (n), b (n)$ , counting the numbers of type- $a$ and type- $b$ structures on $n$ -element labelled sets, with e.g.f.s $A (x), B (x)$ , then $[\frac{x^{n}}{n!}] A (B (x))$ (denoted $a (b) (n)$ ) is the number of ways to put $n$ elements into type- $b$ objects, then put these into a type- $a$ object."

In particular, we can associate the exponent of $B (x)$ with another variable $y$ , to get that $[\frac{x^{n}}{n!} y^{k}] A (y B (x))$ is the number of ways to put $n$ elements into $k$ $b$ -objects in one $a$ -object.

the most important sequences in this case are $s e t s (n) = 1$ , $c y c l e s (n) = (n - 1)!$ , $l i s t s (n) = n!$ (with e.g.f.s $e^{x}$ , $\log (\frac{1}{1 - x})$ and $\frac{1}{1 - x}$ ).

Note that cycles must be nonempty, but for the other two we subtract $1$ from the e.g.f.s to count their nonempty forms; we denote this with an overline.

examples

$S e t s (C y c l e s (x)) = e^{\log (\frac{1}{1 - x})} = \frac{1}{1 - x} = L i s t s (x)$ , meaning there is a bijection between lists and sets of cycles (ie. permutations' cycle decompositions).

if both $a$ - and $b$ -type structures are totally ordered (ie. in both, each instance of an $n$ -node structure is part of an equivalence class of $n!$ that are node-permutations of each other, and the $n$ th terms of both are divisible by $n!$ ), then the $n$ nodes can be considered unlabelled to divide by $n!$ (considering their e.g.f.s as o.g.f.s). In particular, this means that o.g.f. composition for sequences on unlabelled sets imbues total orderings on all but the leaf nodes of the partition-tree.

$L i s t s (\overline{L i s t s} (x)) = \frac{1}{1 - \frac{x}{1 - x}} = \frac{1 - x}{1 - 2 x}$ , and (for $k \geq 1$ ) there are $\underset{n t i m e s}{\underset{⏟}{l i s t s (\overline{l i s t s} (\dots \overline{l i s t s} (}} k) \dots)) = [x^{k}] \frac{1 - (n - 1) x}{1 - n x} = n^{k - 1}$ ways to put $k$ unlabelled objects into a tree of lists $n$ layers deep (since $\frac{1 - (n - 1) \frac{x}{1 - x}}{1 - n \frac{x}{1 - x}} = \frac{1 - n x}{1 - (n + 1) x}$ ). Equivalently, this is the number of ways to arrange brackets around $k$ points such that each of them is $n$ layers deep, and all bracket-pairs contain at least one point.
allowing all lists to contain singletons instead of only the depth- $n$ ones can be recursively constructed 'from the leaves up'; we define $f_{0} = 0$ and thereafter $F_{n} (x) = \frac{F_{n - 1} (x)^{2}}{1 - F_{n - 1} (x)} + x$ ; ie. must be a singleton or contain at least two members of the previous iteration.

this is difficult to analyse directly, but the fixed point of this iteration, $F_{\infty}$ , is not! Since the recurrence is in terms of itself rather than the preceding iterate, by the quadratic formula we get $\frac{1 + x - \sqrt{1 - 6 x + x^{2}}}{4}$ , the functional inverse of $\frac{x (1 - 2 x)}{1 - x}$ , and so f_∞(k)=A001003(k-1).

since its inverse's derivative,

2 - \frac{1}{(1 - x)^{2}}

, becomes zero at

x = 1 - \frac{1}{\sqrt{2}}

, at which the inverse's maximum is

3 - \sqrt{8}

, this is

F_{\infty}

's radius of convergence, so

\frac{f_{\infty} (k)}{f_{\infty} (k - 1)} \sim 3 + \sqrt{8}

Stirling-type triangles

cycle numbers (|A008275|,A132393)

As mentioned, a permutation is a set of cycles, so we define $[\binom{n}{k}] = [\frac{x^{n}}{n!} y^{k}] (S e t s (y C y c l e s (x)) = e^{y \log (\frac{1}{1 - x})} = \frac{1}{(1 - x)^{y}})$ .

Since $[\frac{x^{n}}{n!}] \frac{1}{(1 - x)^{d}} = n! ((\binom{d}{n})) = d^{\overline{n}}$ (the g.f. for a general degree- $d$ polynomial is some degree- $d$ numerator times this), we have $\sum_{k = 0}^{n} [\binom{n}{k}] y^{k} = y^{\overline{n}}$ , so can write $[\binom{n}{k}] = [y^{k}] y^{\overline{n}}$ . (The reason for the unfortunate historical use of $s (n, k) = (- 1)^{n - k} [\binom{n}{k}]$ is that this gives $s (n, k) = [y^{k}] y^{\underline{n}}$ .)

We can form a correspondence; adding an $n + 1$ th element to a length- $n$ permutation can be done by

choosing one of the $n$ existing elements, mapping the $n + 1$ th to it, and mapping its previous preimage to the $n + 1$ th
mapping the $n + 1$ th to itself

in particular, each permutation has $n + 1$ successors, but each of the resultant $n + 1$ -element permutations has only one preimage. Specifically, in $[\binom{n + 1}{k}]$ there are $n$ elements for each in $[\binom{n}{k}]$ and one for each in $[\binom{n}{k - 1}]$ , giving $[\binom{n + 1}{k}] = n [\binom{n}{k}] + [\binom{n}{k - 1}]$ .

for the representation in elementary symmetric polynomials and a bijective proof of its rook-theoretic interpretation, see Stirling factoradics

subset numbers (A008277,A048993)

These count partitions into sets of nonempty sets; ${\binom{n}{k}} = [\frac{x^{n}}{n!} y^{k}] (S e t s (y \overline{S e t s} (x)) = e^{y (e^{x} - 1)})$

By binomial-expanding the e.g.f. for the $k$ th column, $\frac{(e^{x} - 1)^{k}}{k!} = \frac{\sum_{i = 0}^{k} (\binom{k}{i}) (- 1)^{k - i} e^{i x}}{k!} = \frac{Δ^{k} (λ i . e^{i x}) (0)}{k!}$ ; the coefficient of $\frac{x^{n}}{n!}$ is ${\binom{n}{k}} = \frac{Δ^{k}}{k!} (λ i . i^{n}) (0) = \frac{[(\binom{x}{k})] x^{n}}{k!} = [x^{\underline{k}}] x^{n}$ .

By the same kind of argument as the cycle numbers, the $n + 1$ th element can be placed in its own set (in one way) or one of the $k$ existing sets (in $k$ ways), giving ${\binom{n + 1}{k}} = k {\binom{n}{k}} + {\binom{n}{k - 1}}$ .

Writing ${\binom{n}{k}}$ as $[x^{n}] f_{k} (x)$ , this becomes $(1 - k x) f_{k} (x) = x f_{k - 1} (x)$ . Since $f_{0} (x) = 1$ , the column o.g.f. is $f_{k} (x) = \prod_{i = 1}^{k} \frac{x}{1 - i x}$ , which the e.g.f. binomial expansion thus shows partial-fraction-decomposes to $\sum_{i = 0}^{k} \frac{(- 1)^{k - i}}{i! (k - i)!} \frac{1}{1 - i x}$ .

The product form is rewritable in factorial powers as $\frac{1}{{(\frac{1}{x} - 1)}^{\underline{k}}}$ , which (by the last joining identity) equals ${(\frac{1}{x})}^{\overline{- k}}$ . This means that according to the o.g.f.s of their columns and rows respectively (interpreting negative-exponent rising factorials as Puiseux series from $x = \infty$ instead of $0$ ), we have ${\binom{n}{k}} = [\binom{- k}{- n}]$ .

this can be equivalently written exceedingly elegantly (using the Pochhammer reflection identities on binomial coefficients) as $\frac{1}{(\binom{\frac{1}{x} - 1}{k})} = \sum_{i = 0}^{k} \frac{(\binom{\sim i}{\sim k})}{1 - i x}$

note that by expanding out the denominator of the column g.f.s, one gets the linear recurrence ${\binom{n}{k}} = \sum_{i = 0}^{k - 1} [\binom{k + 1}{k - i}] (- 1)^{i} {\binom{n - 1 - i}{k}}$ . The cycle numbers, meanwhile, cannot be similarly decomposed into a simple summation; using the polynomiality of the diagonals of the conjoined triangle (see ^[4], page 11) and the polynomials' linear recurrences (see my MathOverflow answer), the cycle numbers can be computed in a singly-nested sum involving subset numbers, translating to a doubly-nested sum over elementary functions; no singly-nested such sum is known for them.

see also rook configurations for how ${\binom{n}{n - k}}$ enumerates nonattacking $k$ -rook configurations beneath the diagonal in an $n \times n$ chessboard

Lah numbers (|A008297|,A271703)

These count sets of nonempty lists, and have a closed form directly from their e.g.f., making them exceptional in a few ways; $L a h (\binom{n}{k}) = [\frac{x^{n}}{n!} y^{k}] e^{\frac{x y}{1 - x}} = [\frac{x^{n}}{n!}] \frac{{(\frac{x}{1 - x})}^{k}}{k!} = \frac{n!}{k!} (\binom{n - 1}{k - 1})$

The combinatorial interpretation of said closed form is pretty straightforward; since $(\binom{n - 1}{k - 1})$ enumerates ways to place $k - 1$ partitions in the $n - 1$ intervals of a length- $n$ unlabelled list, to split it into an ordered list of $k$ subsections (identified only by their lengths); we multiply by $n!$ to make it totally-ordered, then divide by $k!$ to count equivalence classes under permutations of the subsections.

The combinatorial interpretation directly yields the generatingfunctionological one; for each $j$ -cycle permutation, partition the cycles into $k$ subsets, then use these sets of cycles as permutations, ie. lists (either by interpreting them as a map or by Foata's transformation fondamentale)

L a h (\binom{n}{k}) = \sum_{j = k}^{n} [\binom{n}{j}] {\binom{j}{k}}

which can be rewritten

L a h (\binom{n}{k}) = \sum_{j = k}^{n} [x^{j}] x^{\overline{n}} [x^{\underline{k}}] x^{j} = [x^{\underline{k}}] x^{\overline{n}}

(which is a direct consequence of the Pochhammer-binomial theorem where $y = n - 1$ , and can be rewritten as $(\binom{n - 1}{k - 1}) = [\frac{x^{\underline{k}}}{k!}] \frac{x^{\overline{n}}}{n!} = [(\binom{x}{k})] ((\binom{x}{n}))$ )

Note that since the ratio between two Lah numbers at a constant displacement in the Lah triangle is a rational function of their coordinates, the row and diagonal o.g.f.s are hypergeometric! $L a h (\binom{n}{k}) = n! [y^{k - 1}]_{1} F_{1} (\binom{1 - n}{2}; - y)$ and $L a h (\binom{n + k}{k}) = [x^{k}] n!_{2} F_{1} (\binom{n, n + 1}{2}; x) = [x^{k}] n! \frac{_{2} F_{1} (\binom{2 - n, 1 - n}{2}; x)}{(1 - x)^{2 n - 1}}$ . The latter (obtained by Euler's hypergeometric reflection formula) is interesting, because the $n$ th diagonal's g.f.'s numerator is the g.f. of the $n - 1$ th row of the Narayana triangle A001263, so $L a h (\binom{n + k}{k}) = (n + 1)! ((\binom{k}{2 n}))_{3} F_{2} (\binom{1 - n, - n, 1 - k}{1 - 2 n - k, 2}; 1) = (n + 1)! \sum_{i = 0}^{n} ((\binom{k - i}{2 n})) N a r a y a n a (\binom{n}{i + 1})$ .

In fact,

N a r a y a n a (\binom{n}{k + 1})

has some equivalent definitions

the number of strict order-homomorphisms from a $k \times 2$ array (considered as a poset, with each pair of elements $i, j$ ordered by $i \leq j ⟺ i_{x} \leq j_{x} \land i_{y} \leq j_{y}$ ) to a length- $n$ list (ie. such that for two elements $i, j$ , $i < j$ implies the same about the indexes their mapped to in the list, $l (i) < l (j)$ ).
pairs of strictly increasing length- $k$ lists $a, b$ with elements $[0 . . n)$ such that for all $i$ , $a_{i} > b_{i}$
pairs of monotonically-increasing length- $n$ lists $A, B$ with elements $[0 . . k)$ (where $i$ th term is first index in which an element $\geq i$ appears in the previous bullet point's lists) such that for all $i$ , $A_{i + 1} \leq B_{i}$

general matrix multiplications!

In general, for a Stirling-type array $a (n, k) = [\frac{x^{n}}{n!} y^{k}] e^{y A (x)}$ and a slightly more general array $b (n, k) = [\frac{x^{n}}{n!} y^{k}] e^{\overline{B} (y) B (x)}$ ,

\begin{aligned} \sum_{j = 0}^{n} a (n, j) b (j, k) & = \sum_{j = 0}^{\infty} [\frac{x^{n}}{n!} y^{j}] e^{y A (x)} [\frac{x^{j}}{j!} y^{k}] e^{\overline{B} (y) B (x)} \\ = \sum_{j = 0}^{n} [\frac{x^{n}}{n!}] \frac{A (x)^{j}}{j!} [\frac{A (x)^{j}}{j!} y^{k}] e^{\overline{B} (y) B (A (x))} \\ = [\frac{x^{n}}{n!} y^{k}] e^{\overline{B} (y) B (A (x))} \end{aligned}

that is, given that $a (n, k)$ is the number of ways to partition $n$ labelled nodes into a set of $A$ -egf-type structures, and $b (n, k)$ the ways to partition them into a (set of $\overline{B}$ -ogf-type structures of) $k$ $B$ -egf-type structures, $\sum_{j = 0}^{n} a (n, j) b (j, k)$ is the number of ways to put $n$ labelled nodes into any number of labelled $A$ -type structures, put these into $k$ $B$ -type structures, and put these into a set of $\overline{B}$ -type structures.

In particular, $(\binom{n}{k}) = [\frac{x^{n}}{n!} y^{k}] e^{(1 + y) x}$ , so $\sum_{j = k}^{n} [\binom{n}{j}] (\binom{j}{k}) = [\frac{x^{n}}{n!} y^{k}] \frac{1}{(1 - x)^{1 + y}} = \sum_{i = k}^{n} \frac{n!}{i!} [\binom{i}{k}]$ is the number of ways to totally order all but an arbitrary selection of $i$ of $n$ elements, then put those $i$ into a permutation; equivalently, to cyclically order all but $i$ of $n + 1$ elements, which can then be added as an additional member of the set of cycles in $[\binom{i}{k}]$ , making this equal to $[\binom{n + 1}{k + 1}]$ !

see also my page with some more interesting binomial matmuls

Ward's theorem

If one has a combinatorial structure $s$ such that the number of instances of $s$ with $n$ (labelled) nodes is given by $s (n)$ , with e.g.f. $S (x)$ , the number triangle that counts partitions into sets of $s$ s, $a (n, k) = [\frac{x^{n}}{n!} y^{k}] e^{y S (x)}$ , then the inverse binomial transform of the diagonals gives a partition triangle of the same type.

\begin{aligned} \overline{a} (n, n - k) & = Δ^{n} (λ j . a (j, j - k)) (0) \\ = \sum_{j = 0}^{n} (- 1)^{n - j} (\binom{n}{j}) [\frac{x^{j}}{j!}] \frac{S (x)^{j - k}}{(j - k)!} \\ = [x^{0}] \sum_{j = 0}^{n} (- 1)^{n - j} (\binom{n}{j}) j^{\underline{k}} \frac{S (x)^{j - k}}{x^{j}} \\ = (- 1)^{n} [x^{0}] \frac{_{2} F_{1} (\binom{1, - n}{1 - k}; \frac{S (x)}{x})}{(- k)! S (x)^{k}} \\ = (- 1)^{n - k} n^{\underline{k}} [x^{k}]_{1} F_{0} (\binom{k - n}{}; \frac{S (x)}{x}) \\ = n^{\underline{k}} [x^{k}] {(\frac{S (x) - x}{x})}^{n - k} \\ = n^{\underline{k}} [x^{n}] (S (x) - x)^{n - k} \\ = [\frac{x^{n}}{n!}] \frac{(S (x) - x)^{n - k}}{(n - k)!} \end{aligned}

ie. $\overline{a} (n, k) = [\frac{x^{n}}{n!}] \frac{(S (x) - x)^{k}}{k!} = [\frac{x^{n}}{n!} y^{k}] e^{y (S (x) - x)}$ , meaning $\overline{a} (n, k)$ counts the number of ways to partition $n$ nodes into a set of $k$ $\overline{s}$ s, which are identical to $s$ s but have one fewer singleton.

This means ${{\binom{n}{n - k}}} = Δ^{n} (λ j . {\binom{j}{j - k}}) (0)$ and $[[\binom{n}{n - k}]] = Δ^{n} (λ j . [\binom{j}{j - k}]) (0)$ count partitions into singleton-free subsets and cycles (the latter corresponding with permutations without fixed points).

for the second-order Lah numbers, we have $L a h l a h (\binom{n}{k}) = \frac{n!}{k!} (\binom{n - k - 1}{k - 1}) = [\frac{x^{n}}{n!} y^{k}] e^{y \frac{x^{2}}{1 - x}} = n! [y^{k - 1}]_{2} F_{2} (\binom{1 - \frac{n}{2}, \frac{3 - n}{2}}{2, 2 - n}; - 4 y)$

(See ^[6], which gives two citations for its discovery.)

row g.f.s of the opposite kinds

subset row sums (Bell numbers A000110) and o.g.f.s (Bell polynomials)

The $n$ th row sum of the subset numbers is called the Bell number $\sum_{k = 0}^{n} {\binom{n}{k}} = {B e l l}_{n} =$ A000110(n) $= [\frac{x^{n}}{n!}] e^{e^{x} - 1}$ , and the row o.g.f.s are called Bell polynomials, $\sum_{k = 0}^{n} {\binom{n}{k}} y^{k} = [\frac{x^{n}}{n!}] e^{y (e^{x} - 1)} = {B e l l}_{n} (y)$ .

The Bell numbers aren't as simple as one might expect from their counterparts the factorials, and getting an asymptotic characterisation as precise as Stirling's approximation entails saddle point approximation. However, we can do some elementary things!

Taking the average value of $k$ across all sets of sets, $\frac{\sum_{k = 0}^{n} k {\binom{n}{k}} y^{k}}{\sum_{k = 0}^{n} {\binom{n}{k}} y^{k}} = \frac{\sum_{k = 0}^{n} ({\binom{n + 1}{k}} - {\binom{n}{k - 1}}) y^{k}}{\sum_{k = 0}^{n} {\binom{n}{k}} y^{k}}$ , and the upper bound can be changed to $k + 1$ since the $k + 1$ th summand cancels itself out, giving $\frac{{B e l l}_{n + 1} (y)}{{B e l l}_{n} (y)} - y$ .

We also have that $[y^{\underline{k}}] {B e l l}_{n} (y) = \sum_{i = k}^{n} {\binom{n}{i}} [y^{\underline{k}}] y^{i} = \sum_{i = k}^{n} {\binom{n}{i}} {\binom{i}{k}} = [\frac{x^{n}}{n!} y^{k}] e^{y (e^{e^{x} - 1} - 1)}$ (entries A039810=A130191) by the matmul correspondence

Since we know that ${\binom{n}{k}} = [x^{\underline{k}}] x^{n}$ , ie. $k^{{n}} = k! {\binom{n}{k}} = Δ^{k} (λ i . i^{n}) (0)$ , we can use the formula from #binomial transforms for $e g f (λ k . k^{{n}}) (x) = {B e l l}_{n} (x) = e^{- x} e g f (λ i . i^{n}) (x)$ ; this is Dobiński's formula, and its practical use is the other way around; knowing the function by which to multiply $e^{x}$ in the e.g.f. of a polynomial sequence, in terms of said polynomial's expansion.

Dobiński's formula is not to be confused with the fact that ${(\frac{d}{d x})}^{n} e^{f (x)} = \sum_{p \in s e t s (s e t s (n))} \prod_{s \in p} f^{(s)} (x)$ , which is sometimes called the EXP transform but is a case of Faà di Bruno; it can be rewritten ${(\frac{d}{d x})}^{n} e^{f (x)} = {B e l l}_{n} (f^{'} (x), \dots, f^{(n)} (x))$ via the multivariate Bell polynomial (for which each size of subset is 'coloured' in its own variable)

cycle row rising g.f.s

having looked at $[\binom{n}{k}] = [x^{k}] x^{\overline{n}}$ and ${\binom{n}{k}} = [x^{\underline{k}}] x^{n} = [x^{k}] {B e l l}_{n} (x)$ , it makes sense to look at the function $[\binom{n}{k}] = [x^{\overline{k}}] {a n t i B e l l}_{n} (x)$ !

similarly to before, we have $[y^{k}] {a n t i B e l l}_{n} (y) = \sum_{i = k}^{n} [\binom{n}{i}] [y^{k}] y^{\overline{i}} = \sum_{i = k}^{n} [\binom{n}{i}] [\binom{i}{k}] = [\frac{x^{n}}{n!} y^{k}] (e^{y \log (\frac{1}{1 - \log (\frac{1}{1 - x})})} : = \frac{1}{{(1 - \log (\frac{1}{1 - x}))}^{y}})$ (entries |A039814|=|A325872|); this tells us that ${a n t i B e l l}_{n} (y) = [\frac{x^{n}}{n!}] \frac{1}{{(1 - \log (\frac{1}{1 - x}))}^{y}}$ .

By setting $y = 1$ , we likewise get the antiBell numbers, A007840 (enumerating lists of cycles)!

combinatorial interpretations of Pochhammer calculus

this section now moved to /binomial-type theorems

the duality

As explained in ^[4], the duality shown in the o.g.f.s has a direct combinatorial proof in terms of Richard P. Stanley's poset homomorphism duality theorem. In fact, it works for every variety of generating function, importantly also the falling ones; ${\binom{n}{k}} = [y^{\underline{k}}] y^{n}$ becomes $[\binom{n}{k}] = [x^{\underline{- n}} : = \frac{1}{(x + 1)^{\overline{n}}}] \frac{1}{x^{k}}$ ; that is, within the radius of convergence (of $1$ from $x = 0$ ), $\frac{1}{x^{k}} = \sum_{n = k}^{\infty} \frac{[\binom{n}{k}]}{(x + 1)^{\overline{n}}}$ and so we can get the expansion of the $o$ th-order partial sums of the sum of reciprocals of $k$ th powers!

Eulerian numbers ( ${⟨ \binom{n}{k} ⟩}_{1}$ =A008292(n,k)=A123125(n,k), ${⟨ \binom{n}{k} ⟩}_{0}$ =A173018(n,k))

note that pretty often (including in the primary entry) the indexing $E (n, k) = {⟨ \binom{n}{k} ⟩}_{1}$ is used, but ${⟨ \binom{n}{k} ⟩}_{0}$ is Euler's and Knuth's and Foata's and Hirzebruch's and Luschny's (see the latter's page); be careful

Let ${⟨ \binom{n}{k} ⟩}_{0}$ be the number of permutations of $n$ elements in which $k$ of the $n - 1$ pairs of consecutive elements $p_{i}, p_{i + 1}$ have $p_{i} < p_{i + 1}$ (ie. are 'rises'), and ${⟨ \binom{n}{k} ⟩}_{1} = {⟨ \binom{n}{k - 1} ⟩}_{0}$ have $k - 1$ rises.

To establish the recurrence combinatorially, we can surject a permutation into a 'landscape' of rises and falls, then with $k$ rises,

one can place the $n + 1$ th element at the beginning to add a fall, or in an interval that was a rise (the two new intervals that it's split into are a rise and a fall), for $k + 1$ insertions that conserve the rise-count
likewise, since there are $n - 1$ intervals from which the $k$ rises are subtracted for $n - 1 - k$ falls, one can place it at the end or inside a fall to create a new rise in $n - k$ ways

which give us

{⟨ \binom{n + 1}{k} ⟩}_{0} = (k + 1) {⟨ \binom{n}{k} ⟩}_{0} + (n - k + 1) {⟨ \binom{n}{k - 1} ⟩}_{0}

writing ${⟨ \binom{n}{k} ⟩}_{0} = [y^{k}] f_{n} (y)$ (where $f_{n}$ is known as the $n$ th Eulerian polynomial), the recurrence turns into diffeqs

f_{n + 1} (y) = (1 + n y) f_{n} (y) + y (1 - y) {f_{n}}^{'} (y)

which is actually the quotient rule; note that if we define $g (y) = \frac{y}{(1 - y)^{n + 1}} f (y)$ , we get precisely that diffeq-recurrence in the numerators, $g^{'} (y) = \frac{(1 + n y) f (y) + (1 - y) f^{'} (y)}{(1 - y)^{n + 2}}$ so since $f_{0} (y) = 1$ , $g_{n} (y)$ is the $n$ th iterate of the map $λ f . λ y . y g^{'} (y)$ starting at $g_{0} = \frac{y}{1 - y}$ .

In particular, since the operation 'differentiate and then multiply by $y$ ' multiplies the $k$ th term of the series expansion by $k$ without shifting it, we have that $[y^{k}] g_{n} (y) = k^{n}$ for $n \geq 1$ .^{[n 1]}

So, ${⟨ \binom{n}{k} ⟩}_{0} = [y^{k + 1}] (1 - y)^{n + 1} o g f (λ i . i^{n}) = \nabla^{n + 1} (λ i . i^{n}) (k + 1) = \sum_{i = 0}^{n + 1} (\binom{n + 1}{i}) (- 1)^{i} (k + 1 - i)^{n}$ (and ${⟨ \binom{n}{k} ⟩}_{1} = \sum_{i = 0}^{n + 1} (\binom{n + 1}{i}) (- 1)^{i} (k - i)^{n}$ ), and likewise $k^{n} = [y^{k - 1}] \frac{o g f (λ j . {⟨ \binom{n}{j} ⟩}_{0})}{(1 - y)^{n + 1}} = \sum_{j = 0}^{k - 1} {⟨ \binom{n}{j} ⟩}_{0} ((\binom{k - j}{n})) = \sum_{j = n - k}^{n - 1} {⟨ \binom{n}{j} ⟩}_{0} (\binom{k + j}{n})$ (the latter following from ${⟨ \binom{n}{j} ⟩}_{0} = {⟨ \binom{n}{n - 1 - j} ⟩}_{0}$ ).

known as Worpitzky's identity; a bijective proof is given in ^[7], but a more direct one is as follows:

$k^{n}$ is the number of functions from $[n]$ to $[k]$
$\sum_{j = 0}^{k - 1} {⟨ \binom{n}{j} ⟩}_{0} ((\binom{k - j - 1}{n + 1}))$ is the number of pairings $p, q$ , where $p$ are (permutations of $[n]$ with $j$ falls) and $q$ are (placements of $n + 1$ identical markers into $k - j - 1$ intervals)
to biject from the left to right side,

plot the function's output, then connect the nodes in reading order. the order in which the line lands upon them is a permutation of the initial list; let $p$ be the sequence of $x$ positions along the line (here $1, 3, 6, 4, 2, 0, 5$ )
place tally marks along each line segment for each unit change to $y$ position; the $j$ descents each have at least $1$ , the ascents have at least $0$
after placing the $j$ mandatory tallies, the remaining $k - 1 - j$ have $n + 1$ intervals between successive nodes to go into (in stars and bars, |*||*|*|***|**|||); the red nodes are fixed at the minimum and maximum height, so act to shift all or none of the function respectively

We can put the Eulerian numbers inside the monomials in the formula for subset numbers, to get

\begin{aligned} k^{{n}} & = \sum_{i = 0}^{k} (\binom{k}{i}) (- 1)^{k - i} \sum_{j = 0}^{n - 1} (\binom{i + j}{n}) {⟨ \binom{n}{j} ⟩}_{0} \\ = \sum_{j = 0}^{n - 1} {⟨ \binom{n}{j} ⟩}_{0} \sum_{i = n - j}^{k} (\binom{k}{i}) (- 1)^{k - i} (\binom{i + j}{n}) \\ = \sum_{j = 0}^{n - 1} {⟨ \binom{n}{j} ⟩}_{0} (\binom{k}{n - j}) (- 1)^{j + k - n}_{2} F_{1} (\binom{n - k - j, 1 + n}{1 + n - j}; 1) \\ = \sum_{j = 0}^{n - 1} {⟨ \binom{n}{j} ⟩}_{0} (\binom{k}{n - j}) \frac{j^{\underline{j + k - n}}}{(1 + n - j)^{\overline{j + k - n}}} # G a u s s^{'} s h y p e r g e o m e t r i c t h e o r e m a g a i n! \\ = \sum_{j = n - k}^{n - 1} {⟨ \binom{n}{j} ⟩}_{0} (\binom{j}{n - k}) \end{aligned}

other formulations:

in the other convention, it can be written as

\sum_{j = 1}^{k} {⟨ \binom{n}{n - k + j} ⟩}_{1} ((\binom{j}{n - k}))

; by reflection,

\sum_{j = 1}^{k} {⟨ \binom{n}{k - j} ⟩}_{0} ((\binom{j}{n - k}))

and the bijective proof of this (in the manner of stars and bars) is that one can represent each member of $k^{{n}}$ (a list of sets) by sorting the sets in ascending order then concatenating them together, with $|$ s placed at intervals which were formed by concatenations and $,$ s otherwise; count the $n - k \leq j < n$ ascents, then a fall must be a bar but a rise can be either a comma or bar; there are $n - k$ commas, distributed amongst the $j$ ascents in $(\binom{j}{n - k})$ ways.

We can also get this from the fact that subset numbers are the inverse #binomial transforms of monomials; however, unlike the Bell numbers section, we use the o.g.f. rather than e.g.f. relation. $o g f (λ k . k^{{n}}) (x) = \frac{o g f (λ i . i^{n}) (\frac{x}{1 + x})}{1 + x}$ . (Since $o g f (λ i . i^{n}) (x) = \frac{\sum_{k = 0}^{n - 1} ⟨ \binom{n}{k} ⟩ x^{k + 1}}{(1 - x)^{n + 1}}$ , $o g f (λ k . k^{{n}}) (x) = \sum_{j = 0}^{n - 1} ⟨ \binom{n}{j} ⟩ x^{j + 1} (1 + x)^{n - 1 - j} = \sum_{j = 0}^{n - 1} ⟨ \binom{n}{j} ⟩ x^{n - j} (1 + x)^{j}$ )

Eulerians in the hypercube!

taking a set of $n$ uniform random variables in $[0, 1]$ and replacing each variable with its rank (the number of variables smaller than it) produces a uniformly-selected random permutation. This is useful, because it means the chance that a random permutation satisfies some property (ie. a set of inequalities between some of its elements) is equivalent to the measure (hypervolume) in $[0, 1]^{n}$ that satisfies it (see also bitwise permutations for a little application)

the short single-page note ^[8] explains a mapping that bijects the regions of the hypercube with $k$ rises as a permutation, into the region whose sum of coordinates is between $k$ and $k + 1$ (a polytope bounded by hypersimplices; ^[9] explains much more about them)

map

(x_{1}, \dots, x_{n})

into

(y_{1}, \dots, y_{n}) < m a t h > b y < m a t h > y_{i} = (x_{i - 1} - x_{i}) % 1

(where

x_{0} = 0

); each ascent wraps around and adds

1

to the sum, and each

x_{i}

's contribution is cancelled out by being subtracted from

y_{i}

and added to

y_{i + 1}

, except for the last (which allows the image to be in the interval between two hyperplanes, instead of just within one)

as such, laying an $n$ -cube along its $n$ -agonal, then chopping into $n$ slices of length $\frac{1}{\sqrt{n}}$ and melting down the parts produces a row of the Eulerians!

note this was known to Laplace as of 1812 in ^[10]!

calculus of the wrong kinds

from binomial expansions, $Δ x^{n} = \sum_{k = 0}^{n - 1} (\binom{n}{k}) x^{k}$ and $\nabla x^{n} = \sum_{k = 0}^{n - 1} (\binom{n}{k}) (- 1)^{n - 1 - k} x^{k}$ . What about the expansion in Pochhamers of the derivative of a Pochhammer?

via the product rule, it is $\frac{d}{d x} x^{\overline{n}} = \sum_{k = 0}^{n - 1} (x^{\overline{k}} (x + n - 1)^{\underline{n - 1 - k}} = \frac{x^{\overline{n}}}{x + k}) = x^{\overline{n}} (H_{x + n - 1} - H_{x - 1})$

however, it is also elucidating to do gfologically

\begin{aligned} \frac{d}{d x} x^{\overline{n}} & = \sum_{i = 0}^{n} i x^{i - 1} ([x^{i}] x^{\overline{n}} : = [\binom{n}{i}]) \\ = \sum_{i = 0}^{n} [\binom{n}{i}] i \sum_{k = 0}^{i - 1} x^{\overline{k}} ([x^{\overline{k}}] x^{i - 1} : = (- 1)^{i - 1 - k} {\binom{i - 1}{k}}) \\ = \sum_{k = 0}^{n - 1} (- 1)^{k} x^{\overline{k}} \sum_{i = k + 1}^{n} [\binom{n}{i}] i (- 1)^{i - 1} {\binom{i - 1}{k}} \\ = \sum_{k = 0}^{n - 1} (- 1)^{k} x^{\overline{k}} \sum_{i = k + 1}^{n} [\frac{x^{n}}{n!} y^{i}] \frac{1}{(1 - x)^{y}} i [\frac{x^{i - 1}}{(i - 1)!} y^{k}] e^{y (e^{- x} - 1)} \\ = \sum_{k = 0}^{n - 1} (- 1)^{k} x^{\overline{k}} \sum_{i = k + 1}^{n} [\frac{x^{n}}{n!}] \frac{\log {(\frac{1}{1 - x})}^{i}}{i!} [\frac{x^{i}}{i!} y^{k}] x e^{y (e^{- x} - 1)} \\ = \sum_{k = 0}^{n - 1} (- 1)^{k} x^{\overline{k}} [\frac{x^{n}}{n!} y^{k}] \log (\frac{1}{1 - x}) e^{- y x} \\ = \sum_{k = 0}^{n - 1} (- 1)^{k} x^{\overline{k}} [\frac{x^{n}}{n!} y^{k}] \sum_{i = 1}^{\infty} \sum_{j = 0}^{\infty} \frac{x^{i}}{i} \frac{(- x y)^{j}}{j!} \\ = \sum_{k = 0}^{n - 1} \frac{x^{\overline{k}}}{n - k} \frac{n!}{k!} \end{aligned}

Note that this can also be written as $\frac{d}{d x} ((\binom{x}{n})) = \sum_{k = 0}^{n - 1} \frac{((\binom{x}{k}))}{n - k}$

Faulhabernoulli's formula

We can write

\begin{aligned} \sum_{t = 1}^{y} t^{n} = & \sum_{i = 0}^{n} \frac{y^{\overline{i + 1}}}{i + 1} ([y^{\overline{i}}] y^{n} : = (- 1)^{n - i} {\binom{n}{i}}) \\ = & \sum_{i = 0}^{n} (- 1)^{n - i} {\binom{n}{i}} \sum_{k = 1}^{i + 1} y^{k} \frac{([y^{k}] y^{\overline{i + 1}} : = [\binom{i + 1}{k}])}{i + 1} \\ = & \sum_{k = 1}^{n + 1} y^{k} \sum_{i = k - 1}^{n} (- 1)^{n - i} {\binom{n}{i}} \frac{[\binom{i + 1}{k}]}{i + 1} \\ = & \sum_{k = 1}^{n + 1} y^{k} \sum_{i = k - 1}^{n} [\frac{x^{n}}{n!} y^{i}] e^{y (1 - e^{- x})} [\frac{x^{i + 1}}{i!} y^{k}] \frac{1}{(1 - x)^{y}} \\ = & \sum_{k = 1}^{n + 1} y^{k} \sum_{i = k - 1}^{n} [\frac{x^{n}}{n!}] \frac{(1 - e^{- x})^{i}}{i!} [\frac{x^{i}}{i!} y^{k}] \frac{1}{x (1 - x)^{y}} - \frac{1}{x} \\ = & \sum_{k = 1}^{n + 1} y^{k} [\frac{x^{n}}{n!} y^{k}] \frac{1}{(1 - e^{- x}) (1 - (1 - e^{- x}))^{y}} - \frac{1}{1 - e^{- x}} \\ = & \sum_{k = 1}^{n + 1} y^{k} [\frac{x^{n}}{n!} y^{k}] \frac{e^{x y} - 1}{1 - e^{- x}} \\ = & [\frac{x^{n}}{n!}] \frac{e^{x y} - 1}{1 - e^{- x}} \end{aligned}

if we define the 'ordinaryised' Bernoulli numbers ${\overline{B}}_{n}^{+} = [x^{n}] \frac{x}{1 - e^{- x}}$ ( $\frac{1}{n!}$ th of the standard definition $B_{n}^{+}$ as the e.g.f. expansion), then since $e^{x y} - 1 = \sum_{j = 1}^{\infty} \frac{(x y)^{j}}{j!}$ , $\frac{e^{x y} - 1}{1 - e^{- x}} = \sum_{i = 0}^{\infty} \sum_{j = 1}^{\infty} {\overline{B}}_{i}^{+} x^{i - 1 + j} \frac{y^{j}}{j!}$ , so $[\frac{x^{n}}{n!} y^{k}] \frac{e^{x y} - 1}{1 - e^{- x}} = {\overline{B}}_{n + 1 - k}^{+} \frac{n!}{k!}$ .

Plugging this in, we obtain the very elegant $\sum_{t = 1}^{y} \frac{t^{n}}{n!} = \sum_{k = 1}^{n + 1} {\overline{B}}_{n + 1 - k}^{+} \frac{y^{k}}{k!}$ ; that is, the 2D array of coefficients is just a 1D sequence in the first column with elements extruded into diagonals.

Gregory's dual thereto

going the other way around, we have the analogue,

\begin{aligned} \int_{t = 0}^{y} t^{\overline{n}} & = \sum_{i = 0}^{n} \frac{y^{i + 1}}{i + 1} ([y^{i}] y^{\overline{n}} : = [\binom{n}{i}]) \\ = \sum_{i = 0}^{n} [\binom{n}{i}] \frac{1}{i + 1} \sum_{k = 1}^{i + 1} y^{\overline{k}} ([y^{\overline{k}}] y^{i + 1} : = (- 1)^{i + 1 - k} {\binom{i + 1}{k}}) \\ = \sum_{k = 1}^{n + 1} y^{\overline{k}} \sum_{i = k - 1}^{n} [\binom{n}{i}] \frac{(- 1)^{i + 1 - k}}{i + 1} {\binom{i + 1}{k}} \\ = \sum_{k = 1}^{n + 1} y^{\overline{k}} \sum_{i = k - 1}^{n} [\frac{x^{n}}{n!} y^{i}] \frac{1}{(1 - x)^{y}} \frac{1}{i + 1} [\frac{x^{i + 1}}{(i + 1)!} y^{k}] e^{y (1 - e^{- x})} \\ = \sum_{k = 1}^{n + 1} y^{\overline{k}} \sum_{i = k - 1}^{n} [\frac{x^{n}}{n!}] \frac{\log {(\frac{1}{1 - x})}^{i}}{i!} [\frac{x^{i}}{i!} y^{k}] \frac{e^{y (1 - e^{- x})} - 1}{x} \\ = \sum_{k = 1}^{n + 1} y^{\overline{k}} [\frac{x^{n}}{n!} y^{k}] \frac{e^{y x} - 1}{\log (\frac{1}{1 - x})} \end{aligned}

again, we must define a sequence for the expansion this unpleasant reciprocal of a pleasant e.g.f.; we define ${\overline{G}}_{n} = [x^{n}] \frac{x}{\log (\frac{1}{1 - x})}$ (whereas usually $G_{n} = [x^{n}] \frac{x}{\log (1 + x)}$ , so ${\overline{G}}_{n} = (- 1)^{n} G_{n}$ ; the $G_{n}$ alternate in sign (every even term after the $0$ th is negative), but the ${\overline{G}}_{n}$ are all negative after the $0$ th). Then, as before,

\frac{e^{y x} - 1}{\log (\frac{1}{1 - x})} = \sum_{i = 0}^{\infty} \sum_{j = 1}^{\infty} {\overline{G}}_{i + 1} x^{i + j} \frac{y^{j}}{j!}

so we have $\int_{t = 0}^{y} t^{\overline{n}} = \sum_{k = 0}^{n + 1} {\overline{G}}_{n - k + 1} \frac{n!}{k!} y^{\overline{k}}$ , ie. $\int_{t = 0}^{y} ((\binom{t}{n})) = \sum_{k = 0}^{n + 1} {\overline{G}}_{n - k + 1} ((\binom{y}{k}))$ , or $\int_{t = 0}^{y} (\binom{t}{n}) = \sum_{k = 0}^{n + 1} G_{n - k + 1} (\binom{y}{k})$

We can represent this as a single coefficient extraction from a bivariate, just like the monomial summation. Knowing $[\frac{x^{n}}{n!} y^{k}] \frac{e^{y x} - 1}{\log (\frac{1}{1 - x})} = [\frac{x^{n}}{n!} y^{\overline{k}}] f (x, y)$ , we have that

\begin{aligned} [\frac{x^{n}}{n!} y^{k}] f (x, y) & = \sum_{i = 0}^{k} [\frac{x^{n}}{n!} y^{i}] \frac{e^{y x} - 1}{\log (\frac{1}{1 - x})} ([y^{k}] y^{\overline{i}} : = [\binom{i}{k}]) \\ = \sum_{i = 1}^{k} [\frac{x^{n}}{n!}] \frac{1}{\log (\frac{1}{1 - x})} \frac{x^{i}}{i!} [\frac{x^{i}}{i!} y^{k}] \frac{1}{(1 - x)^{y}} \\ = [\frac{x^{n}}{n!} y^{k}] \frac{(1 - x)^{- y} - 1}{\log (\frac{1}{1 - x})} \end{aligned}

so, $\int_{t = 0}^{y} t^{\overline{n}} = [\frac{x^{n}}{n!}] \frac{(1 - x)^{- y} - 1}{\log (\frac{1}{1 - x})}$

asymptotics and properties as statistical distributions

For the cycle numbers, the existence of $o g f (λ k . [\binom{n}{k}]) = x^{\overline{n}}$ helps us,

\frac{\sum_{p \in p e r m s (n)} c y c l e s (p)}{# (p e r m s (n))} = \frac{\sum_{k = 0}^{n} k [\binom{n}{k}] y^{k}}{\sum_{k = 0}^{n} [\binom{n}{k}] y^{k}} = \frac{\frac{d}{d y} y^{\overline{n}}}{y^{\overline{n}}} = \frac{d}{d y} \log (\frac{(y + n - 1)!}{(y - 1)!}) = H_{y + n - 1} - H_{y - 1}

so at $y = 1$ , the centre of mass of the distribution is $H_{n}$ ! meanwhile, the variance, $\underset{p \in p e r m s (n)}{e x p e c t} (c y c l e s (p) - H_{n})^{2}$ ; in general,

\frac{\sum_{k = 0}^{n} ((k^{2} : = k^{\underline{2}} + k^{\underline{1}}) - 2 k H_{n} + H_{n}^{2}) [y^{k}] f (y)}{n!} = (\frac{f^{″} (1)}{f (1)} + \frac{f^{'} (1)}{f (1)}) - 2 \frac{f^{'} (1)}{f (1)} H_{n} + H_{n}^{2} = \frac{f^{″} (1) : = y^{\overline{n}} ((H_{y + n - 1} - H_{y - 1})^{2} - (H_{n + y - 1}^{(2)} - H_{y - 1}^{(2)})) |_{y = 1}}{n!} + H_{n} - H_{n}^{2} = H_{n}^{2} - H_{n}^{(2)} + H_{n} - H_{n}^{2} = H_{n} - H_{n}^{(2)}

meaning that (since $H_{n}^{(2)} \sim \frac{π^{2}}{6}$ ) both the expectation and variance of the cycle count of a length- $n$ permutation are asymptotic to $\log (n)$ . ^[11] proves that the distribution is asymptotically normal, so (asymptotically, up to Puiseux refinement) completely characterised by these, since higher-order moments can be neglected.

Applying the saddle point method (from ^[1]), we can still get asymptotics,

$g (x) = x y e^{x}, g^{'} (x) = (x + 1) y e^{x}$
$x_{n} = W_{0} (\frac{n}{y}) \sim \log (\frac{n}{y})$ (Lambert W function)
$f (x_{n}) = e^{\frac{n}{W_{0} (\frac{n}{y})} - y}$
$g^{'} (x_{n}) = n + y e^{W_{0} (\frac{n}{y})} = n (1 + \frac{1}{W_{0} (\frac{n}{y})}) \sim n$
$x_{n}^{n + \frac{1}{2}} = e^{(n + \frac{1}{2}) \log (W_{0} (\frac{n}{y}))} = e^{(n + \frac{1}{2}) (\log (\frac{n}{y}) - W_{0} (\frac{n}{y}))} = \frac{{(\frac{n}{y})}^{n + \frac{1}{2}}}{e^{(n + \frac{1}{2}) W_{0} (\frac{n}{y})}} \sim \frac{n!}{\sqrt{2 π e}} {(\frac{e^{1 - W_{0} (\frac{n}{y})}}{y})}^{n + \frac{1}{2}}$

so an asymptotic on the $n$ th Bell polynomial is

{B e l l}_{n} (y) = [\frac{x^{n}}{n!}] e^{y (e^{x} - 1)} = n! \frac{f (x_{n})}{\sqrt{2 π g^{'} (x_{n})} x_{n}^{n + \frac{1}{2}}} \sim \frac{e^{\frac{n}{W_{0} (\frac{n}{y})} - y + \frac{1}{2}} {(y e^{W_{0} (\frac{n}{y}) - 1})}^{n + \frac{1}{2}}}{\sqrt{n (1 + \frac{1}{W_{0} (\frac{n}{y})})}} \sim \frac{e^{\frac{n}{W_{0} (\frac{n}{y})} - y - n} {(\frac{n}{W_{0} (\frac{n}{y})})}^{n + \frac{1}{2}}}{\sqrt{n}} \sim \frac{e^{\frac{n}{W_{0} (\frac{n}{y})} - y - n} n^{n}}{W_{0} {(\frac{n}{y})}^{n + \frac{1}{2}}}

whose logarithm is

\frac{n}{W (\frac{n}{y})} - (n + \frac{1}{2}) (\log (\frac{n}{y}) - W (\frac{n}{y})) + n (\log (n) - 1) - y

, and logarithmic derivative

\frac{n}{y W (\frac{n}{y})} + \frac{1}{2 y (W (\frac{n}{y}) + 1)} - 1

(though reintroducing the removed

\sqrt{1 + \frac{1}{W_{0} (\frac{n}{y})}}

denominator part gives

\frac{n}{y W (\frac{n}{y})} + \frac{W (\frac{n}{y})}{2 y {(W (\frac{n}{y}) + 1)}^{2}} - 1

),

giving us the final result that the centre of mass of the $n$ th row is $\underset{P \in s e t s (s e t s (n))}{e x p e c t} (| P |) \sim \frac{n}{W (n)} + \frac{1}{2 (W (n) + 1)} - 1$ (although the refinement, $\frac{n}{W (n)} + \frac{W (n)}{2 (W (n) + 1)^{2}} - 1$ , changes the ratio of the estimates for the 192nd term (877 bits long) from 1.000423 times overapproximation to 1.00000734 under-; <1/57th the error!)

Since we know (from the section on them) that this logarithmic derivative equals $\frac{{B e l l}_{n + 1} (y)}{{B e l l}_{n} (y)} - y$ , this can be slightly more nicely expressed as $\frac{{B e l l}_{n + 1}}{{B e l l}_{n}} \sim \frac{n}{W (n)} + \frac{W (n)}{2 (W (n) + 1)^{2}}$ .

Likewise, knowing the variance equals $(\frac{f^{″} (1)}{f (1)} : = \frac{f^{″} (1)}{f^{'} (1)} \frac{f^{'} (1)}{f (1)}) + \frac{f^{'} (1)}{f (1)} - {(\frac{f^{'} (1)}{f (1)})}^{2}$ (where $f = {B e l l}_{n}$ ). Resolving $\frac{f^{″} (1)}{f^{'} (1)} = \frac{n}{W} + \frac{3 W - 2}{2 (W + 1)^{2}} + 2 (\frac{2 n - W^{3} - W^{2} - 2 W}{2 n (W + 1)^{2} - W (2 W^{2} + 3 W + 2)} - 1)$ , we get $\underset{P \in s e t s (s e t s (n))}{v a r} (| P |) = \frac{({B e l l}_{n + 1} - {B e l l}_{n}) ({B e l l}_{n} ({B e l l}_{n + 1} + {B e l l}_{n + 2}) - {B e l l}_{n + 1}^{2})}{{B e l l}_{n}^{2} {B e l l}_{n + 1}} \sim \frac{n}{W (n) (W (n) + 1)} - 1 + \frac{1}{2 (W (n) + 1)^{2}} - \frac{3}{2 (W (n) + 1)^{3}} + \frac{1}{(W (n) + 1)^{4}}$

^[12] gives an analogous result to the first kind; asymptotically, these first two moments describe the normal distributions they converge to.

row log-concavity inequalities

the cycle row o.g.f.s (rising powers) have roots lie in an arithmetic progression over the nonpositive reals, and ^[12]'s lemma 1 shows that the subset row o.g.f.s' (Touchard polynomials') roots are also real; theorem 2 of ^[13] is that this property makes them at least as log-concave as the binomial coefficients, ie. $\frac{{[\binom{n}{k}]}^{2}}{[\binom{n}{k - 1}] [\binom{n}{k + 1}]} \geq \frac{{(\binom{n - 1}{k - 1})}^{2}}{(\binom{n - 1}{k - 2}) (\binom{n - 1}{k})} = (1 + \frac{1}{k - 1}) (1 + \frac{1}{n - k})$ (and it seems the excess ratio is monotonically decreasing; $\frac{\frac{{[\binom{n}{n - 1}]}^{2}}{[\binom{n}{n - 2}] [\binom{n}{n}]}}{\frac{{(\binom{n}{n - 1})}^{2}}{(\binom{n}{n - 2}) (\binom{n}{n})}} = \frac{2 \frac{n (n - 1)}{(n - 2) (n - \frac{1}{3})}}{2 \frac{n - 1}{n - 2}} = 1 + \frac{1}{3 n - 1}$ , which is a lower bound when varying $k$ )

^[14] compiles a lot of nice results; theorem (3.2) is that since $\frac{{\binom{n}{k + 1}}}{{\binom{n}{k}}} \geq \frac{2 (n - k)}{k (k + 1)}$ , for subsets we have the slightly stronger $\frac{{\binom{n}{k}}^{2}}{{\binom{n}{k - 1}} {\binom{n}{k + 1}}} > \frac{(k + 1) (n - k + 1)}{(k - 1) (n - k)} = (1 + \frac{2}{k - 1}) (1 + \frac{1}{n - k})$ , with excess error ratio $\frac{\frac{{\binom{n}{k}}^{2}}{{\binom{n}{k - 1}} {\binom{n}{k + 1}}}}{2 (1 + \frac{2}{n - 2})} = 1 + \frac{2}{3 n - 5}$ on the right end (to which it also seemingly decreases monotonically)

For the Lah numbers, this section of my page on A058349 provides some more general results about asymptotics for their o.g.f.s (and modifications covering all confluent hypergeometrics with respect to a single numerator Pochhammer).

asymptotics along rays

a (non-Hayman) saddle point method can be used slightly more directly; write $k = c n$ , then

\begin{aligned} (c n)^{{n}} = [\frac{x^{n}}{n!}] (e^{x} - 1)^{k} & = \frac{n!}{τ i} \int_{γ} \frac{(e^{x} - 1)^{c n}}{x^{n + 1}} d x \\ \sim \frac{n!}{τ i} \int_{γ} \frac{(e^{x} - 1)^{c n}}{x^{n + 1}} d x \\ = \frac{n!}{τ i} \int_{γ} \frac{(e^{x} - 1)^{c n}}{x^{n + 1}} d x # c h o o s e r s o e^{r} = \frac{1}{1 - r c}; r = W_{0} (- \frac{1}{c \sqrt[c]{e}}) + \frac{1}{c} \\ = \frac{n!}{τ i r^{n + 1}} \int_{0}^{τ} \frac{(e^{r e^{i θ}} - 1)^{c n}}{e^{i θ (n + 1)}} (\frac{d x}{d θ} = r i e^{i θ}) d (θ = \frac{\log (sgn (x))}{i}) \\ = \frac{n!}{τ r^{n}} \int_{0}^{τ} \frac{(e^{r e^{i θ}} - 1)^{c n}}{e^{i θ n}} d θ \\ = \frac{n!}{τ r^{n}} \int_{0}^{τ} \exp (ϕ (x : = e^{i θ}) : = n (c \log (e^{r x} - 1) - \log (x) + \log (r))) d θ # c o n s i d e r i n g r t o b e i n d e p e n d e n t f r o m x \\ = \frac{n!}{τ r^{n}} \int_{- ε}^{ε} \exp (ϕ (x : = e^{i θ}) : = n (c \log (e^{r x} - 1) - \log (x))) d θ # m a t c h f u n c t i o n a t r e a l l i n e \end{aligned}

so $ϕ^{″} (x) = \frac{1}{x^{2}} - \frac{c e^{x}}{(e^{x} - 1)^{2}}$ , $ϕ (x) \sim ϕ (r) - ϕ^{″} (r) \frac{θ^{2}}{2}$ and

\begin{aligned} (c n)^{{n}} & \sim \frac{n!}{τ r^{n}} \int_{- \infty}^{\infty} \exp (ϕ (x) \sim n (c \log (\frac{e^{r} - 1}{r}) - (\frac{1}{r^{2}} - \frac{c e^{r}}{(e^{r} - 1)^{2}}) \frac{θ^{2}}{2})) d θ \\ = \frac{n! (e^{r} - 1)^{c n}}{τ r^{n + 1}} \sqrt{\frac{τ}{n (\frac{1}{r^{2}} - \frac{c e^{r}}{(e^{r} - 1)^{2}})}} \\ = \frac{n! (e^{r} - 1)^{c n}}{r^{n + 1}} \sqrt{\frac{1}{τ n (\frac{1}{r^{2}} - \frac{c e^{r}}{(\frac{1}{1 - r c} - 1)^{2}})}} \\ \sim (n e^{c r - 1} r^{c - 1} c^{c})^{n} \sqrt{\frac{c}{c (r + 1) - 1}} \end{aligned}

this allows you to asymptoterate ${\binom{n}{c n}}$ by dividing by $(c n)!$ , then (as realised by ^[15]) setting $c > 1$ and using $[\binom{n}{k}] = {\binom{- k}{- n}}$ lets you asymptoterate the cycle numbers!

transforms

the factorial integral

The classical integral for the factorial, $x! = \int_{t = 0}^{\infty} \frac{t^{x}}{e^{t}} d t$ , implies the useful properties of the two transforms we will be using. As the area under a graph, it can be stretched $n$ times, $n x! = \int_{t = 0}^{\infty} \frac{{(\frac{t}{n})}^{x}}{e^{\frac{t}{n}}} d t$ . By reassigning $n : = \frac{1}{n}$ , $\frac{x!}{n^{x + 1}} = \int_{t = 0}^{\infty} \frac{t^{x}}{e^{n t}} d t$ .

the Mellin transform is $ℳ {f} (x) = \int_{t = 0}^{\infty} f (t) t^{x - 1} d t$ , so this is rewritable as $\frac{ℳ {λ t . e^{- n t}} (x)}{(x - 1)!} = \frac{1}{n^{x}}$ . By summing, $\frac{ℳ {λ t . \sum_{n = 1}^{\infty} e^{- n t} = \frac{1}{e^{t} - 1}} (x)}{(x - 1)!} = \sum_{n = 1}^{\infty} \frac{1}{n^{x}} = ζ (x)$
$x! n^{x + 1} = \int_{t = 0}^{\infty} \frac{t^{x}}{e^{t / n}} d t$ ; by swapping $x$ and $n$ around, $n! x^{n} = \frac{\int_{t = 0}^{\infty} \frac{t^{n}}{e^{t / x}} d t}{x}$ . The Laplace transform is $ℒ {f} (x) = \int_{t = 0}^{\infty} f (t) e^{- x t} d t$ so we can write $\frac{ℒ {λ t . \frac{t^{n}}{n!}} (\frac{1}{x})}{x} = x^{n}$

e.g.f.s to o.g.f.s (Laplace)

as per above, we can define $\overline{ℒ} {f} (x) = \frac{ℒ {f} (\frac{1}{x})}{x}$ so that $\overline{ℒ} {f} (x) = o g f ({e g f}^{- 1} (f)) (x)$ . (This is most of why the Laplace transform is so useful for differential equations; $\overline{ℒ} {λ t . {(\frac{d}{d t})}^{n} f (t)} (x) = {t r u n c}^{n} \overline{ℒ} {f} (x)$ , where the $t r u n c$ operator does truncating division, $t r u n c f (x) = \frac{f (x) - f (0)}{x}$ ; through this, ordinary differential equations with constant coefficients (that define e.g.f.s of linear-recurrent sequences) become arithmetic equations (that define rational o.g.f.s); it can be applied to solve differential equations that define the g.f.s of a variety of D-finite recurrences also)

o.g.f.s to r.g.f.s (Mellin)

$\int_{t = 0}^{\infty} f (t) \frac{t^{x}}{e^{t}} d t = \sum_{n = 0}^{\infty} [t^{n}] f (t) \int_{t = 0}^{\infty} \frac{t^{x + n}}{e^{t}} d t = \sum_{n = 0}^{\infty} (x + n)! [t^{n}] f (t)$ . As such, $\frac{\int_{t = 0}^{\infty} f (t) \frac{t^{x - 1}}{e^{t}} d t}{(x - 1)!} = \sum_{n = 0}^{\infty} x^{\overline{n}} [t^{n}] f (t) = r g f ({o g f}^{- 1} (f)) (x)$ . (This is a variant of the Mellin transform, which we will denote as $\overline{ℳ} {f} (x) = \frac{ℳ {λ t . \frac{f (t)}{e^{t}}} (x)}{(x - 1)!}$ )

via this, the previous transform for the zeta function can be rewritten as $\overline{ℳ} {λ t . \frac{1}{1 - e^{- t}}} = ζ$

As another example, ${a n t i B e l l}_{n} (x) = \frac{\int_{t = 0}^{\infty} t^{\overline{n}} \frac{t^{x - 1}}{e^{t}} d t}{(x - 1)!} = \frac{\int_{t = 0}^{\infty} \int_{r = 0}^{\infty} \frac{r^{n + t - 1} t^{x - 1}}{e^{r + t}} d r \frac{d t}{(t - 1)!}}{(x - 1)!}$ and in particular ${a n t i B e l l}_{n} = \int_{t = 0}^{\infty} \frac{t^{\overline{n}}}{e^{t}} d t$

convergence

for a function that is $O (x^{α})$ as $x \to 0$ and $O (x^{β})$ as $x \to \infty$ , the Mellin transform $ℳ {f} (x) = \int_{t = 0}^{\infty} f (t) t^{x - 1} d t$ converges for $- α < ℜ x < - β$

o.g.f.s to f.g.f.s

Since $x^{\underline{n}} = (- 1)^{n} (- x)^{\overline{n}}$ , $f g f (f) (x) = r g f (λ n . (- 1)^{n} f (n)) (- x)$

to recap on sequence transforms,

we can make a whole table of all the different variations of the binomial transform and their g.f.wise interpretations!

$t$ 's name	binomial	multichoose	binomial	multichoose
$\begin{aligned} t {a} (n) \\ o g f (t {a}) (x) \\ e g f (t {a}) (x) \end{aligned}$	$\begin{aligned} \sum_{k = 0}^{n} (\binom{n}{k}) a (k) \\ \frac{f (\frac{x}{1 - x})}{1 - x} \\ e^{x} f (x) \end{aligned}$	$\begin{aligned} \sum_{k = 0}^{\infty} ((\binom{n}{k})) a (k) \\ \frac{x}{1 - x} f (\frac{1}{1 - x}) \\ ⋮ \end{aligned}$	$\begin{aligned} \sum_{k = n}^{\infty} (\binom{k}{n}) a (k) \\ f (x + 1) \\ ⋮ \end{aligned}$	$\begin{aligned} \sum_{k = 0}^{\infty} ((\binom{k}{n})) a (k) \\ f (\frac{1}{1 - x}) \\ ⋮ \end{aligned}$
$\begin{aligned} t^{- 1} {b} (n) \\ o g f (t^{- 1} {b}) (x) \\ e g f (t^{- 1} {b}) (x) \end{aligned}$	$\begin{aligned} \sum_{k = 0}^{n} (- 1)^{n - k} (\binom{n}{k}) b (k) \\ \frac{f (\frac{x}{1 + x})}{1 + x} \\ e^{- x} f (x) \end{aligned}$ ^{[t 1]}	$\begin{aligned} - \sum_{k = 0}^{n} (\binom{n}{k}) [x^{k}] f (1 + x) \\ \frac{f (1 - \frac{1}{x})}{x - 1} \\ ⋮ \end{aligned}$ ^{[t 2]}	$\begin{aligned} \sum_{k = n}^{\infty} (- 1)^{k - n} (\binom{k}{n}) a (k) \\ f (x - 1) \\ ⋮ \end{aligned}$	$\begin{aligned} ⋮ \\ f (1 - \frac{1}{x}) \\ ⋮ \end{aligned}$

and since we now know how to turn monomials into Pochhammers (and how to expand Pochhammers in monomials), likewise for the Stirling numbers!

$t$ 's name	subset (conventionally "Stirling")	cycle	subset	cycle
$\begin{aligned} t {a} (n) \\ o g f (t {a}) (x) \\ e g f (t {a}) (x) \end{aligned}$	$\begin{aligned} \sum_{k = 0}^{n} {\binom{n}{k}} a (k) \\ ⋮ \\ f (e^{x} - 1) \end{aligned}$	$\begin{aligned} \sum_{k = 0}^{n} [\binom{n}{k}] a (k) \\ ⋮ \\ f (\log (\frac{1}{1 - x})) \end{aligned}$	$\begin{aligned} \sum_{k = n}^{\infty} {\binom{k}{n}} a (k) \\ g f {{f g f}^{- 1} {f}} (x) = \overset{- 1}{\overline{ℳ}} {λ x . f (- x)} (- x) \\ ⋮ \end{aligned}$	$\begin{aligned} \sum_{k = n}^{\infty} [\binom{k}{n}] a (k) \\ r g f {{g f}^{- 1} {f}} (x) = \overline{ℳ} {f} (x) \\ ⋮ \end{aligned}$
$\begin{aligned} t^{- 1} {b} (n) \\ o g f (t^{- 1} {b}) (x) \\ e g f (t^{- 1} {b}) (x) \end{aligned}$	$\begin{aligned} \sum_{k = 0}^{n} (- 1)^{n - k} [\binom{n}{k}] b (k) \\ ⋮ \\ f (\log (1 + x)) \end{aligned}$	$\begin{aligned} \sum_{k = 0}^{n} (- 1)^{n - k} {\binom{n}{k}} b (k) \\ ⋮ \\ f (1 - e^{- x}) \end{aligned}$	$\begin{aligned} \sum_{k = n}^{\infty} (- 1)^{k - n} [\binom{k}{n}] a (k) \\ f g f {{g f}^{- 1} {f}} (x) = \overline{ℳ} {λ x . f (- x)} (- x) \\ ⋮ \end{aligned}$	$\begin{aligned} \sum_{k = n}^{\infty} (- 1)^{k - n} {\binom{k}{n}} a (k) \\ g f {{r g f}^{- 1} {f}} (x) = \overset{- 1}{\overline{ℳ}} {f} (x) \\ ⋮ \end{aligned}$

we can use this to obtain combinatorial identities, by finding closed forms for the expansion of a function as both an o.g.f. and (either kind of) Pochhammer g.f.! for example,

we know that ${\binom{n}{k}} = [x^{\underline{k}}] x^{n}$ , so ${\binom{n + 1}{k + 1}} = [x^{\underline{k + 1}}] x^{n + 1} = [(x + 1)^{\underline{k + 1}}] (1 + x)^{n + 1} = [x^{\underline{k}}] (1 + x)^{n}$ ! (the last step being to divide both the $[]$ 's reference frame's inside and outside by $1 + x$ ) As such, we have the two simultaneous interpretations $(1 + x)^{n} = o g f {λ k . (\binom{n}{k})} = f g f {λ k . {\binom{n + 1}{k + 1}}}$ , which translates to a pair of dual identities

{\binom{n + 1}{k + 1}} = \sum_{i = k}^{n} {\binom{i}{k}} (\binom{n}{i})

(\binom{n}{k}) = \sum_{i = k}^{n} (- 1)^{i - k} [\binom{i}{k}] {\binom{n + 1}{i + 1}}

likewise, $[\binom{n}{k}] = [x^{k}] x^{\overline{n}}$ , so $[\binom{n + 1}{k + 1}] = [x^{k + 1}] x^{\overline{n + 1}} = [x^{k}] (x + 1)^{\overline{n}}$ ; meanwhile, since $L a h (\binom{n}{k}) = [x^{\underline{k}}] x^{\overline{n}}$ , we can apply $Δ$ to both sides of a coeff-extraction $[x^{\underline{k}}] (x + 1)^{\overline{n}} = [Δ x^{\underline{k}}] Δ (x + 1)^{\overline{n}} = [k x^{\underline{k - 1}}] n x^{\overline{n - 1}} = \frac{n}{k} L a h (\binom{n}{k}) = \frac{n!}{k!} (\binom{n}{k})$ , which translates to

\frac{n!}{k!} (\binom{n}{k}) = \sum_{i = k}^{n} {\binom{i}{k}} [\binom{n + 1}{i + 1}]

[\binom{n + 1}{k + 1}] = \sum_{i = k}^{n} (- 1)^{i - k} [\binom{i}{k}] \frac{n!}{i!} (\binom{n}{i})

meanwhile, $(- 1)^{n - k} (\binom{n}{k}) = [x^{k}] (x - 1)^{n}$ but $[x^{\underline{k}}] (x - 1)^{n} = [x^{\underline{k - 1}}] \frac{x^{n} - (- 1)^{n}}{x + 1} = \sum_{j = k}^{n} (- 1)^{n - j} {\binom{j - 1}{k - 1}}$ (which equals $(- 1)^{n - k} [x^{\overline{k}}] (1 + x)^{n}$ by the connection identity), so

\sum_{j = k}^{n} (- 1)^{n - j} {\binom{j - 1}{k - 1}} = \sum_{i = k}^{n} {\binom{i}{k}} (- 1)^{n - i} (\binom{n}{i})

(=A105794(n,k))

(\binom{n}{k}) = \sum_{k \leq i \leq j \leq n} (- 1)^{j - i} [\binom{i}{k}] {\binom{j - 1}{i - 1}}

notes

↑ we can also write the coefficient as $(- 1)^{n - k} (\binom{n}{k}) = (\binom{\sim k}{\sim n})$
↑ where $[x^{n}] f (1 + x) = \sum_{k = n}^{\infty} k^{\underline{n}} a (k)$ ; so we can rewrite it $- \sum_{i = 0}^{\infty} b (i) \sum_{k = 0}^{n} (\binom{n}{k}) i^{\underline{k}}$ , where the inner sum can be rewritten $[\frac{x^{i}}{i!}] e^{x} (1 + x)^{n} =_{2} F_{0} (\binom{- n, - i}{}; 1) = i^{\underline{n}}_{1} F_{1} (\binom{- n}{i - n + 1}; - 1) \sim i^{n}$ .
the reason for the leading minus sign, informally, is that the sequence $b (n) = c^{n}$ requires $c < 1$ (though in general does not prohibit $\lim_{n \to \infty} \frac{a (n)}{a (n - 1)} = 1$ ) and multichoose-transforms forwards into $b (n) = {\frac{1}{1 - c}}^{n}$ , and exponentially-growing infinite sums resolve to negative values by analytic continuation, so the sign flips it back around

o.g.f.s to mixed kind (Lapllin transform)

putting these together, we can define an operator that performs both transforms in different variables; let $a (n) = [x^{n}] f (x)$ , then

ℒ ℳ {f} (x, y) = \frac{\int_{0}^{\infty} \frac{t^{y - 1}}{e^{t / x}} f (t) d t}{(y - 1)! x^{y}} = \sum_{n = 0}^{\infty} a (n) x^{n} y^{\overline{n}}

Ramanujan's master theorem

Note that $(- 1)^{n} m g f (φ) (- n) = \sum_{k = 0}^{n} (- 1)^{n - k} \frac{φ (k)}{k!} n^{\underline{k}} = Δ^{n} (φ) (0)$ , which can be rewritten $(- 1)^{n} m g f ({e g f}^{- 1} (f)) (- n) = [(\binom{y}{n})] f^{(y)} (0) = [\frac{x^{n}}{n!}] e^{- x} f (x)$ ; note that $m g f ({e g f}^{- 1} (f))$ equals $r g f ({o g f}^{- 1} (f))$ , the thing we have a Mellin transform for! Writing the integral, $(- 1)^{n} \overline{ℳ} {f} (- n) = (- 1)^{n} \frac{\int_{t = 0}^{\infty} f (t) \frac{t^{\sim n}}{e^{t}} d t}{(\sim n)!} = [\frac{x^{n}}{n!}] e^{- x} f (x)$ . Defining $g (x) = e^{- x} f (x)$ , $\frac{ℳ {λ t . g (- t)} (- n)}{(\sim n)!} = [\frac{x^{n}}{n!}] g (x)$ (and via Euler's reflection formula, $\frac{- \sin (π n)}{π} ℳ {λ t . g (- t)} (- n) = [x^{n}] g (x)$ ).

This is Ramanujan's master theorem.

note that the Euler's-reflection-formula'd version is a deformation of Cauchy's formula $[x^{n}] f (x) = \frac{\oint_{γ} \frac{f (t)}{t^{n + 1}} d t}{2 π i}$ into an infinitesimal-width contour to infinity around the negative reals!

\begin{aligned} [\frac{x^{n}}{n!}] f (x) & = \frac{\int_{0}^{\infty} \frac{f (- t)}{t^{n + 1}} d t}{(\sim n)!} \\ [x^{n}] f (x) & = \frac{\int_{0}^{\infty} \frac{f (- t)}{t^{n + 1}} d t}{- π \csc (π n)} = \lim_{c \to 0} \frac{(\int_{0}^{- \infty} \frac{f (t)}{(t + c i)^{n + 1}} d t) + (\int_{- \infty}^{0} \frac{f (t)}{(t - c i)^{n + 1}} d t)}{2 π i} \end{aligned}

(we use the negative reals rather than the positive, to use the branch cut we've induced along them)

note that having proven the first case combinatorially and second case analytically, their simultaneous truth is logically equivalent to the statement of Euler's reflection identity, giving an accidental proof of that as well!

Some special cases of its use:

the factorial integral comes by setting $g (x) = e^{x}$ ; $[\frac{x^{n}}{n!}] e^{x}$ is continued to equal $1$ for all complex $n$
if we denote $(n! (\sim n)! : = \frac{π}{- \sin (π n)}) [x^{n}] f (x) = \int_{0}^{\infty} \frac{f (- t)}{t^{n + 1}} d t = ℳ {λ t . f (- t)} (- n)$ by ${x^{n}} f (x)$ , then it behaves quite similarly to $[x^{n}]$ ; we have

${x^{n}} f (λ x) = λ^{n} {x^{n}} f (x)$
${x^{n}} x^{v} f (x) = {x^{n - v}} f (x)$
${x^{n}} f (- (- x)^{p}) = {x^{n / p}} f (x)$ (the somewhat awkward arrangement is because it needs to converge along negative reals)
${x^{n}} \log (\frac{1}{x}) f (x) = \frac{d}{d n} {x^{n}} f (x)$

the first two work in the same manner as ordinary coefficient extraction, but the last two work based on

{x^{n}} f (x)

being a complex function of

n

for instance, we can start with $(\sim n)! = {x^{n}} e^{x}$ , then use the second law for $(\sim \frac{n}{p})! = {x^{n}} e^{- (- x)^{p}}$ ; by dividing both sides by $(\sim n)!$ and using the recurrence for the factorial, we get $\frac{(\sim \frac{n}{p})!}{(\sim n)!} = [\frac{x^{n}}{n!}] e^{- (- x)^{p}}$ ; we know $[\frac{x^{n}}{n!}] e^{- (- x)^{p}} = [p d i v i d e s n] (- 1)^{n (1 + \frac{1}{p})} \frac{n!}{(\frac{n}{p})!}$ ; as such, we get the identity over the integers $(- 1)^{n (1 + \frac{1}{p})} \frac{(\sim \frac{n}{p})!}{(\sim n)!} = [p d i v i d e s n] \frac{n!}{(\frac{n}{p})!}$ which is maybe a little bit useful sometimes

Faulhaber's formula $\sum_{t = 1}^{y} t^{n} = [\frac{x^{n}}{n!}] \frac{e^{x y} - 1}{1 - e^{- x}}$ becomes $\frac{\int_{t = 0}^{\infty} \frac{1 - e^{- t y}}{e^{t} - 1} t^{n - 1} d t}{(n - 1)!} = \sum_{t = 1}^{y} t^{- n} = H_{y}^{(n)}$ . The $1$ in the numerator contributes $ζ (n) = H_{\infty}^{(n)}$ , so $\frac{\int_{t = 0}^{\infty} \frac{e^{- t y}}{e^{t} - 1} t^{n - 1} d t}{(n - 1)!} = ζ (n) - H_{y}^{(n)} = ζ (n, y + 1)$ , the Hurwitz incomplete zeta function
${\overline{B}}_{n}^{+} = [x^{n}] \frac{x}{1 - e^{- x}}$ becomes $\frac{\int_{t = 0}^{\infty} \frac{t^{- n}}{e^{t} - 1} d t}{n! (\sim n)!} = {\overline{B}}_{n}^{+}$ . By substituting $n = 1 - n$ in $\frac{\int_{t = 0}^{\infty} \frac{t^{n - 1}}{e^{t} - 1} d t}{(n - 1)!} = ζ (n)$ , we get that ${\overline{B}}_{n}^{+} = - \frac{ζ (1 - n)}{(n - 1)!} = \frac{- 2 \cos (\frac{π n}{2})}{(2 π)^{n}} ζ (n)$ (by the zeta function's reflection formula)
for the Stirling numbers, we write $\frac{n!}{k!}$ as $n^{\underline{n - k}}$ , then

since ${\binom{n}{k}} = n^{\underline{n - k}} [x^{n}] (e^{x} - 1)^{k}$ and ${\binom{- n}{- k}} = [\binom{k}{n}]$ , $[\binom{n}{k}] = (- k)^{\underline{n - k}} \frac{\int_{t = 0}^{\infty} (e^{- t} - 1)^{- n} t^{k - 1} d t}{(k - 1)!} = (- k)^{\underline{n - k}} [x^{- k}] (e^{x} - 1)^{- n} = (- k)^{\underline{n - k}} [x^{n - k}] {(\frac{x}{e^{x} - 1})}^{n} = k^{\overline{n - k}} [x^{n - k}] {(\frac{x}{1 - e^{- x}})}^{n}$
since $[\binom{n}{k}] = n^{\underline{n - k}} [x^{n}] \log {(\frac{1}{1 - x})}^{k}$ and $[\binom{- n}{- k}] = {\binom{k}{n}}$ , ${\binom{n}{k}} = (- k)^{\underline{n - k}} \frac{\int_{t = 0}^{\infty} \log {(\frac{1}{1 + x})}^{- n} t^{k - 1} d t}{(k - 1)!} = (- k)^{\underline{n - k}} [x^{- k}] \log {(\frac{1}{1 - x})}^{- n} = (- k)^{\underline{n - k}} [x^{n - k}] {(\frac{x}{\log (\frac{1}{1 - x})})}^{n} = k^{\overline{n - k}} [x^{n - k}] {(\frac{x}{\log (1 + x)})}^{n}$

since exponents of g.f.s correspond with nested convolutions of sequences, these two translate to sums of products over partitions

\begin{aligned} [\binom{n}{k}] & = k^{\overline{n - k}} \sum_{\binom{P \in ℕ^{n}}{\sum (P) = n - k}} \prod_{b \in P} {\overline{B}}_{b}^{+} \\ {\binom{n}{k}} & = k^{\overline{n - k}} \sum_{\binom{P \in ℕ^{n}}{\sum (P) = n - k}} \prod_{b \in P} G_{b} \end{aligned}

knowing that $\int_{t = 0}^{\infty} \frac{1 - e^{- t y}}{e^{t} - 1} t^{n - 1} d t = (n - 1)! H_{y}^{(n)}$ , we can take the e.g.f. for this as a sequence in $n$ ,

\begin{aligned} \sum_{n = 1}^{\infty} H_{y}^{(n)} \frac{x^{n}}{n} & = \sum_{n = 1}^{\infty} \int_{t = 0}^{\infty} \frac{1 - e^{- t y}}{e^{t} - 1} t^{n - 1} d t \frac{x^{n}}{n!} \\ = \int_{t = 0}^{\infty} \frac{1 - e^{- t y}}{e^{t} - 1} \sum_{n = 1}^{\infty} t^{n - 1} \frac{x^{n}}{n!} d t \\ = \int_{t = 0}^{\infty} \frac{1 - e^{- t y}}{e^{t} - 1} \frac{e^{t x} - 1}{t} d t \end{aligned}

the derivative in $x$ is $\sum_{n = 0}^{\infty} H_{y}^{(n + 1)} x^{n} = \int_{t = 0}^{\infty} \frac{1 - e^{- t y}}{e^{t} - 1} e^{t x} d t$ ; we can rewrite this as $\sum_{n = 0}^{\infty} H_{y}^{(n + 1)} x^{n} = \int_{t = 0}^{\infty} \frac{e^{t x} - e^{t (x - y)}}{e^{t} - 1} d t$ . This is a difference between two of the $n = 1$ case of the previous Hurwitz zeta integral, $\int_{t = 0}^{\infty} \frac{e^{- t y}}{e^{t} - 1} d t = ζ (1) - H_{y}^{(1)} = ζ (1, y + 1)$ , so $\sum_{n = 0}^{\infty} H_{y}^{(n + 1)} x^{n} = ζ (1, 1 + y - x) - ζ (1, 1 - x) = H_{y - x} - H_{- x}$ , which Mathematica says is valid for $ℜ (y) > ℜ (x) - 1 < 0$ .

So, $\sum_{n = 1}^{\infty} H_{y}^{(n)} \frac{x^{n}}{n} = \log ((- x)^{\underline{- y}} : = \frac{(- x)!}{(y - x)!})$ , ie. $\frac{H_{y}^{(n)}}{n} = [x^{n}] \log ((- x)^{\underline{- y}})$ . By Ramanujan's master theorem again, we get $\frac{\sum_{t = 1}^{y} t^{n}}{n} = [\frac{x^{n}}{(n - 1)!}] \frac{e^{x y} - 1}{1 - e^{- x}} = (n - 1)! \sum_{k = 1}^{n + 1} {\overline{B}}_{n + 1 - k}^{+} \frac{y^{k}}{k!} = [x^{- n}] \log (\frac{(y - x)!}{(- x)!})$ , so $\log (\frac{(y - x)!}{(- x)!}) = \sum_{k = 0}^{\infty} {\overline{B}}_{k}^{+} \sum_{n = k}^{\infty} \frac{(n - 1)!}{x^{n}} \frac{y^{n + 1 - k}}{(n + 1 - k)!} = \sum_{k = 0}^{\infty} {\overline{B}}_{k}^{+} \frac{(y + x ((1 - y / x)^{k} - 1)) (k - 2)!}{(x - y)^{k}}$

harmonic asymptotic for cycle columns

Knowing that $o g f (λ c . \frac{H_{y}^{(c)}}{c}) = \log ((- x)^{\underline{- y}})$ , we can write $\frac{1}{x^{\underline{- y}}} = (x + 1)^{\overline{y}} = \exp (o g f (λ c . (- 1)^{c - 1} \frac{H_{y}^{(c)}}{c}))$ . It makes sense to think of this instead as $\exp (e g f (λ c . (- 1)^{c - 1} (c - 1)! H_{y}^{(c)}))$ , since (via Faà di Bruno) the $\exp$ counts sets of its input's object type, and the interior counts cycles 'coloured' with variables that happen to be harmonic numbers. As such, an e.g.f. coefficient extraction can be written as a sum over permutations.

Then since $[x^{k}] (x + 1)^{\overline{n}} = [x^{k + 1}] x^{\overline{n + 1}} = [\binom{n + 1}{k + 1}]$ , we have $[\binom{n + 1}{k + 1}] = \frac{n!}{k!} \sum_{p \in s e t s (c y c l e s) (k)} \prod_{c \in p} (- 1)^{| c | - 1} H_{n}^{(| c |)}$ .

this is useful! if one fixes $k$ then as $n \to \infty$ , we can rewrite it as $[\binom{n + 1}{k + 1}] \sim \frac{n!}{k!} \sum_{p \in s e t s (c y c l e s) (k)} H_{n}^{| {c \in p : | c | = 1} |} \prod_{\binom{c \in p}{| c | > 1}} (- 1)^{| c | - 1} ζ (| c |)$ ; so we can write

\begin{aligned} [\binom{n + 1}{k + 1}] & \sim \frac{n!}{k!} \sum_{j = 0}^{k} (\binom{k}{j}) H_{n}^{k - j} \sum_{d \in d e r a n g e m e n t s (j)} (- 1)^{j - | d |} \prod_{c \in d} ζ (c) \\ = \frac{n!}{k!} (H_{n}^{k} - (\binom{k}{2}) ζ (2) H_{n}^{k - 2} + (\binom{k}{3}) 2 ζ (3) H_{n}^{k - 3} + (\binom{k}{4}) (3 ζ (2)^{2} - 6 ζ (4)) H_{n}^{k - 4} - \dots) \end{aligned}

(a refinement to the DLMF's 26.8.40)

more musings:

Defining the coefficient $D (j) = \sum_{d \in d e r a n g e m e n t s (j)} (- 1)^{j - | d |} \prod_{c \in d} H_{n}^{(c)}$ , noting that constructing derangements by adding cycles to preceding cases gives $D (j) = \sum_{i = 2}^{j} \frac{j^{\underline{i}}}{j} H_{n}^{(i)} (- 1)^{i - 1} D (j - i)$ . Writing $d (j) = \frac{D (j)}{j!}$ this is $j d (j) = \sum_{i = 2}^{j} (- 1)^{i - 1} H_{n}^{(i)} d (j - i)$ . Since $\sum_{i = 2}^{\infty} H_{n}^{(i)} (- x)^{i - 1} = H_{n + x} - H_{n} - H_{x}$ , writing $F (x) = \sum_{j = 0}^{\infty} d (j) x^{j}$ , we have $\frac{F^{'} (x)}{F (x)} = H_{n + x} - H_{x}$ so $D (j) = [\frac{x^{j}}{j!}] e^{\int_{t = 0}^{x} H_{n + t} - H_{n} - H_{t}}$ (where the approximation reduces this to $[\frac{x^{j}}{j!}] e^{\int_{t = 0}^{x} - H_{t}}$ ), so

\begin{aligned} [\binom{n + 1}{k + 1}] & = \frac{n!}{k!} \sum_{j = 0}^{k} (\binom{k}{j}) H_{n}^{k - j} [\frac{x^{j}}{j!}] e^{\int_{t = 0}^{x} H_{n + t} - H_{n} - H_{t}} \\ = n! [x^{k}] e^{H_{n} x + \int_{t = 0}^{x} H_{n + t} - H_{n} - H_{t}} \\ = n! [x^{k}] (\binom{n + x}{x}) \\ = [x^{k}] ((x + 1)^{\overline{n}} \sim_{n} \frac{e^{x (H_{n} - γ)}}{x!}) # b y s u b s t i t u t i n g H_{n}^{(i)} f o r ζ (i) \end{aligned}

note that there is a dual!

\begin{aligned} [\binom{n + 1}{k + 1}] & = n! [x^{k}] (\begin{aligned} (x + 1)^{\overline{n}} \\ = & \exp (e g f (λ c . (- 1)^{c - 1} (c - 1)! H_{n}^{(c)})) \end{aligned}) = \frac{n!}{k!} \sum_{p \in s e t s (c y c l e s) (k)} (- 1)^{k - | p |} \prod_{c \in p} H_{n}^{(| c |)} \\ Δ^{n} (λ i . {\begin{cases} 0 & i = 0 \\ \frac{1}{i^{k}} & e l s e \end{cases}) (0) & = n! [x^{k}] (\begin{aligned} \frac{- 1}{(x - 1)^{\underline{n}}} = - x^{\overline{- n}} \\ = & (- 1)^{n - 1} \exp (e g f (λ c . (c - 1)! H_{n}^{(c)})) \end{aligned}) = \frac{(- 1)^{n - 1}}{k!} \sum_{p \in s e t s (c y c l e s) (k)} \prod_{c \in p} H_{n}^{(| c |)} = n^{{- k}} \end{aligned}

these numbers $n^{{- k}}$ (which arise when interpreting the extension of the cycle row g.f.s backwards as a Taylor rather than Laurent series, and also in expansions of recursive integrals of powers of logarithms) are covered thoroughly in section Subpowers with negative integer exponents beginning p.12 of ^[2]

Stirling polynomials

The fact $[\binom{n}{k}] = k^{\overline{n - k}} [x^{n - k}] {(\frac{x}{1 - e^{- x}})}^{n}$ can be rewritten $\frac{[\binom{y}{y - n}]}{(\binom{y - 1}{n})} = [\frac{x^{n}}{n!}] {(\frac{x}{1 - e^{- x}})}^{y} = \sum_{k = 0}^{n} y^{k} \sum_{\binom{S \in ℕ_{1}^{k}}{Σ (S) = n}} \prod_{p \in S} [\frac{x^{p}}{p!}] \log (\frac{x}{1 - e^{- x}})$ . (Since ${v a l}_{x} (\log (\frac{x}{1 - e^{- x}})) = 1$ , each of the $k$ summands must be at least $1$ , so the inner sum has a nonzero number of summands iff $k \in [1 . . n]$ , or $k = 0$ (the empty partition) for $n = 0$ .) As such, $\frac{[\binom{y}{y - n}]}{(y - 1)^{\underline{n}}}$ is a polynomial in $y$ of degree $n$ , and therefore so too is the more pleasant index-shift $\frac{[\binom{n + y}{y}]}{((\binom{y}{n}))}$ !

and by the same argument, ${\binom{n}{k}} = k^{\overline{n - k}} [x^{n - k}] {(\frac{x}{\log (1 + x)})}^{n}$ becomes $\frac{{\binom{y}{y - n}}}{(\binom{y - 1}{n})} = [\frac{x^{n}}{n!}] {(\frac{x}{\log (1 + x)})}^{y} = \sum_{k = 0}^{n} y^{k} \sum_{\binom{S \in ℕ_{1}^{k}}{Σ (S) = n}} \prod_{p \in S} [\frac{x^{p}}{p!}] \log (\frac{x}{\log (1 + x)})$

there is a name for these, the Nørlund/generalised Bernoulli numbers! see this answer for how the cycle triangle's columns further leftwards (with their zeroes divided out) give coefficients for higher-order versions of #Faulhabernoulli's formula.

for $n > 0$ , we have

{\overline{G}}_{n} = [x^{n}] \frac{x}{\log \frac{1}{1 - x}} = \frac{1}{(n - 1)!} \frac{d}{d x} [\binom{n + x}{x}] |_{x = - 1}

(due to

G_{n} = \frac{- B_{n}^{(n - 1)}}{n - 1} = \frac{(- 1)^{n}}{(n - 1)!} \frac{d}{d x} [\binom{n + x}{x}] |_{x = - 1}

)

\frac{A 002208 (n)}{A 002209 (n)} = [x^{n}] \frac{x}{(1 - x) \log \frac{1}{1 - x}} = \frac{1}{(n - 1)!} \frac{d}{d x} [\binom{n + x}{x}] |_{x = 0}

^{[n 2]}

{\overline{B}}_{n}^{-} = [x^{n}] \frac{x}{e^{x} - 1} = B_{n}^{(1)} = \frac{1}{(n - 1)!} \frac{d}{d x} {\binom{n + x}{x}} |_{x = - 1}

{\overline{B}}_{n}^{+} = [x^{n}] \frac{x}{1 - e^{- x}} = \frac{1}{(n - 1)!} \frac{d}{d x} {\binom{n + x}{x}} |_{x = 0}

recurrence relations

see also my big math.se post about this

linear

only for subset numbers

o.g.f.s

unravelling the cycle row o.g.f. and subset column o.g.f. as products gives

[\binom{n}{k}] = \sum_{\binom{S \subseteq {0 . . n - 1}}{| S | = n - k}} \prod_{i \in S} i

{\binom{n}{k}} = \sum_{\binom{S \underset{m u l t}{\subseteq} {0 . . k}}{| S | = n - k}} \prod_{i \in S} i = \sum_{\binom{P \in ℕ^{k}}{\sum (P) = n - k}} \prod_{i = 1}^{k} i^{P_{i}}

(where $\underset{m u l t}{\subseteq}$ denotes making a multiset by drawing from a set with multiplicity, and the latter sum is just a run-length encoding)

only the latter can be partially unravelled into preceding cases, to give the recurrence

{\binom{n}{k}} = \sum_{b = 0}^{n - k} k^{b} {\binom{n - 1 - b}{k - 1}}

e.g.f.s

likewise,

\begin{aligned} L a h (\binom{n}{k}) & = \frac{n!}{k!} \sum_{\binom{P \in ℕ_{1}^{k}}{\sum (P) = n}} 1 & = \frac{n!}{k!} (\binom{n - 1}{k - 1}) \\ [\binom{n}{k}] & = \frac{n!}{k!} \sum_{\binom{P \in ℕ_{1}^{k}}{\sum (P) = n}} \frac{1}{\prod_{b \in P} b} \\ {\binom{n}{k}} & = \frac{n!}{k!} \sum_{\binom{P \in ℕ_{1}^{k}}{\sum (P) = n}} \frac{1}{\prod_{b \in P} b!} \end{aligned}

which becomes

\begin{aligned} L a h (\binom{n}{k}) & = \sum_{b = 1}^{n - k} \frac{n^{\underline{b}}}{k} L a h (\binom{n - b}{k - 1}) \\ [\binom{n}{k}] & = \sum_{b = 1}^{n - k} \frac{n^{\underline{b}}}{b k} [\binom{n - b}{k - 1}] \\ {\binom{n}{k}} & = \sum_{b = 1}^{n - k} \frac{(\binom{n}{b})}{k} {\binom{n - b}{k - 1}} \end{aligned}

these become more evident when written via the Stirling powers; the coefficient tells you how many ways you can take out $b$ elements and arrange them into the first list/cycle/set in the ordered list of lists/cycles/sets

\begin{aligned} k^{(n)} & = \sum_{b = 1}^{n - k} n^{\underline{b}} (k - 1)^{(n - b)} \\ k^{[n]} & = \sum_{b = 1}^{n - k} \frac{n^{\underline{b}}}{b} (k - 1)^{[n - b]} \\ k^{{n}} & = \sum_{b = 1}^{n - k} (\binom{n}{b}) (k - 1)^{{n - b}} \end{aligned}

duality

employing the Stirling duality on e.g.f.s (from #Ramanujan's master theorem) gives

\begin{aligned} [\binom{n + 1}{k + 1}] & = \frac{n}{k} \sum_{b = 0}^{n - k} {\overline{B}}_{b}^{+} k^{\overline{b}} [\binom{n}{k + b}] \\ {\binom{n + 1}{k + 1}} & = \frac{n}{k} \sum_{b = 0}^{n - k} G_{b} k^{\overline{b}} {\binom{n}{k + b}} \end{aligned}

or

\begin{aligned} \frac{(k + 1)^{[n + 1]}}{k + 1} & = n \sum_{b = 0}^{n - k} {\overline{B}}_{b}^{+} \frac{(k + b)^{[n]}}{k + b} \\ \frac{(k + 1)^{{n + 1}}}{k + 1} & = n \sum_{b = 0}^{n - k} G_{b} \frac{(k + b)^{{n}}}{k + b} \end{aligned}

another formulation can also be derived with indexes shifted; this lets you use it down to $k = 1$ without division-by-0 issue

\begin{aligned} k^{[n]} & = n \sum_{b = 0}^{n - k} {\overline{B}}_{b}^{+} (k + b - 1)^{[n - 1]} \\ k^{{n}} & = n \sum_{b = 0}^{n - k} G_{b} (k + b - 1)^{{n - 1}} \end{aligned}

transforms

as shown there, we have

{\binom{n + 1}{k + 1}} = \sum_{i = k}^{n} (\binom{n}{i}) {\binom{i}{k}}

[\binom{n + 1}{k + 1}] = \sum_{i = k}^{n} \frac{n!}{i!} (\binom{n}{i}) (- 1)^{i - k} [\binom{i}{k}]

moments of statistical distributions

^[16] gives applications to a few kinds of random variables' factorial and ordinary moments

table of their results (and more!) in nicer formatting:

as a recap,

binomial is "how many heads in $n$ tosses"
Poisson is "if [event] occurs randomly (chance unaffected by past occurrences, like radioactive decay) with $λ$ instances expected in the measuring duration, how many are actually observed"
geometric is "how many tails before one heads"
negative binomial is "how many tails before $n$ heads"
coupon is the coupon collector's problem; the random variable $X$ is how many times one must roll an $n$ -sided fair die for all faces to land up at least once (I copied the analysis done for this table (slightly more verbosely) into there, since it superseded the old method)

given the o.g.f. for $P (X = x)$ ,

the e.g.f. for $E (X^{\underline{k}})$ (ie. the o.g.f. for $E (\binom{X}{k})$ ) is obtained by replacing each $x$ with $x + 1$
the e.g.f. for $E (X^{k})$ is obtained from that of $E (X^{\underline{k}})$ by replacing each $x$ with $e^{x} - 1$

name	uniform	binomial	Poisson	geometric	negative binomial	hypergeometric	cycle count	coupon
$P (X = x)$	$\frac{[0 \leq x < n]}{n}$	$\begin{aligned} (\binom{n}{x}) p^{x} q^{n - x} \\ = & [t^{x}] (q + p t)^{n} \end{aligned}$	$e^{- λ} \frac{λ^{x}}{x!}$	$p q^{x}$	$\begin{aligned} p^{n} ((\binom{n}{x})) q^{x} \\ = & [t^{x}] {(\frac{p}{1 - q t})}^{n} \end{aligned}$	$\begin{aligned} \frac{(\binom{K}{x}) (\binom{N - K}{n - x})}{(\binom{N}{n})} \\ = & [t^{x}] \frac{(N - K)^{\underline{n}}}{N^{\underline{n}}}_{2} G_{2} (\binom{\sim n, \sim K}{0, N - K - n}; t) \end{aligned}$	$\begin{aligned} \frac{[\binom{n}{x}]}{n!} \\ = & [t^{x}] ((\binom{t}{n})) \end{aligned}$	$\begin{aligned} \frac{(n - 1)^{{x - 1}}}{n^{x - 1}} \\ = [t^{x}] (\frac{n!}{{(\frac{n}{t})}^{\underline{n}}} = \frac{1}{(\binom{\frac{n}{t}}{n})}) \end{aligned}$
$P (X \leq x)$	$\frac{x + 1}{n}$	$(\binom{n}{x}) p^{x} q^{n - x}_{1} G_{1} (\binom{\sim x}{n - x}; - \frac{q}{p})$	$\frac{Γ (x + 1, λ)}{x!}$	$1 - q^{x + 1}$	$p^{n - 1} ((\binom{n}{x})) (1 - q^{x + 1})$	$\frac{(\binom{K}{x}) (\binom{N - K}{n - x})}{(\binom{N}{n})}_{2} G_{2} (\binom{K - N + n + \sim x, \sim x}{n - x, K - x}; 1)$ ^{[n 3]}	A349782(n,x)	$\frac{n^{{x}}}{n^{x}}$
$E (X^{\underline{k}})$	$\begin{aligned} \frac{(n - 1)^{\underline{k}}}{k + 1} \\ = & [\frac{x^{k}}{k!}] \frac{(1 + x)^{n} - 1}{n x} \end{aligned}$ ^{[n 4]}	$\begin{aligned} n^{\underline{k}} p^{k} q^{n - k}_{1} F_{0} (\binom{k - n}{}; - \frac{p}{q}) \\ = & n^{\underline{k}} p^{k} \\ = & [\frac{x^{k}}{k!}] (1 + p x)^{n} \end{aligned}$	$λ^{k}$	$\begin{aligned} k! {(\frac{q}{p})}^{k} \\ = & [\frac{x^{k}}{k!}] \frac{1}{1 - \frac{q}{p} x} \end{aligned}$	$\begin{aligned} n^{\overline{k}} {(\frac{q}{p})}^{k} \\ = & [\frac{x^{k}}{k!}] \frac{1}{{(1 - \frac{q}{p} x)}^{n}} \end{aligned}$	$\frac{n^{\underline{k}} K^{\underline{k}}}{N^{\underline{k}}}$	$\begin{aligned} [x^{k}] ((\binom{e^{x} - 1}{n})) \end{aligned}$	$\begin{aligned} [\frac{x^{k}}{k!}] \frac{1}{(\binom{\frac{n}{x + 1}}{n})} \\ = & n k! \sum_{i = 0}^{n} (\binom{\sim i}{\sim n}) i \frac{(i - 1)^{k - 1}}{(n + 1 - i)^{k + 1}} \\ = & k! \sum_{i = 0}^{k} (\binom{- i}{- k}) [y^{i}] \frac{1}{(\binom{n - n y}{n})} \\ = & \sum_{i = 0}^{k} L a h (\binom{k}{i}) (- 1)^{k - i} n^{i} \sum_{P \in p e r m s (i)} \prod_{c \in P} H_{n}^{(\| c \|)} \end{aligned}$ ^{[n 5]}
$E (X^{k})$ ^{[n 6]}	$\begin{aligned} \frac{\sum_{x = 0}^{n - 1} x^{k}}{n} \\ = & \sum_{i = 0}^{k} {\binom{k}{i}} \frac{(n - 1)^{\underline{i}}}{i + 1} \\ = & [\frac{x^{k}}{k!}] \frac{e^{n x} - 1}{n (e^{x} - 1)} \end{aligned}$	$\begin{aligned} \sum_{x = 0}^{n} (\binom{n}{x}) p^{x} q^{n - x} x^{k} \\ = & \sum_{i = 0}^{k} {\binom{k}{i}} n^{\underline{i}} p^{i} \\ = & [\frac{x^{k}}{k!}] (1 + p (e^{x} - 1))^{n} \\ \underset{k}{\sim} & (n p)^{k} \frac{{(p + \frac{q}{e^{k / n}})}^{n - k}}{\sqrt{1 + \frac{k q}{n p e^{k / n}}}} \end{aligned}$ ^{[n 7]}	${B e l l}_{k} (λ)$	$\begin{aligned} p \sum_{x = 0}^{\infty} q^{x} x^{k} \\ = & \sum_{i = 0}^{k} i^{{k}} {(\frac{q}{p})}^{i} \\ = & \sum_{j = 0}^{k - 1} {⟨ \binom{k}{j} ⟩}_{0} \frac{q^{k - j}}{p^{k}} \\ = & [\frac{x^{k}}{k!}] \frac{1}{1 - \frac{q}{p} (e^{x} - 1)} \end{aligned}$	$\begin{aligned} p^{n} \sum_{x = 0}^{\infty} ((\binom{n}{x})) q^{x} x^{k} \\ = & \sum_{i = 0}^{k} {\binom{k}{i}} n^{\overline{i}} {(\frac{q}{p})}^{i} \\ = & [\frac{x^{k}}{k!}] \frac{1}{{(1 - \frac{q}{p} (e^{x} - 1))}^{n}} \end{aligned}$	$\begin{aligned} \frac{n^{\underline{k}} K^{\underline{k}}}{N^{\underline{k}} k!}_{2} G_{2} (\binom{N - k, \sim k}{n - k, K - k}; - ξ), \\ w h e r e ξ^{i} = (k - i)^{{k}} \end{aligned}$	$\begin{aligned} \frac{1}{n!} \sum_{i = 0}^{n} [\binom{n}{i}] i^{k} \\ = & [\frac{x^{k}}{k!}] ((\binom{e^{x}}{n})) \\ = & [\frac{x^{k}}{k!} y^{n}] \frac{1}{(1 - y)^{e^{x}}} \\ = & [y^{k}] \frac{1}{1 - y} \sum_{i = 0}^{k} {\binom{k}{i}} \log {(\frac{1}{1 - y})}^{i} \\ = & \sum_{i = 0}^{k} {\binom{k}{i}} \sum_{j = 0}^{n} \frac{i!}{j!} [\binom{j}{i}] \\ = & \sum_{i = 0}^{k} {\binom{k}{i}} \frac{i!}{n!} [\binom{n + 1}{i + 1}] \\ = & \sum_{i = 0}^{k} {\binom{k}{i}} \sum_{p \in p e r m s (i)} \prod_{c \in p} (- 1)^{\| c \| - 1} H_{n}^{(\| c \|)} \end{aligned}$	$\begin{aligned} [\frac{x^{k}}{k!}] \frac{n!}{{(\frac{n}{e^{x}})}^{\underline{n}}} \\ = & \sum_{i = 0}^{k} {\binom{k}{i}} (- 1)^{k - i} n^{i} \sum_{P \in p e r m s (i)} \prod_{c \in P} H_{n}^{(\| c \|)} \\ = & \sum_{i = 0}^{k} (- 1)^{n - 1 + k - i} i^{{k}} n^{{- i}} n^{i} \end{aligned}$ ^{[n 8]}

the Poisson distribution's moments being the Bell polynomials is sometimes also referred to as the Dobiński's formula, and the fact that we can do saddlepointery for binomial but not negative binomial is a consequence of the e.g.f. conserving the Hayman-admissible pole at $x = \infty$ , whereas the negative one produces a finite-order simple pole as the nearest to the origin

note this tells you that $o g f (λ i . i^{{k}}) = 𝔼 [{\underset{p = \frac{1}{1 + x}}{g e o m}}^{k}]$ and $o g f (λ j . {⟨ \binom{k}{j} ⟩}_{0}) = (x - 1)^{k} 𝔼 [{\underset{p = 1 - \frac{1}{x}}{g e o m}}^{k}]$ , which means both are log-convex sequences with respect to $k$ for all $x$ by Hölder's inequality ( $𝔼 [X^{i}] = 𝔼 [\sqrt{X^{i - 1} X^{i + 1}}] \leq \sqrt{𝔼 [X^{i - 1}] 𝔼 [X^{i + 1}]}$ )

historical/nomenclaturewise notes

the abstract of ^[2] notes that Euler had written the number triangle of $k^{{n}}$ in 1755, which might imply (since they're only a factorial factor away) the Stirling subset numbers would more aptly be called Euler numbers; Unfortunately,
in many sources, the univariate Bell polynomials are known as the Touchard polynomials; however, per Ramanujan's notebooks, part 1, p. 11, Ramanujan had developed a lot of the same theory as Bell and Touchard over two decades prior, so either name is a slight misnomer (but the cards have fallen where they lay)

attributions

thank you very much to my dear friend MagmaMcFry (from the ConwayLife lounge) for finding the bijective proofs of some of the identities found here

notes

↑ and since $\frac{d}{d y} \frac{1}{1 - y} = \frac{d}{d y} \frac{y}{1 - y}$ we can set $g_{0} (y) = \frac{1}{1 - y}$ in order for this to hold for all $n$ by the convention $0^{0} = 1$ ; since every $g_{0} = \frac{c + (1 - c) y}{1 - y}$ works, the Eulerian numbers take no opinion on $0^{0}$ 's true value.
↑ and $\frac{A 075266 (n)}{A 075267 (n)} = [x^{n}] \log \frac{\log \frac{1}{1 - x}}{x} = \frac{1}{n!} \frac{d}{d x} [\binom{n + x}{x}] |_{x = 0}$ , since $\frac{A 075266 (n)}{A 075267 (n)} = \frac{A 002208 (n)}{n \cdot A 002209 (n)}$
↑ this is unfortunately not the kind of $_{2} G_{2}$ that is solved by the generalisation of of Saalschutz's theorem given in my hypergeometrics page; one requires that $m = N$ . However, note that if the $G$ is turned into an $I$ to become bilateral, then applying Dougall's sum evaluates to $1$ ; that is, the integer-parameters bilaterally-terminating case of Dougall's theorem is equivalent to the fact that summing the p.d.f. over all $x$ gives $1$
↑ Zeilberger's algorithm helpfully tells us the o.g.f. $f_{n} (x)$ satisfies the cute little D-finite recurrence $(n + 1) f_{n + 1} - n ((1 + n x) f_{n} + (n - 1) x f_{n - 1}) = 1$
↑ from the generating function, we have $\frac{1}{(\binom{\frac{n}{x + 1}}{n})} = \sum_{i = 0}^{n} \frac{(\binom{\sim i}{\sim n})}{1 - i (1 - \frac{n}{x + 1 + n})} = \sum_{i = 0}^{n} (\binom{\sim i}{\sim n}) (\frac{1 + n}{1 + n - i} + i n \sum_{k = 1}^{\infty} \frac{(i - 1)^{k - 1}}{(n + 1 - i)^{k + 1}} x^{k})$ , so for $k > 0$ we get the second line. Line 3 comes from writing it as the inverse binomial transform of its binomial transform, and the inner summation on line 4 is the expansion of $[\frac{y^{i}}{i!}] \frac{1}{(\binom{n - y}{n})}$ via the same method as #harmonic asymptotic for cycle columns took
↑ the e.g.f. for each entry here comes directly from applying the Stirling transform to the above entry's e.g.f. (ie. replacing $x$ with $e^{x} - 1$ ), providing (for the uniform dist.) a much shorter proof of the e.g.f. form of Faulhaber's theorem!
↑ $g (x) = n \frac{x}{1 + (\frac{q}{p}) e^{- x}}$ so $x_{k} = (j : = \frac{k}{n}) + (W : = W (\frac{j q}{e^{j} p}))$ , $g^{'} (x) = \frac{e^{x} n p}{q + e^{x} p} + \frac{e^{x} x n p q}{(q + e^{x} p)^{2}}$ , and $E (X^{k}) \sim_{k} \frac{k! q^{n} (j + W)^{n - k}}{W^{n} \sqrt{2 π k (1 + W)}} \sim (n p)^{k} \frac{{(p + \frac{q}{e^{k / n}})}^{n - k}}{\sqrt{1 + \frac{k q}{n p e^{k / n}}}}$ (the first by ordinary saddlepointery, the second by Stirling's approx. and truncating $W (x) \sim x$ for small values)
the ratio to $(n p)^{k}$ (asymptoted by the $\frac{{(p + \frac{q}{e^{k / n}})}^{n - k}}{\sqrt{1 + \frac{k q}{n p e^{k / n}}}}$ part) is at most $1$ , and this paper (p. 5) says it cannot exceed $\frac{1}{p^{k}}$ ; it converges to $\frac{p^{n}}{p^{k}}$
we have recurrence $E [X_{n}^{k + 1}] = n (E [X_{n}^{k}] - q E [X_{n - 1}^{k}])$
↑ this comes from the falling moments via the identity ${\binom{K}{i}} (- 1)^{K} = \sum_{k = 0}^{K} {\binom{K}{k}} L a h (\binom{k}{i}) (- 1)^{k}$

references

↑ ^1.0 ^1.1 A. M. Odlyzko, 1995. Asymptotic enumeration methods (page 118, equation (12.10))
↑ ^2.0 ^2.1 ^2.2 Mircea Dan Rus, 2025, Yet another note on notation
↑ J. G. Wendel, 1948. Note on the Gamma Function, Am. Math. Mo., Vol. 55, No. 9, pp. 563-564
↑ ^4.0 ^4.1 Donald Knuth, 1992. Two notes on notation
↑ Nicholas A. Loehr, Jeffrey B. Remmel, May 2009. Rook-by-rook rook theory: Bijective proofs of rook and hit equivalences
↑ Lemma 2.6 of E. G. Santos, November 24, 2024. Counting non-attacking chess pieces placements: Bishops and Anassas
for prerequisites to understand in somewhat more detail, read ^[5]
↑ bijective proof of Worpitzky's identity; StackExchange answer by EuYu, 2015
↑ Richard P. Stanley, Eulerian Partitions of a Unit Hypercube (1986)
↑ Fred J. Rispoli, 2008. The Graph of the Hypersimplex
↑ Pierre Simon de Laplace, 1812. Théorie analytique des probabilités, 1812
↑ L. A. Shepp, S. P. Lloyd, 1965. Ordered Cycle Lengths in a Random Permutation
↑ ^12.0 ^12.1 L. H. Harper, 1967. Stirling Behaviour is Asymptotically Normal
↑ Richard P. Stanley, Log-Concave and Unimodal Sequences in Algebra, Combinatorics and Geometry (1989)
↑ Masaaki Sibuya, Log-concavity of Stirling numbers and unimodality of Stirling distributions (1987)
(note i am citing it for things that it brought forth from earlier papers, otherwise there would be more here when it serves as a nice convenient grouping)
↑ O. Arfwedson, 1951. A probability distribution connected with Stirling's second class numbers, Scandinavian Actuarial Journal, vol. 1951, iss. 1-2, pp. 121-132
↑ S. Bagui, K.L. Mehra, 2024. The Stirling Numbers of the Second Kind and Their Applications (Alabama Journal of Mathematics, Vol. 47 (1), pp. 1-22) (read beginning at page 14)

[17] we can also write the coefficient as $(- 1)^{n - k} (\binom{n}{k}) = (\binom{\sim k}{\sim n})$

[18] where $[x^{n}] f (1 + x) = \sum_{k = n}^{\infty} k^{\underline{n}} a (k)$ ; so we can rewrite it $- \sum_{i = 0}^{\infty} b (i) \sum_{k = 0}^{n} (\binom{n}{k}) i^{\underline{k}}$ , where the inner sum can be rewritten $[\frac{x^{i}}{i!}] e^{x} (1 + x)^{n} =_{2} F_{0} (\binom{- n, - i}{}; 1) = i^{\underline{n}}_{1} F_{1} (\binom{- n}{i - n + 1}; - 1) \sim i^{n}$ .
the reason for the leading minus sign, informally, is that the sequence $b (n) = c^{n}$ requires $c < 1$ (though in general does not prohibit $\lim_{n \to \infty} \frac{a (n)}{a (n - 1)} = 1$ ) and multichoose-transforms forwards into $b (n) = {\frac{1}{1 - c}}^{n}$ , and exponentially-growing infinite sums resolve to negative values by analytic continuation, so the sign flips it back around

[7] since $\frac{d}{d y} \frac{1}{1 - y} = \frac{d}{d y} \frac{y}{1 - y}$ we can set $g_{0} (y) = \frac{1}{1 - y}$ in order for this to hold for all $n$ by the convention $0^{0} = 1$ ; since every $g_{0} = \frac{c + (1 - c) y}{1 - y}$ works, the Eulerian numbers take no opinion on $0^{0}$ 's true value.

[19] $\frac{A 075266 (n)}{A 075267 (n)} = [x^{n}] \log \frac{\log \frac{1}{1 - x}}{x} = \frac{1}{n!} \frac{d}{d x} [\binom{n + x}{x}] |_{x = 0}$ , since $\frac{A 075266 (n)}{A 075267 (n)} = \frac{A 002208 (n)}{n \cdot A 002209 (n)}$

[21] this is unfortunately not the kind of $_{2} G_{2}$ that is solved by the generalisation of of Saalschutz's theorem given in my hypergeometrics page; one requires that $m = N$ . However, note that if the $G$ is turned into an $I$ to become bilateral, then applying Dougall's sum evaluates to $1$ ; that is, the integer-parameters bilaterally-terminating case of Dougall's theorem is equivalent to the fact that summing the p.d.f. over all $x$ gives $1$

[22] Zeilberger's algorithm helpfully tells us the o.g.f. $f_{n} (x)$ satisfies the cute little D-finite recurrence $(n + 1) f_{n + 1} - n ((1 + n x) f_{n} + (n - 1) x f_{n - 1}) = 1$

[23] rom the generating function, we have $\frac{1}{(\binom{\frac{n}{x + 1}}{n})} = \sum_{i = 0}^{n} \frac{(\binom{\sim i}{\sim n})}{1 - i (1 - \frac{n}{x + 1 + n})} = \sum_{i = 0}^{n} (\binom{\sim i}{\sim n}) (\frac{1 + n}{1 + n - i} + i n \sum_{k = 1}^{\infty} \frac{(i - 1)^{k - 1}}{(n + 1 - i)^{k + 1}} x^{k})$ , so for $k > 0$ we get the second line. Line 3 comes from writing it as the inverse binomial transform of its binomial transform, and the inner summation on line 4 is the expansion of $[\frac{y^{i}}{i!}] \frac{1}{(\binom{n - y}{n})}$ via the same method as #harmonic asymptotic for cycle columns took

[24] the e.g.f. for each entry here comes directly from applying the Stirling transform to the above entry's e.g.f. (ie. replacing $x$ with $e^{x} - 1$ ), providing (for the uniform dist.) a much shorter proof of the e.g.f. form of Faulhaber's theorem!

[25] $g (x) = n \frac{x}{1 + (\frac{q}{p}) e^{- x}}$ so $x_{k} = (j : = \frac{k}{n}) + (W : = W (\frac{j q}{e^{j} p}))$ , $g^{'} (x) = \frac{e^{x} n p}{q + e^{x} p} + \frac{e^{x} x n p q}{(q + e^{x} p)^{2}}$ , and $E (X^{k}) \sim_{k} \frac{k! q^{n} (j + W)^{n - k}}{W^{n} \sqrt{2 π k (1 + W)}} \sim (n p)^{k} \frac{{(p + \frac{q}{e^{k / n}})}^{n - k}}{\sqrt{1 + \frac{k q}{n p e^{k / n}}}}$ (the first by ordinary saddlepointery, the second by Stirling's approx. and truncating $W (x) \sim x$ for small values)
the ratio to $(n p)^{k}$ (asymptoted by the $\frac{{(p + \frac{q}{e^{k / n}})}^{n - k}}{\sqrt{1 + \frac{k q}{n p e^{k / n}}}}$ part) is at most $1$ , and this paper (p. 5) says it cannot exceed $\frac{1}{p^{k}}$ ; it converges to $\frac{p^{n}}{p^{k}}$
we have recurrence $E [X_{n}^{k + 1}] = n (E [X_{n}^{k}] - q E [X_{n - 1}^{k}])$

[26] this comes from the falling moments via the identity ${\binom{K}{i}} (- 1)^{K} = \sum_{k = 0}^{K} {\binom{K}{k}} L a h (\binom{k}{i}) (- 1)^{k}$

[asympenum-1] 1.0 ^1.1 A. M. Odlyzko, 1995. Asymptotic enumeration methods (page 118, equation (12.10))

[another-2] 2.0 ^2.1 ^2.2 Mircea Dan Rus, 2025, Yet another note on notation

[3] J. G. Wendel, 1948. Note on the Gamma Function, Am. Math. Mo., Vol. 55, No. 9, pp. 563-564

[notetation-4] 4.0 ^4.1 Donald Knuth, 1992. Two notes on notation

[stirookling-5] Nicholas A. Loehr, Jeffrey B. Remmel, May 2009. Rook-by-rook rook theory: Bijective proofs of rook and hit equivalences

[6] Lemma 2.6 of E. G. Santos, November 24, 2024. Counting non-attacking chess pieces placements: Bishops and Anassas
for prerequisites to understand in somewhat more detail, read ^[5]

[8] tive proof of Worpitzky's identity; StackExchange answer by EuYu, 2015

[9] Richard P. Stanley, Eulerian Partitions of a Unit Hypercube (1986)

[10] Fred J. Rispoli, 2008. The Graph of the Hypersimplex

[11] Pierre Simon de Laplace, 1812. Théorie analytique des probabilités, 1812

[12] L. A. Shepp, S. P. Lloyd, 1965. Ordered Cycle Lengths in a Random Permutation

[normal-13] 12.0 ^12.1 L. H. Harper, 1967. Stirling Behaviour is Asymptotically Normal

[14] Richard P. Stanley, Log-Concave and Unimodal Sequences in Algebra, Combinatorics and Geometry (1989)

[15] Masaaki Sibuya, Log-concavity of Stirling numbers and unimodality of Stirling distributions (1987)
(note i am citing it for things that it brought forth from earlier papers, otherwise there would be more here when it serves as a nice convenient grouping)

[16] O. Arfwedson, 1951. A probability distribution connected with Stirling's second class numbers, Scandinavian Actuarial Journal, vol. 1951, iss. 1-2, pp. 121-132

[20] S. Bagui, K.L. Mehra, 2024. The Stirling Numbers of the Second Kind and Their Applications (Alabama Journal of Mathematics, Vol. 47 (1), pp. 1-22) (read beginning at page 14)

[1]

[2]

[3]

[4]

[6]

[n 1]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[t 1]

[t 2]

[n 2]

[16]

[n 3]

[n 4]

[n 5]

[n 6]

[n 7]

[n 8]

[5]

User:Natalia L. Skirrow/an introduction to Stirling numbers

foreword

tools

calculus of finite differences

power-analogue notations

binomial transforms

Faà di Bruno's formula

examples

Stirling-type triangles

cycle numbers (|A008275|,A132393)

subset numbers (A008277,A048993)

Lah numbers (|A008297|,A271703)

general matrix multiplications!

Ward's theorem

row g.f.s of the opposite kinds

subset row sums (Bell numbers A000110) and o.g.f.s (Bell polynomials)

cycle row rising g.f.s

combinatorial interpretations of Pochhammer calculus

the duality

Eulerian numbers (⟨nk⟩1=A008292(n,k)=A123125(n,k),⟨nk⟩0=A173018(n,k))

Eulerians in the hypercube!

calculus of the wrong kinds

Faulhabernoulli's formula

Gregory's dual thereto

asymptotics and properties as statistical distributions

row log-concavity inequalities

asymptotics along rays

transforms

the factorial integral

e.g.f.s to o.g.f.s (Laplace)

o.g.f.s to r.g.f.s (Mellin)

convergence

o.g.f.s to f.g.f.s

to recap on sequence transforms,

o.g.f.s to mixed kind (Lapllin transform)

Ramanujan's master theorem

harmonic asymptotic for cycle columns

Stirling polynomials

recurrence relations

linear

o.g.f.s

e.g.f.s

duality

transforms

moments of statistical distributions

historical/nomenclaturewise notes

attributions

see also

notes

references

Navigation menu

Search

Eulerian numbers ( ${⟨ \binom{n}{k} ⟩}_{1}$ =A008292(n,k)=A123125(n,k), ${⟨ \binom{n}{k} ⟩}_{0}$ =A173018(n,k))