Stirling number and partition number

Rising power and falling power

Rising power: \ (x ^ {\ outline {n}} = \ prod {k = 0} ^ {n-1} (x + k) = x (x + 1) (x + 2) (x+n-1)\)
Descending power: \ (x^{\underline{n}}=\frac{x!}{(x-n)!}=\prod_{k=0}^{n-1}(x-k)\)

Stirling number of the first kind (unsigned)

Definition: the first type of Stirling number (Stirling rotation number) \ (n\brack k \), which can also be recorded as \ (s(n,k) \), represents the number of schemes that divide \ (n \) two different elements into \ (k \) non empty rotation that are not distinguished from each other. A rotation is a circular arrangement connected end to end. We can write a rotation \ ([A,B,C,D] \), and we think that \ ([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 think that two rotation equivalents that can be obtained from each other by flipping, that is \ ([A,B,C,D]\neq [D,C,B,A] \). (another understanding: divide the \ (n \) elements into the number of schemes arranged in \ (k \) circles)
Recursive formula: \ ({n\brack k}={n-1\brack k-1}+(n-1){n-1 \brack k} \). Boundary \ ({n \ brace 0} = [n = 0] \)

Combination meaning: put the new element in a separate rotation, with a total of schemes in \ ({n-1 \ brace k-1} \); There are \ ((n-1){n-1 \brack k} \) schemes for inserting this element into any existing rotation.
nature

\(\sum_{k=0}^n{n\brack k}=n!\)

\({n\brack n-1}=\binom{n}{2}\)

\({n\brack 2}=(n-1)!\sum_{i=1}^{n-1}\frac{1}{i}\)

\({n\brack 1}=(n-1)!\)

Generating function (peer) rising power: \ (f_n (x) = x ^ {\ outline {n}} = \ prod_ {i=0}^{n-1}(x+i)=\frac{(x+n-1)!} {(x-1)!}= \prod_ {i=0}^n{n\brack i}x^i\)
\(O(nlogn)\)

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("gen.in","r",stdin);
    Poly::init(19);
    auto CDQ=[&](auto self,int l,int r)->Poly::poly{
        if(l==r) return Poly::poly({l,1});
        int mid=l+r>>1;
        return Poly::poly_mul(self(self,l,mid),self(self,mid+1,r));
    };
    int n;
    cin>>n;
    Poly::poly F=CDQ(CDQ,0,n-1);
    for(int i=0;i<=n;i++) cout<<F[i]<<" ";
    return 0;
}

Generating function (same column): \ (F(x)=\sum_{i=1}^n\frac{(i-1)!x^i}{i!}=\sum_{i=1}^n\frac{x^i}{i}=\sum_{i=1}^n{i \brack k}x^i\)

Stirling number of the second kind (unsigned)

Definition: the second kind of Stirling number (Stirling subset number) \ (n \brace k \), which can also be recorded as \ (S(n,k) \), represents the number of schemes that divide \ (n \) two different elements into \ (k \) non empty subsets that are indistinguishable from each other
Recursive formula: \ ({n\brace k}={n-1\brace k-1}+k{n-1\brace k} \)

Composite meaning: when inserting a new element, you can put the element into a separate subset, or you can put the element into an existing non empty subset
General term formula: \ ({n\brace m}=\sum\u{i=0}^m\frac{(-1) ^ {m-i}i^n}{i! (M-I)!}\)
nature

\(\ sum {k = 0} ^ n {n \ brace K} = B_n \), \ (B_n \) is the bell number

\(n^k=\sum_{i=1}^k{k\brace i}\times i!\times \binom{n}{i}=\sum_{i=1}^k{k\brace i}\times n^{\underline{i}}\)， This can be used to seek the natural number and power of natural number, and it can be used to seek the natural number and power of the natural number, which can be used to seek the natural number and the natural number of natural number and the natural number of the natural number. The natural number of the natural number and the natural number of the natural number of the natural number and the natural number of the natural number and the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number and the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of the natural number of{K \ brace J} \ frac {(n + 1) ^ {\ underline {j + 1} {(j + 1)!} \)
Calculation of the general term formula of the second kind of Stirling number in the same line \ (O(nlogn) \)

int main() {
    scanf("%d", &n);
    poly f(n + 1), g(n + 1);
    for (int i = 0; i <= n; ++i)
        g[i] = (i & 1 ? mod - 1ll : 1ll) * infac[i] % mod,
        f[i] = 1ll * qpow(i, n) * infac[i] % mod;
    poly F=poly_mul(f,g);
    F.resize(n + 1);
    for (int i = 0; i <= n; ++i)
        printf("%d ", F[i]);
    return 0;
}

partition

Definition: the number of schemes that split positive integers \ (n \) into integers

Solution:

Complete backpack: take the number \ (1-n \) as an item with a value of \ (1 \) and a capacity of \ (i \) to complete backpack

Pentagon theorem

#include <stdio.h>

long long a[100010];
long long p[50005];

int main() {
p[0] = 1;
p[1] = 1;
p[2] = 2;
int i;
for (i = 1; i < 50005;i++) /*Recursive coefficients 1,2,5,7,12,15,22,26 i*(3*i-1)/2,i*(3*i+1)/2*/
{
    a[2 * i] = i * (i * 3 - 1) / 2; /*The number of pentagons is 1,5,12,22 i*(3*i-1)/2*/
    a[2 * i + 1] = i * (i * 3 + 1) / 2;
}
for (  i = 3; i < 50005; i++) /*p[n]=p[n-1]+p[n-2]-p[n-5]-p[n-7]+p[12]+p[15]-...+p[n-i*[3i-1]/2]+p[n-i*[3i+1]/2]*/
{
    p[i] = 0;
    int j;
    for (j = 2; a[j] <= i; j++) /*If 1000007 is added, it may be negative*/
    {
    if (j & 2) {
        p[i] = (p[i] + p[i - a[j]] + 1000007) % 1000007;
    } else {
        p[i] = (p[i] - p[i - a[j]] + 1000007) % 1000007;
    }
    }
}
int n;
while (~scanf("%d", &n)) {
    printf("%lld\n", p[n]);
}
}

\The division of (k \) parts is recorded as \ (p(n,k) \)

\(p(n,k)=p(n-1,k-1)+p(n-k,k)\)

Examples

2021CCPC Guangzhou A

reference resources: OIWiki

Posted by lkalik on Sat, 16 Apr 2022 02:16:09 +0930

Programs Wiki