poj 3088 斯特林数-白红宇

poj 3088 斯特林数

阅读量：5142 次

发布时间：2019-06-13

本文共 1782 字，大约阅读时间需要 5 分钟。

第一类Stirling数是有正负的，其绝对值是 $n$ 个元素的项目分作 $k$ 个环的方法数目。常用的表示方法有 $s(n,k) , \left[\begin{matrix} n \\ k \end{matrix}\right]$ 。

换个较生活化的说法，就是有 $n$ 个人分成 $k$ 组，每组内再按特定顺序围圈的分组方法的数目。例如 $s(4,2)=11$ ：

{A,B},{C,D}

{A,C},{B,D}

{A,D},{B,C}

{A},{B,C,D}

{A},{B,D,C}

{B},{A,C,D}

{B},{A,D,C}

{C},{A,B,D}

{C},{A,D,B}

{D},{A,B,C}

{D},{A,C,B}

给定 $s(n,0)=0,s(1,1)=1$ ，有关系 $s(n,k)=s(n-1,k-1) + (n-1) s(n-1,k)$

======================================================================================================================================================

第二类Stirling数是 $n$ 个元素的集定义k个的方法数目。常用的表示方法有 $S(n,k) , S_n^{(k)} , \left\{\begin{matrix} n \\ k \end{matrix}\right\}$ 。

换个较生活化的说法，就是有 $n$ 个人分成 $k$ 组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只能所有人在同一组，因此 $S(4,1)=1$ ；若所有人分成4组，只能每人独立一组，因此 $S(4,4)=1$ ；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：

{A,B},{C,D}

{A,C},{B,D}

{A,D},{B,C}

{A},{B,C,D}

{B},{A,C,D}

{C},{A,B,D}

{D},{A,B,C}

因此 $S(4,2)=7$ 。

给定 $S(n,n)=S(n,1)=1$ ，有递归关系 $S(n,k) = S(n-1,k-1) + k S(n-1,k)$

======================================================================================================================================================

poj 3088 题意：给一串数字1、2、...、B，求这些数字分组的情况数,{(1)，(2)} {(2)，(1)} 算两种不同的情况

解法：赤裸裸的第二类斯特林数

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;long long c[15][15] , s[15][15] ,f[15];void dabiao(){    c[0][0]=1,f[1]=f[0]=1,s[1][1]=1;    for(int i=1; i<=11;i++){        f[i]=f[i-1]*i;        c[i][0]=1 ,c[i][1] = i;        s[i][1]=1,s[i][i]=1,s[i][0]=0;        for(int j=2;j<=11;j++){            c[i][j] = c[i-1][j-1]+c[i-1][j] ;            s[i][j]=s[i-1][j-1]+j*s[i-1][j] ;        }    }}int main(){    int t;    scanf("%d",&t);    dabiao();    int ncase =1;    while(t--){        int n;        long long ans= 0;        scanf("%d", &n) ;        for(int i=1;i<=n;i++){            for(int j=1;j<=i;j++){                ans+=c[n][i]*s[i][j]*f[j] ;            }        }        printf("%d %d %lld\n",ncase++,n,ans) ;    }    return 0;}

转载于:https://www.cnblogs.com/Scale-the-heights/p/4712351.html

你可能感兴趣的文章