Sequences (3): Stirling numbers of the first kind

# Stirling Number of the First Kind

Stirling numbers of the first kind(Number of Sterling rotations)$\begin{bmatrix}n\\ k\end{bmatrix}$, can also be recorded as $s(n,k)$, indicating that the $n$ Pairwise different elements are divided into $k$ The number of mutually indistinguishable non-empty rotation plans.

A rotation is a circular arrangement arranged end to end. We can write a rotation $[A,B,C,D]$, and we think $[A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]$, that is, two rotations that can be obtained from each other by rotation are equivalent. Note that we do not consider two rotations that can be obtained from each other by flipping to be equivalent, i.e. $[A,B,C,D]\neq[D,C,B,A]$。

# Recursive

$$\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$$

The boundary is $\begin{bmatrix}n\\ 0\end{bmatrix}=[n=0]$。

The proof of this recursion can consider its combinatorial significance.

When we insert a new element, we have two options:

• Place the new element in a separate rotation with a total of $\begin{bmatrix}n-1\\ k-1\end{bmatrix}$ kind of plan;
• Insert this element into any existing rotation, there are $(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$ kind of plan.

According to the principle of addition, the recursive formula can be obtained by adding the two formulas.

# general formula

There is no practical general formula for Stirling numbers of the first kind.

# Calculation of Stirling numbers of the first kind in the same row

Similar to the Stirling number of the second kind, we construct the generating function of the Stirling number of the first kind, namely

$F_n(x)=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i$

According to the recursion formula, it is not difficult to write

$F_n(x)=(n-1)F_{n-1}(x)+xF_{n-1}(x)$

So

$F_n(x)=\prod\limits_{i=0}^{n-1}(x+i)=\dfrac{(x+n-1)!}{(x-1)!}$

This is actually $x$ of $n$ times raised to the factorial power, recorded as $x^{\overline n}$. Naturally, this thing can be violently divided and conquered. $O(n\log^2n)$ It can be found, but it can be obtained by using the related methods of rising powers. $O(n\log n)$ Find out.

# Calculation of Stirling numbers of the first kind in the same column

Following the calculation of the second type of Stirling number, we can use exponential generating functions to solve this problem. Note that since the recursive formula is related to rows, we cannot use the recursive formula to calculate the Stirling number of the first kind in the same column.

Obviously, the exponential generating function of a single rotation is

$F(x)=\sum\limits_{i=1}^n\dfrac{(i-1)!x^i}{i!}=\sum\limits_{i=1}^n\dfrac{x^i}{i}$

its $k$ The power is $\begin{bmatrix}i\\k\end{bmatrix}$ The exponential generating function of$O(n\log n)$ Just calculate.

int main() { scanf("%d%d", &n, &k); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod; ifact[n] = qpow(fact[n], mod - 2); for (int i = n - 1; i >= 0; --i) ifact[i] = (ll)ifact[i + 1] * (i + 1) % mod; poly f(n + 1); for (int i = 1; i <= n; ++i) f[i] = (ll)fact[i - 1] * ifact[i] % mod; f = exp(log(f >> 1) * k) << k, f.resize(n + 1); for (int i = 0; i <= n; ++i) printf("%lld ", (ll)f[i] * fact[i] % mod * ifact[k] % mod); return 0;
}

# Application

# Mutual conversion of rising powers and ordinary powers

We remember rising factorial power $x^{\overline{n}}=\prod_{k=0}^{n-1} (x+k)$。

Then you can use the following identity to convert rising powers into ordinary powers:

$$x^{\overline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} x^k$$

If you convert ordinary powers into ascending powers, you have the following identity:

$$x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} (-1)^{n-k} x^{\overline{k}}$$

# Mutual conversion of descending power and ordinary power

We write down the factorial power $x^{\underline{n}}=\dfrac{x!}{(x-n)!}=\prod_{k=0}^{n-1} (x-k)$。

Then you can use the following identity to convert ordinary powers into descending powers:

$$x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} x^{\underline{k}}$$

If descending powers are converted to ordinary powers, we have the following identity:

$$x^{\underline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} (-1)^{n-k} x^k$$

# The relationship between polynomial descending factorial power representation and polynomial point value representation

Here, the descending factorial power representation of the polynomial is expressed by

$$f(x)=\sum\limits_{i=0}^nb_i{x^{\underline{i}}}$$

represents a polynomial in the form of $n+1$ point

$$(i,a_i),i=0..n$$

to represent a polynomial.

Obviously, descending the factorial power $b$ and pip value $a$ satisfy the following relationship:

$$a_k=\sum\limits_{i=0}^{n}b_ik^{\underline{i}}$$

That is

$$\begin{aligned} a_k&=\sum\limits_{i=0}^{n}\dfrac{b_ik!}{(k-i)!}\\\dfrac{a_k}{k!}&=\sum\limits_{i=0}^kb_i\dfrac{1}{(k-i)!} \end{aligned}$$

This is an equation in convolution form. We can $O(n\log n)$ Complete the mutual conversion between point value and descending factorial power within the time complexity of

# Example link

hdu 5625open in new window

# Question overview

​ There is a key stored in each warehouse (it may be to open this warehouse, or it may be based on the assumption that up to k warehouses can be forcibly opened and the keys inside can be obtained, and it is required that warehouse No. 1 cannot be forcibly opened, then calculate the probability that all warehouses can be opened, and keep 4 decimal places.

# some ideas

​ First consider the problem of n warehouses, how to open k warehouses, get the keys inside, and then open the remaining warehouses. Obviously, this is when the n warehouses form k circular arrangements, and then violently open one from each circular arrangement, get the key, and then the warehouses in this circular arrangement can be opened (at this time, each warehouse places the key of its next warehouse). This corresponds to the first type of Stirling number. But this question has a requirement, it cannot be opened violently1No. warehouse, so1The key to warehouse No. 1 can only be placed in this way. Randomly select a warehouse to place key No. 1 from k arrangements composed of n-1 warehouses. You can first open other warehouses and then obtain the key to warehouse No. 1; but for the case where n-1 warehouses have been arranged into k-1 arrangements, at this time1The number must place its key on itself, but it cannot be opened violently, so n warehouses cannot be opened violently.1No., the requirement to violently open at most k warehouses to obtain keys and then open other warehouses so that they can all be opened, must be subtracted from the calculated first type Stirling number s(n,k)1The case where the number is placed on itself is s(n,k)−s(n−1,k−1).

​ The above calculation is to be able to open and ensure that1The number of possible ways to open a number without being violently opened. The total number of ways to randomly place keys is n!n!, so to calculate the probability, just divide the number of possible ways by the total number. Because the question requires that the number be opened at most k times, it means that using 1, 2,...,k-1 will also be counted as at most k times.

# Note

​ When I was calculating the first type of Stirling numbers, I considered that I could not subtract directly after calculating one term, because the calculation of the recursive formula depends on the first two terms, so I subtracted the previous terms after the complete calculation. I forgot that the latter part of the recursive formula depends on the previous ones. The first few are not changed because they are 0, but once a non-zero value is encountered, the previous results begin to change, and the corresponding subsequent ones also begin to change.

# Code implementation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 30;
ll s[N][N];
ll ans[N][N];
ll f[N]; void calculate(){ s[0][0] = 1; f[0] = 1; // Calculate Stirling numbers of the first kind for (int i = 1; i < N; i++){ for (int j = 0; j <= i; j++){ // Recursive formula for Stirling numbers of the first kind s[i][j] = (i-1) * s[i - 1][j] + s[i-1][j-1]; } f[i] = f[i - 1] * i; } //Cannot be eliminated in this way. The previous changes will affect the results of subsequent eliminations. // for (int i = 1; i < N; i++){ // for (int j = 1; j <= i; j++){ // // Eliminate the situation where 1 cannot be opened // s[i][j] -= s[i-1][j-1]; // } // } for (int i = 0; i < N; i++){ for (int j = 1; j <= i; j++){ ans[i][j] = ans[i][j - 1] + s[i][j] - s[i-1][j-1]; } }
} void print(){ for(int i = 0; i < N; i++){ for(int j = 0; j <= i; j++){ printf("%lld ", s[i][j]); } printf("\n"); }
}
int main() { calculate(); // print(); int t; scanf("%d", &t); while (t--){ int n, m; scanf("%d%d", &n, &m); printf("%.4f\n", 1.0 * ans[n][m] / f[n]); } return 0;
}