斯特林数和自然数前m项n次方的求和公式
科技节口号-
斯特林数和自然数前
m
项
n
次方的求和公式
将
n
个元素，分成
k
个非空子集，不同的分配方法种数
，称为
斯特林数
（
Stirling
Number
）
，记为
S
(
n
,
k
)
，
1
k
n
。<
/p>
例如，将
4
个
物体
a
,
b
,
c
,
d
分成<
/p>
3
个非空子集，有下列
6
种方法：
{(
a
,
b
),
(
c
),
(
d
)}
，
{(
a
,
c
),
(
< br>b
),
(
d
)}
，
{(
a
,
d
),
(
b
),
(
c
)}
，
{(
b
,
c
),
(
a
),
(
d<
/p>
)}
，
{(
b<
/p>
,
d
),
(
a
),
(
c
)}
，
{(
c
,
d
),
(
a
),
(
b
)}
。
所以，
S
(
4
,
3
)
6
< br>
。
斯特林
数
S
(
n
,<
/p>
k
)
的值列表如下：
n
1
2
3
4
5
6
7
8
9
k
1
1
1
1
1
1
1
1
1
1
2
1
3
7
15
31
63
127
255
3
1
6
25
90
301
966
3025
4
1
10
65
350
1701
7770
5
1
15
140
1050
6951
6
1
21
266
2646
7
1
28
462
8
1
36
2
9
1
n<
/p>
1
容易看出，有
S
(
n
,
1
)
S
(
n
,
n
)
1
，
S
(
n
,
< br>2
)
2
1
，
S
(
n
,
n
1
)
C
n
n
(
n
1
)
< br>
。
2
定理
1
当
2
k
n
时，有
S
(
n
1
,
k
)
S
(
n
,
k
1
)
< br>kS
(
n
,
k
)
。
证
把
n
1
个元素分成
k
个非空子集，有
S
< br>(
n
1
,
k
)
种不同分法。
把
n
1
个元素分成
k
个非空子集，也可
以这样考虑：或者将第
n
1
个元素单独作为
1
个
子
集，其余
n
个元素分成
k
1
个非空子集，这种情况下有
S
(
n
,
k
1
)
种不
同做法；或者先将
前
n
个元素分成
k
个非空子集，
有
S
(
n
,
k<
/p>
)
种分法，
再将第
n
1
个元素插入这
k
个子集，
有
k
种
选择，这种情况下有
k
S
(
n
,
k
)
种不同做法。所以共有
S
(
n
,
k
1
)
kS
(
n
,
k
)
种分法。
两种考虑，结果应该是一样的，因此有
S
(
n
1
,
k
)
S
(
n
,
k
1
)
kS
(
n
,
k
)
。
如果规定当
k
1
或
k
n
时，
S<
/p>
(
n
,
k
)
0
，
则公式
S
(
n
1
,
k
)
S
(
n
,
k
1
)
kS
(
n
,
k
)
对
任何正整数
n
和任何整数
k
都成立。
1
定理
2
对任何整数
n
1
和
k
0
，有
1
k<
/p>
1
S
(
n
,
k
)
(
1
)
i
C
k
i
(
k
i
)
n
。
k
!
i
0
证
用数学归纳法证明。
（
1
）当
n
1
时，
1<
/p>
0
0
1
k
1
1
k
1
(
1
)
C
0
1
k
1
i
i
i<
/p>
i
S
(
1
,
k
)
，
(
1
)
C
k
(
k
i
)
(
<
/p>
1
)
C
k
1
0
!
k
!
i
0
(
k
1
)
!
i
<
/p>
0
0
k
1
公式成立。<
/p>
（
2
）设已知
对某个正整数
n
，公式成立，下面看
n
1
时的情形：
S
(
n
1
,
k
)
S
(
n
,
k
1
)
kS
(
n
,
k
)
k
k
1
1
k
2
i
i<
/p>
i
n
(
k
i
)
n
(
1
)
C
k
1
(
k
1
i
)<
/p>
(
1
)
i
C
k
(
k
1
)!
i
< br>
0
k
!
i
0
1
k
1
1
k
1
i
i
1
n
(
1
< br>)
C
k
1
(
k
i
)
(
1
)
i
C
k
i
(
k
i
)
n
< br>
(
k
1
)
!
i
1
(
k
1
)
!
i
0
1
k
1
< br>1
k
1
i
i
n
(
1
)
C
k
1
(
k
i
)
(
< br>1
)
i
C
k
i
(
k
i
)
n
1
，
(
k
1
)!
i
0
k
!
i
0
可见
n
1
时公式也成立。
（
< br>3
）所以，对任何正整数
n
，公式都成立。
例如，有
2
n
2
1<
/p>
n
S
(
n
,
2
)
2
n
1
1
，
2
!
3
n
3
2
n
3
1
n
< br>3
n
1
2
2
n
1
1
,
S
(
n
,
3
)
3
!
2
!
4
n
4
3
n
6
2<
/p>
n
4
1
n
4
n
1
3
3
n
1
3
2
n
1
<
/p>
1
,
S
(
n
,
4
)
4
!
3
!
5
< br>n
5
4
n
10
3
n
10
2
n
5
1
n
5
n
1
4
4
< br>n
1
6
3
n
1
4
2
n
1
1
。
S
(
n
,
5
)
5
!
4
!
定理
3
当
1
k
n
m
时，有
k
1
2
n
m
P
m
S
(
n
,
k
)
P
m
< br>S
(
n
,
1
)
P
m
S
(
n
,
2
)
P
m
S
(
n
,
n
< br>)
。
n
n
k
1
2
证
将
n
个元素
分配到
m
个不同的格子中，每个格子可以有多个元素，也可以没
有元素，共
有
m
种不同分配方法。
将
n
个元素分配
到
m
个不同的格子中，
也可以这样考虑
：
先将
n
个元素分成
< br>k
个非空子集，
有
S
(
n
,
k
)
种不同分法，再将这
k
个子
集分配到
m
个格子中，每个格子最多只能放一个子集，
k
k
不同的子集分配在不同的格子中，有
P
m
种不同分法，共有
S
(
n
,
k
)
P
m
种不同
做法。这里
k
可
n
取
1
,
2
,
,
n
中每
一个值，所以有
k
m
S
(
n
,
1
)
P
S
(
n
,<
/p>
2
)
P
S
(
n
,
n
)
P
S
(
n
,
k
)
P
m
。
n
1
m
2
m
n
m
n
k
1
k
< br>1
P
m
1
定理
4
对任何正整数
m
1
，
k
1
，有
P
。
k
1
j
1
m
k
j
证
用数学归纳法证明。
k
1
0<
/p>
当
k
1
时
P
1
（
1
）当
m
1
时，
P
P
1
，定理显然成立。
j
1
1
当
k
1
时
k
1
1
k
j
< br>k
1
（
2
）设已知对某个正整数
m
，定理成立，下面看
m
1
时的情形：
P
j
1
m
1
k
j
P
P
k
j
j
1
m
k
< br>m
1
k
1
k
1
P
m
P
m
m
k
1
k
m
2
k
k
k
< br>
1
P
m
1
P
m
1
P
m
1
2
，
P
m
< br>
1
k
1
k
1
k
1
k
1
可见当
m
1
时，定理也成立。
（
3
）所以，对任何正整数
m
，定理都成立。
定理
5
对任何整数
m
1
和
n
1
，有
1
<
/p>
2
3
m
j
n
n
n
n
n
j
1
m
k
1
n
P<
/p>
m
k
1
k
1
1
S
(
n
,
k
)
(
<
/p>
1
)
i
C
k
i
(
k
i
)
n
1
C
m
1
。
k
1
k
1
k
1
i
0
< br>n
k
1
P
m
1
证
由定理
3
可知
j
S
(
n
,
k
)
P
，由定理
4
可知
P
，所以
k
1
k
1
j
1
n
n
k
j
m
k
j
k
< br>
1
P
m
1
2
3
m
j
S
(
n
,
k
)
P
S
(
n
,
k
)
P
S<
/p>
(
n
,
k
)
1
k
1
j
1
j
1
k
1
k
1
j
<
/p>
1
k
1
n
n
n
n
m
n
m
n
k
j
n
m
k
j
n
k
1
n
1<
/p>
k
1
k
1
k
1
i
i
i
n
P
m
1
(<
/p>
1
)
i
C
k
(
k
i
)
n
C
m
(
1
)
C
k<
/p>
(
k
i
)
1
。
k
1
k
!
i
0
k
1<
/p>
k
1
i
0
n
3