Hello, Codeforces!
1. Recently, adamant published an excellent blog Stirling numbers with fixed n and k. There he described an approach to them via generating functions.
In this (messy) blog, I want to share one useful technique on the example of Stirling numbers of the first kind.
2. We start with the definition of the Stirling transformation of a sequence $$$(x_n)$$$ is the following mapping
$$$\displaystyle \{x_n\} \xrightarrow{\quad Stirling\quad} \left\{ \sum_{k=0}^{n} s(n,k) x_k \right\}, $$$where $$$s(n,k)$$$ is a first-kind Stirling number. Here we have a place of flexibility for our technique: we can choose any other function $$$f(n,k)$$$ instead of Stirling numbers, though it only sometimes turns out to be useful.
3. The essence of this method is to find the transition formulae between Stirling transformations of a sequence $$$(x_n)$$$ and the sequence of its finite differences (one can think of it as a discrete analogue of derivative) $$$(y_n)$$$ defined by
$$$\displaystyle \{x_n\} \xrightarrow{\quad \Delta\quad} \{x_{n+1}-x_n\}. $$$The acquaintance with finite differences is highly recommended for the readers of this blog.
Theorem 1 (Transition formulae). In fact, the following transition formulae hold:
Step 1. How to work with finite differences?
Theorem 2 (solving first-order linear difference equation). Let $$$(y_k)$$$ be a recurrence relation that satisfies
$$$\displaystyle y_{k+1} = p_k y_{k} + q_k, $$$where $$$(p_k), (q_k)$$$ are given sequences and there is no $$$i$$$ such that $$$p_i=0$$$, then the solution to this equation is given by
$$$\displaystyle y_k = \prod_{j=0}^{k-1} p_j \left( \sum_{j=0}^{k-1} \frac{q_j}{\prod_{\ell=0}^{j} p_\ell } + C\right) $$$ ProofFor the shortness of calculations, we introduce the following sequence
$$$\displaystyle \Pi_k = p_0\dots p_k. $$$It is easy to see that if $$$q_k=0$$$, then the solution is
$$$\displaystyle y_k = y_0 \Pi_{k-1}. $$$Indeed, one may multiply all recurrences
$$$\displaystyle \begin{array}{rcl} y_1 & = & p_0 y_0\\ y_2 & = & p_1 y_1\\ \vdots & \vdots & \vdots\\ y_k & = & p_{k-1} y_{k-1} \end{array} $$$and obtain
$$$\displaystyle y_1\dots y_k = \Pi_{k-1} y_0\dots y_{k-1}. $$$hence
$$$\displaystyle y_k = y_0\Pi_{k-1} $$$Now we assume that $$$q_k\neq 0$$$ somewhere. We divide both parts of the equation by $$$\Pi_k$$$ and obtain
$$$\displaystyle \frac{y_{k+1}}{\Pi_k} = \frac{y_k}{\Pi_{k-1}} + \frac{q_k}{\Pi_k}. $$$We subtract
$$$\displaystyle \Delta \left( \frac{y_k}{\Pi_{k-1}} \right) = \frac{y_{k+1}}{\Pi_k} - \frac{y_k}{\Pi_{k-1}} = \frac{q_k}{\Pi_k} $$$We take an `integral’ ($$$\smallint_k$$$) in both sides of the last expression and obtain
$$$\displaystyle \frac{y_k}{\Pi_{k-1}} = \sum_{j=0}^{k-1} \frac{q_j}{\Pi_j} + C = \sum_{j=0}^{k-1} \frac{q_j}{\Pi_j} + C $$$Consequently, the formula is
$$$\displaystyle y_k = \Pi_{k-1} \left(\sum_{j=0}^{k-1} \frac{q_j}{\Pi_j} + C\right). $$$ Step 2. Proof of the Theorem 1.
ProofWe start from the following well-known lemma.
Lemma 1 (Pascal identity). For Stirling numbers of the first kind, it holds that
$$$ s(n+1,k) = n s(n,k) + s(n,k-1) $$$The proof is left as an exercise for the reader :)
Firstly, we shall prove the $$${b_n}\longrightarrow {c_n}$$$ formula.
Indeed,
$$$\displaystyle b_{n+1} - nb_n = \sum_{k=0}^{n+1} s(n+1,k) x_k - \sum_{k=0}^n n s(n,k) x_k = $$$ $$$\displaystyle s(n+1,n+1) x_{n+1} + \sum_{k=1}^{n} \left( s(n+1,k)-s(n,k) \right) x_k = $$$ $$$\displaystyle \sum_{k=1}^{n} s(n,k-1) x_k + s(n,n) x_{n+1} = \sum_{k=0}^{n} s(n,k) x_{k+1}. $$$Now consider
$$$\displaystyle b_{n+1} - nb_n - b_n = \sum_{k=0}^{n} s(n,k) x_{k+1} - \sum_{k=0}^{n} s(n,k) x_k = \sum_{k=0}^{n} s(n,k) y_k. $$$So, we have proved the first part of the theorem.
We have just proved that the following recurrence relation holds
$$$\displaystyle b_{n+1} = (n+1)b_n + c_n. $$$This equation is of the form discussed in Step 1. We apply Theorem 1. First, note that
$$$\displaystyle \prod_{j=1}^{k} (j+1) = (k+1)!\qquad \text{and}\qquad \prod_{j=1}^{k-1} (j+1) = k!. $$$Consequently,
$$$\displaystyle b_n = n! \left( C + \sum_{k=0}^{n-1} \frac{c_k}{(k+1)!} \right) $$$but $$$b_0 = s(0,0) x_0 = x_0$$$ so $$$C=x_0$$$ and
$$$\displaystyle b_n = n! \left( x_0 + \sum_{k=1}^{n} \frac{c_{k-1}}{k!} \right). $$$and we have just proved the second part of the theorem.
4. Using these transition formulae we can derive countless identities with Stirling numbers of the first kind (as well as identities involving binomial coefficients and other interesting combinatorial functions, as pointed out in 2). For example, taking $$$x_n = 1$$$, we obtain the following nice identity
$$$\displaystyle \sum_{k=0}^{n} s(n,k) = n! $$$visualised by the diagram
5. A nontrivial and interesting example. We exploit the combinatorial nature of $$$s(n,k)$$$ to write down the average number of cycles in a random permutation.
$$$\displaystyle \mathbf{E}[cycles] = \sum_{k=0}^{n} k \frac{s(n,k)}{n!} = \frac{\sum\limits_{k=0}^{n} k s(n,k)}{n!}. $$$We can easily find the sum in the numerator by applying theorem 1 to the sequence $$$x_n = n$$$.
where the ($$$\ast$$$) is given by the following formula
$$$\displaystyle \sum\limits_{k=0}^{n} k s(n,k) = n!\sum_{k=1}^{n} \frac{(k-1)!}{k!} = n!H_n, $$$where $$$H_n = 1 + 1/2 + \dots + 1/n$$$ is $$$n$$$-th Harmonic number. Hence $$$\mathbf{E}[cycles]=H_n=O(\log n)$$$, a very nice result!
ExerciseProve that
$$$\displaystyle \sum_{k=0}^n ks(n,k) = s(n+1,2). $$$ 6. We generalise 5 and 6 by consider the sequence $$$x_n = n^k$$$ for a fixed $$$k$$$. From adamant's blog (highly connected with this section), we know that first-kind Stirling numbers behave much better with falling factorials. So, in order to find a good formula for the Stirling transformation of $$$n^k$$$, we first find it for $$$(n)_k$$$ and then apply
$$$\displaystyle n^k = \sum_{j=0}^{k} S(n,j) (n)_j. $$$and derive the desired formula.
The details are left for the reader, here is the outline.
Step 1. Prove the identity $$$\sum_{j=0}^{N} s(j,k)/j! = 1/N! s(N+1,k+1)$$$ by double induction and Pascal-like identity (lemma 1).
Step 2. Apply Theorem 1 to $$$x_n=(n)_k$$$ (fix $$$k$$$) and using 1 prove that
$$$\displaystyle \sum_{n=0}^{N} s(N,n) (n)_k = k! s(N+1, k+1). $$$Step 3. Finally, prove that
$$$\displaystyle \sum_{j=0}^{N} s(N,n) n^k = \sum_{j=1}^{k} S(k,j) s(N+1, j+1) j!. $$$The last formula is obviously practical.
7 (Bonus).
Theorem 3 (transition between two kinds of Stirling numbers). Let $$$(a_n)$$$ be a sequence and
$$$\displaystyle b_n = \sum_{k=1}^{n} S(n,k) a_k $$$be is second-kind Stirling transform. Then
$$$\displaystyle a_n = \sum_{k=1}^{n} (-1)^{n-k} s(n,k) b_k. $$$ ProofConsider an $$$n$$$-element set. We split it into several subsets and build a structure on the set of the subsets. If we denote the number of ways to build the structure on the $$$k$$$-element set is $$$a_k$$$, then the number of ways to split and build the $$$n$$$-element set is equal to
$$$\displaystyle b_n = \sum_{k=1}^{n} S(n,k) a_k. $$$By composition formula for exponential generating functions, we have the following identity for exponential generating functions
$$$\displaystyle B(x) = A(e^x - 1) $$$because we (do nothing) build an identity structure on each set of the partition.
Let $$$x=\log(1+t)$$$, then
$$$\displaystyle A(t) = B(\log(1+t)). $$$We formally do
$$$\displaystyle \sum_{n=0}^{\infty} a_n \frac{t^n}{n!} = \sum_{k=0}^{\infty} b_k\frac{\log^k(1+t)}{k!} = \sum_{k=0}^{\infty} \left[ b_k \sum_{n=0}^{\infty} s(n,k) \frac{t^n}{n!}\right] = $$$ $$$\displaystyle \sum_{k=0}^{\infty} \sum_{n=0}^{\infty} s(n,k) b_k \frac{t^n}{n!} = \sum_{n=0}^{\infty} \left[ \left(\sum_{k=0}^{n} s(n,k) b_k\right) \frac{t^n}{n!} \right] $$$and compare coefficient of $$$t^n/n!$$$ in leftmost and rightmost parts.
8 (Remark). I mentioned twice that this method can be generalised. For example, for the binomial transformation
$$$\displaystyle \{x_n\} \xrightarrow{\quad Binom\quad} \left\{ \sum_{k=0}^{n} \binom{n}{k} x_k \right\}, $$$the main theorem will be the following
Using a similar strategy as in 6, we can prove that
$$$\displaystyle \sum_{n=0}^{N} \binom{N}{n} n^k = \sum_{j=0}^{k} S(k,j) \binom{n}{j} j! 2^{N-j}. $$$
Is this based on this article? Quite nice presentation! Yet, I generally don't like direct work with coefficients, so I tried to understand e.g. what formulas for binomial transformation and finite differences mean in terms of EGF.
So, the binomial transformation is equivalent to multiplying EGF $$$A(x)$$$ with $$$e^x$$$:
And finite differences, defined as $$$a_n \mapsto a_{n+1} - a_n$$$, correspond to the transform on EGF:
So, the binomial transform of finite differences is $$$e^x( A' - A)$$$, while the binomial transform of the initial sequence is $$$e^x A$$$.
To express the binomial transform of finite differences through the binomial transform of original sequence, we notice
Meaning that the transform from $$$b_k'$$$ to $$$c_k'$$$ should, indeed, be $$$\Delta b_k' - b_k'$$$ (I assume, $$$\Delta b_k' - b_k$$$ is a typo).
Unfortunately, I don't have any clear ideas right now on how to do something similar with Stirling numbers, or even how to derive the inverse formulas or interpret them in terms of genfuncs...
Ok, I see why the inverse transform is messy. So, we know that
How to get $$$G(x)$$$ from known $$$F(x)$$$? Well, it's just a linear diffeq, so there is a formula:
It probably yields the same result, but an easier way to solve it is, let $$$A(x)$$$ and $$$B(x)$$$ be the ordinary genfuncs of sequences, for which $$$F(x)$$$ and $$$G(x)$$$ are exponential genfuncs. Differentiation in EGFs translates to OGFs as
so we have
which gives the same conversion formula between $$$b'_k$$$ and $$$c'_k$$$.
Now, for Stirling transform, Wikipedia suggests that a proper representation, in terms of EGFs is
I guess, it makes sense, as
given that $$$\frac{\log(1+x)^k}{k!}$$$ is the EGF for $$$s(n, k)$$$ with fixed $$$k$$$. So, the Stirling transform of finite differences is
Using $$$[A(\log(1+x))]' = \frac{A'(\log(1+x))}{1+x}$$$, we can re-express it as a function of $$$A(\log(1+x))$$$ as
Note that it corresponds to transition formula $$$c_n = b_{n+1} + (n-1) b_n$$$ instead of $$$c_n = b_{n+1} - (n+1) b_n$$$.
This is because for signed Stirling numbers $$$s(n, k)$$$ the transition formula is
instead of
which was used in the blog.