hdu 2643
/*
?第二類Stirling數(shù)是把包含n個元素的集合劃分為正好k個非空子集的方法的數(shù)目。
?遞推公式為：
?S(n,k) = 0(n<k||k=0),
?S(n,n) = S(n,1) = 1,
?S(n,k) = S(n-1,k-1) + kS(n-1,k).
?*/
#include<stdio.h>
#define LL long long
#define nmax 101
#define nnum 20090126LL
LL num[nmax][nmax], fac[nmax];
void init() {
int i, j;
for (i = 1, fac[0] = 1; i < nmax; i++) {
fac[i] = fac[i - 1] * i % nnum;
}
for (i = 1; i < nmax; i++) {
num[i][1] = 1;
num[i][0] = 0;
}
for (i = 2; i < nmax; i++) {
for (j = 1; j < nmax; j++) {
if (i == j) {
num[i][i] = 1;
} else {
num[i][j] = (num[i - 1][j - 1] + num[i - 1][j] * j) % nnum;
}
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.data", "r", stdin);
#endif
init();
int T, N, i;
LL res;
while (scanf("%d", &T) != EOF) {
while (T--) {
scanf("%d", &N);
for (i = 1, res = 0; i <= N; i++) {
res += num[N][i] * fac[i];
res %= nnum;
}
printf("%I64d\n", res);
}
}
return 0;
}
?
hdu 2512
#include<stdio.h>
#define nmax 2001
#define nnum 1000
int num[nmax][nmax];
void init() {
int i, j;
for (i = 1; i < nmax; i++) {
num[i][0] = 0, num[i][1] = 1;
}
for (i = 2; i < nmax; i++) {
for (j = 1; j < nmax; j++) {
if (i == j) {
num[i][i] = 1;
continue;
}
num[i][j] = (num[i - 1][j - 1] + num[i - 1][j] * j) % nnum;
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.data", "r", stdin);
#endif
int n, x, i, res;
init();
while (scanf("%d", &n) != EOF) {
while (n--) {
scanf("%d", &x);
for (i = 1, res = 0; i <= x; i++) {
res += num[x][i];
res %= nnum;
}
printf("%d\n", res);
}
}
return 0;
}
Bell數(shù)，又稱為貝爾數(shù)。
是以埃里克·坦普爾·貝爾(Eric Temple Bell)為名的。
B(n)是包含n個元素的集合的劃分方法的數(shù)目。
B(0) = 1, B(1) = 1, B(2) = 2, B(3) = 5,
B(4) = 15, B(5) = 52, B(6) = 203,...
遞推公式為，
B(0) = 1,
B(n+1) = Sum(0,n) C(n,k)B(k). n = 1,2,...
其中，Sum(0,n)表示對k從0到n求和，C(n,k) = n!/[k!(n-k)!]
-------------------------
Stirling數(shù)，又稱為斯特靈數(shù)。
在組合數(shù)學(xué)，Stirling數(shù)可指兩類數(shù)，都是由18世紀數(shù)學(xué)家James Stirling提出的。
第一類Stirling數(shù)是有正負的，其絕對值是包含n個元素的集合分作k個環(huán)排列的方法數(shù)目。
遞推公式為，
S(n,0) = 0, S(1,1) = 1.
S(n+1,k) = S(n,k-1) + nS(n,k)。
第二類Stirling數(shù)是把包含n個元素的集合劃分為正好k個非空子集的方法的數(shù)目。
遞推公式為，
S(n,n) = S(n,1) = 1,
S(n,k) = S(n-1,k-1) + kS(n-1,k).
將n個有區(qū)別的球的球放入k個無標(biāo)號的盒子中( n>=k>=1，且盒子不允許為空)的方案數(shù)就是stirling數(shù).(即含 n 個元素的集合劃分為 k 個集合的情況數(shù))
遞推公式:
S(n,k) = 0 (k > n)
S(n,1) = 1 (k = 1)
s(n,k)=1 (n=k)
S(n,k) = S(n-1,k-1)+k*S(n-1,k) (n >= k >= 2)
分析：設(shè)有n個不同的球，分別用b1,b2,...,bn表示。從中取出一個球bn，bn的放法有以下兩種：
1.bn獨占一個盒子，那么剩下的球只能放在k-1個盒子里，方案數(shù)為S（n-1,k-1);
2.bn與別的球共占一個盒子，那么可以將b1,b2,...,bn-1這n-1個球放入k個盒子里，然后將bn放入其中一個盒子中，方案數(shù)為k*S(n-1,m).
-------------
bell數(shù)和stirling數(shù)的關(guān)系為，
每個貝爾數(shù)都是"第二類Stirling數(shù)"的和。
B(n) = Sum(1,n) S(n,k).
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
