Stirling numbers with fixed n and k

Правка en2, от adamant, 2023-07-05 19:28:54

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

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). $$$
Теги tutorial, stirling numbers

История

 
 
 
 
Правки
 
 
  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)