Java教程

斯特林数和分拆数

本文主要是介绍斯特林数和分拆数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

上升幂与下降幂

  • 上升幂:\(x^{\overline{n}}=\prod_{k=0}^{n-1}(x+k)=x(x+1)(x+2)...(x+n-1)\)
  • 下降幂:\(x^{\underline{n}}=\frac{x!}{(x-n)!}=\prod_{k=0}^{n-1}(x-k)\)

第一类斯特林数(无符号)

  • 定义:第一类斯特林数(斯特林轮换数)\(n\brack k\),也可记做\(s(n,k)\) ,表示将\(n\)个两两不同的元素,划分为\(k\)个互不区分的非空轮换的方案数。一个轮换就是一个首尾相接的环形排列。我们可以写出一个轮换\([A,B,C,D]\) ,并且我们认为\([A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]\) ,即,两个可以通过旋转而互相得到的轮换是等价的。注意,我们不认为两个可以通过翻转而相互得到的轮换等价,即\([A,B,C,D]\neq [D,C,B,A]\) 。(另一种理解:将 \(n\) 个元素,划分为 \(k\) 个圆排列的方案数)

  • 递推式:\({n\brack k}={n-1\brack k-1}+(n-1){n-1 \brack k}\)。边界\({n\brack 0}=[n=0]\)

    组合意义:将该新元素置于一个单独的轮换中,共有\({n-1\brack k-1}\)中方案;将该元素插入到任何一个现有的轮换中,共有\((n-1){n-1 \brack k}\)种方案。

  • 性质

    \(\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)!\)

生成函数(同行) 上升幂:\(F_n(x)=x^{\overline{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;
}

生成函数(同列):\(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\)

第二类斯特林数(无符号)

  • 定义:第二类斯特林数(斯特林子集数)\(n \brace k\),也可记做\(S(n,k)\) ,表示将\(n\)个两两不同的元素,划分为\(k\) 个互不区分的非空子集的方案数

  • 递推式:\({n\brace k}={n-1\brace k-1}+k{n-1\brace k}\)

    组合意义:插入一个新元素时,可以将这个元素单独放入一个子集,也可以将这个元素放入现有的一个非空子集

  • 通项公式:\({n\brace m}=\sum_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!}\)

  • 性质

    \(\sum_{k=0}^n{n\brace k}=B_n\),\(B_n\)为贝尔数

    \(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}}\),这个可以用来求自然数数幂和:\(\sum_{i=1}^n i^k=\sum_{i=1}^n\sum_{j=0}^k{k\brace j}\times j!\times \binom{i}{j}=\sum_{j=0}^k{k\brace j}\times j!\sum_{i=1}^n\binom{i}{j}=\sum_{j=0}^k{k\brace j}\times j!\times \binom{n+1}{j+1}=\sum_{j=0}^k{k\brace j}\frac{(n+1)^{\underline{j+1}}}{(j+1)!}\)

  • 同一行第二类斯特林数通项公式计算\(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;
}

分拆数

  • 定义:将正整数\(n\)进行整数拆分的方案数

  • 求法:

    • 完全背包,把数字\(1-n\)看做价值为\(1\),容量为\(i\)的物品,进行完全背包
    • 五边形定理
      #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++) /*递推式系数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; /*五边形数为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++) /*有可能为负数,式中加1000007*/
          {
          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]);
      }
      }
      
  • \(k\)个部分的分拆,记作\(p(n,k)\)

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

例题

2021CCPC Guangzhou A

参考:OIWiki

这篇关于斯特林数和分拆数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!