Stirling numbers with fixed n and k

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hi everyone!

In combinatorics, you often need to compute Stirling numbers for various reason. Stirling numbers of the first kind count the number of permutations of $$$n$$$ elements with $$$k$$$ disjoint cycles, while Stirling numbers of the second kind count the number of ways to partition a set of $$$n$$$ elements into $$$k$$$ nonempty subsets. Besides that, they're often arise when you need to change between powers of $$$x$$$ and rising/falling factorials. There are three problems on Library Checker that go as follows:

Library Checker — Stirling Number of the First Kind. Given $$$N$$$, find $$$s(N, k)$$$ for $$$0 \leq k \leq N$$$.

Library Checker — Stirling Number of the Second Kind. Given $$$N$$$, find $$$S(N, k)$$$ for $$$0 \leq k \leq N$$$.

Library Checker — Stirling Number of the First Kind (Fixed K). Given $$$N$$$ and $$$K$$$, find $$$s(n, K)$$$ for $$$K \leq n \leq N$$$.

Here $$$s(n, k)$$$ are Stirling numbers of the first kind, and $$$S(n, k)$$$ are Stirling numbers of the second kind. Let's solve them!

Definitions

There are various ways to define Stirling numbers. In this blog, we will follow the algebraic approach to highlight their connection.

Def.: The falling factorial is the polynomial $$$(x)_n$$$ defined as

$$$ \boxed{(x)_n = \overbrace{x (x-1) \dots (x-n+1)}^{n\text{ factors}} = \prod\limits_{i=0}^{n-1} (x-i)} $$$

Def.: The rising factorial is the polynomial $$$x^{(n)}$$$ defined as

$$$ \boxed{x^{(n)} = \overbrace{x (x+1) \dots (x+n-1)}^{n\text{ factors}} = \prod\limits_{i=0}^{n-1} (x+i)} $$$

Note: From the definitions above, it follows that $$$x^{(n)} = (x+n-1)_n = (-1)^n (-x)_n$$$.

We will start with Stirling numbers of the second kind, as the proof is simpler for them.

Def.: Stirling numbers of the second kind are the coefficients $$$S(n, k)$$$ in the expansion of $$$x^n$$$ into falling factorials:

$$$ \boxed{x^n = \sum\limits_{k=0}^n S(n, k) (x)_k} $$$

Claim: The value $$$S(n, k)$$$ equates to $$$C(n, k)$$$ the number of ways to partition $$$n$$$ distinct elements into $$$k$$$ non-empty sets.

Note: We assume that there is a unique way to partition a set of $$$0$$$ elements into $$$0$$$ non-empty sets.

Proof

Def.: Stirling numbers of the first kind are the coefficients $$$s(n, k)$$$ in the expansion of $$$(x)_n$$$ into powers of $$$x$$$:

$$$ \boxed{(x)_n = \sum\limits_{k=0}^{n} s(n, k) x^k} $$$

Note: From the definition above, and the fact that $$$x^{(n)} = (-1)^n (-x)_n$$$, it follows that

$$$ x^{(n)} = \sum\limits_{k=0}^n (-1)^{n-k} s(n, k) x^k = \sum\limits_{k=0}^n |s(n, k)| x^k. $$$

Claim: The absolute value $$$|s(n, k)|$$$ equates to $$$c(n, k)$$$, is the number of permutations of length $$$n$$$ with $$$k$$$ disjoint cycles.

Proof

Standard, possibly simpler, approaches here typically involve either of the following:

Proving that $$$|s(n, k)|$$$ and the number of permutations with $$$k$$$ cycles satisfy the same recurrence (see here),
Showing a bijection between ways to expand $$$x^{(n)}$$$ and ways to construct a permutation with a specific cycle structure (see here).

We will use a different approach, which is a bit more involved, but is consistent with the proof for Stirling numbers of the second kind.

Assume that we're coloring the set of $$$n$$$ indistinguishable objects into $$$x$$$ colors. How many ways are there to do it?

On one hand, it is $$$\binom{n+x-1}{n} = \frac{x^{(n)}}{n!}$$$, as can be derived with the help of stars and bars (theorem 2).

On the other hand, let's consider all colorings of $$$n$$$ distinct objects and group them in equivalence classes in such way that each class unites colorings that can be obtained from one another with a permutation. We essentially need to compute the total amount of such classes, as each class uniquely corresponds to a coloring of indistinguishable objects.

Claim: Let $$$I(c)$$$ be the number of permutations that translate a coloring $$$c$$$ into itself. Then the size of $$$c$$$'s class is $$$\frac{n!}{I(c)}$$$.

Proof

From the claim above it follows that we can count the number of equivalence classes by summing up $$$\frac{I(c)}{n!}$$$ over all colorings of distinct objects. In this way, the summands within each individual class will sum up to $$$1$$$, so the whole sum is the number of such classes. On the other hand, the sum $$$I(c)$$$ of "stabilizing" permutations over individual colorings can be substituted with a sum of "fixed points" (i.e. colorings that stay the same) over all permutations.

For a permutation with $$$k$$$ cycles, the number of fixed points is $$$x^k$$$, which corresponds to the number of ways to color all elements on each cycle in the same color. Thus, the number of the colorings expresses as

$$$ \frac{x^{(n)}}{n!} = \frac{1}{n!} \sum\limits_{k=0}^n c(n, k) x^k. $$$

LHS and RHS are the same for any integer $$$x$$$, but since they're both polynomials in $$$x$$$, it must mean that they're identical.

Note: The proof essentially repeats the proof of Burnside's lemma, but adjusted to this particular setting.

Generating functions

Finding Stirling numbers with fixed $$$n$$$ or $$$k$$$ will most certainly involve working with polynomials. As it's usually most convenient to explain polynomial operations in the framework of generating functions, let's find them for Stirling numbers.

Stirling numbers of the second kind

As we already mentioned, $$$S(n, k)$$$ is the number of ways to partition a set of $$$n$$$ distinct objects into $$$k$$$ non-empty sets. The exponential formula tells us that if $$$F(x)$$$ is the exponential generating function for objects of some kind, then $$$\exp F(x)$$$ is the generating function for sets of such objects, also meaning that $$$\exp F(x) - 1$$$ is the generating function for non-empty sets of such objects.

As things enumerated by $$$S(n, k)$$$ can be described as "sets of $$$k$$$ non-empty sets of objects", the exponential generating function should look roughly as $$$e^{e^{x} - 1}$$$, where $$$x$$$ is a formal variable keeping track of "base" objects. However, for Stirling numbers we need to keep track of the base objects (their total amount sums to $$$n$$$), and of the non-empty sets, in which we split them (their amount sums to $$$k$$$).

To account for non-empty sets, we will introduce another variable $$$y$$$, and use the generating function

$$$ F(x, y) = e^{y(e^x-1)} $$$

instead. In this way, when the external exponent is expanded into powers of $$$(e^x-1)$$$, each summand $$$\frac{(e^x-1)^k}{k!}$$$, corresponding to sets of $$$k$$$ non-empty sets will be additionally multiplied by $$$y^k$$$. Thus, we get the expansion into generating function as

$$$ \boxed{\sum\limits_{n=0}^\infty \sum\limits_{k=0}^n S(n, k) \frac{x^n}{n!} y^k = e^{y(e^x-1)}} $$$

Fixed $$$k$$$

Using the power series definition of exponent, we can then expand it as

$$$ e^{y(e^x-1)} = \sum\limits_{k=0}^\infty \frac{y^k (e^x-1)^k}{k!}, $$$

from which we get the exponential generating function with a fixed $$$k$$$:

$$$ \boxed{S(n, k) = \left[\frac{x^n}{n!}\right] \frac{(e^x-1)^k}{k!}} $$$

Fixed $$$n$$$

Library Checker — Stirling Number of the Second Kind. Given $$$N$$$, find $$$S(N, k)$$$ for $$$0 \leq k \leq N$$$.

But what if we want to expand with fixed $$$n$$$? No worries! Let $$$F(y)$$$ be the ordinary generating function of $$$S(n, k)$$$ with fixed $$$n$$$.

From the definition of Stirling numbers, considering $$$t=0, 1, \dots$$$ we get

$$$ t^n = \sum\limits_{k=0}^n S(n, k) \frac{t!}{(t-k)!}. $$$

Right-hand side can be perceived as a convolution of $$$F(y)$$$ and $$$e^y$$$, as the later expands into sum of $$$\frac{y^{t-k}}{(t-k)!}$$$. Thus,

$$$ \sum\limits_{t=0}^\infty \frac{t^n y^t}{t!} = e^y F(y), $$$

from which follows the generating function with a fixed $$$n$$$:

$$$ \boxed{S(n, k) = [y^k] e^{-y} \sum\limits_{t=0}^\infty \frac{t^n y^t}{t!}} $$$

Defined this way, the generating function on the right-hand side is also known as the $$$n$$$-th Touchard polynomial.

Expanded, the expression above transforms into the well-known explicit formula

$$$ \boxed{S(n, k) = \frac{1}{k!}\sum\limits_{t=0}^k (-1)^{k-t} \binom{k}{t} t^n = \sum\limits_{t=0}^k \frac{(-1)^{k-t} t^n}{t!(k-t)!}} $$$

which can also be obtained through the principle of inclusion and exclusion. The formula above can also be used to compute a specific $$$S(n, k)$$$ in $$$O(k \log_k n)$$$ without Fourier transform or other complicated algorithms.

Stirling numbers of the first kind

Generally, a permutation can be represented as a set of cycles. The exponential generating function for cycles is known to be

$$$ \log \frac{1}{1-x} = \sum\limits_{k=1}^\infty \frac{x^k}{k}. $$$

Now, we can mark each cycle by an additional formal variable $$$y$$$ and apply exponential formula. However, we should note that for signed Stirling numbers, we should multiply the coefficient near $$$x^n y^k$$$ with $$$(-1)^{n-k}$$$, which is done by substituting $$$x$$$ and $$$y$$$ with $$$-x$$$ and $$$-y$$$:

$$$ F(x, y) = e^{-y \log \frac{1}{1+x}} = e^{y \log (1+x)} = (1+x)^y. $$$

So, similarly to Stirling numbers of the second kind, we get the expansion

$$$ \boxed{\sum\limits_{n=0}^\infty \sum\limits_{k=0}^n s(n, k) \frac{x^n}{n!} y^k = (1+x)^y } $$$

Unlike generating functions for the Stirling numbers of the second kind, this one can be checked in a very straightforward way:

$$$ (1+x)^y = \sum\limits_{n=0}^\infty \binom{y}{n} x^n = \sum\limits_{n=0}^\infty \frac{x^n}{n!}(y)_n = \sum\limits_{n=0}^\infty \frac{x^n}{n!} \sum\limits_{k=0}^n s(n, k) y^k. $$$

Fixed $$$k$$$

Library Checker — Stirling Number of the First Kind (Fixed K). Given $$$N$$$ and $$$K$$$, find $$$s(n, K)$$$ for $$$K \leq n \leq N$$$.

One obvious way to find the generating function with fixed $$$k$$$ is to expand

$$$ e^{y \log(1+x)} = \sum\limits_{k=0}^\infty \frac{\log(1+x)^k}{k!}y^k, $$$

so we get the exponential generating function with a fixed $$$k$$$:

$$$ \boxed{s(n, k) = \left[\frac{x^n}{n!}\right] \frac{\log(1+x)^k}{k!}} $$$

Fixed $$$n$$$

Library Checker — Stirling Number of the First Kind. Given $$$N$$$, find $$$s(N, k)$$$ for $$$0 \leq k \leq N$$$.

Sasha and the Swaps II. Given $$$n$$$, find the number of distinct permutations obtainable with exactly $$$k$$$ swaps for each $$$k$$$ from $$$1$$$ to $$$n-1$$$.

For a fixed $$$n$$$, we already know that the generating function would be

$$$ (y)_n = y(y-1)\dots(y-n+1). $$$

Computing it as is with divide and conquer approach, we would get $$$O(n \log^2 n)$$$. Can we do better? Sure thing! We can represent it as

$$$ (y)_{2n} = (y)_{n} (y-n)_{n}, $$$

therefore we can first compute $$$(y)_n$$$, then do a Taylor shift to find $$$(y-n)_n$$$ and multiply them in $$$O(n \log n)$$$. The overall time is

$$$ T(n) = T\left(\frac{n}{2}\right) + O(n \log n) = O(n \log n). $$$

	Rev.	Язык	Кто	Когда	Δ	Комментарий
	en2		adamant	2023-07-05 19:28:54	145	Tiny change: ' transform.\n\n#### ' -> ' transform or other complicated algorithms.\n\n#### '
	en1		adamant	2023-07-05 18:48:09	12953	Initial revision (published)

Definitions

Generating functions

Stirling numbers of the second kind

Fixed $$$k$$$

Fixed $$$n$$$

Stirling numbers of the first kind

Fixed $$$k$$$

Fixed $$$n$$$

История