杨辉三角与组合数
相信大部分OIer已经对杨辉三角很熟悉了，我第一次做杨辉三角的时候是刚学完for循环，有一道题是打印杨辉三角的，那时起，我就对这个几何图形的构造方式充满了兴趣。最近，在老师的引导下，我学习了有关杨辉三角的一个小秘密。本文将简单介绍杨辉三角与组合数之间的联系。
杨辉三角
百度百科
如果将
(
a
+
b
)
n
(a+b)^n
(a+b)n(
n
n
n为非负整数)的每一项按字母
a
a
a的次数由小到大排列，就可以得到下面的等式：
(
a
+
b
)
0
=
1
(a+b)^0=1
(a+b)0=1，它只有一项，系数为
1
1
1；
(
a
+
b
)
1
=
a
+
b
(a+b)^1=a+b
(a+b)1=a+b，它有两项，系数分别是
1
1
1，
1
1
1；
(
a
+
b
)
2
=
a
2
+
2
a
b
+
b
2
(a+b)^2=a^2+2ab+b^2
(a+b)2=a2+2ab+b2，它有三项，系数分别是
1
1
1，
2
2
2，
1
1
1；
(
a
+
b
)
3
=
a
3
+
3
a
2
b
+
3
a
b
2
+
b
3
(a+b)^3=a^3+3a^2b+3ab^2+b^3
(a+b)3=a3+3a2b+3ab2+b3，它有三项，系数分别是
1
1
1，
3
3
3，
3
3
3，
1
1
1； …… 观察右表，我们发现每一行的首末都是1，并且下一行的数比上一行多1个，中间各数都写在上一行两数中间，且等于它们的和，按照这个规律可以继续将这个表写下去： 图片来源于网络，文段选自《北师大版义务教育教科书·数学》七年级下册第25页
杨辉三角在教科书里，最初是被用来探究
(
a
+
b
)
n
(a+b)^n
(a+b)n的展开问题，通过发掘
(
a
+
b
)
0
(a+b)^0
(a+b)0，
(
a
+
b
)
1
(a+b)^1
(a+b)1，
(
a
+
b
)
2
(a+b)^2
(a+b)2，
(
a
+
b
)
3
(a+b)^3
(a+b)3的展开式，寻找到了展开式项数规律与各项系数的规律，将这两个规律进行有序排列，得到了杨辉三角。
组合数
百度百科 组合数是指从
n
n
n个元素中选出
m
m
m个元素的所有组合个数，在高中数学作为选修课程，在信息学竞赛中作为必修课程，不仅出现在NOIP初赛，还有可能隐含在上机测试的题目中。 通用计算公式：
C
n
m
=
n
!
m
!
(
n
−
m
)
!
,
C
n
0
=
1
C^{m}_{n}=\frac{n!}{m!(n-m)!},C^{0}_{n}=1
Cnm=m!(n−m)!n!,Cn0=1 如果在求多个组合数的问题情况下，用程序实现组合数计算公式的时间复杂度会大大增加，下面通过杨辉三角与组合数的联系，使这时间复杂度降低。
二者联系
解决问题：用动态规划求从
n
n
n个元素中选出
m
m
m个元素的所有组合个数
设
f
[
i
]
[
j
]
f[i][j]
f[i][j]为已在
i
i
i个元素中抽取了
j
j
j个元素，对于上一步描述，有可能是：
这一步没有抽取元素，之前已经抽了
j
j
j个元素：
f
[
i
−
1
]
[
j
]
f[i-1][j]
f[i−1][j]这一步抽取了一个元素，之前已经抽了
j
−
1
j-1
j−1个元素：
f
[
i
−
1
]
[
j
−
1
]
f[i-1][j-1]
f[i−1][j−1]
将这两种情况加起来便是
f
[
i
]
[
j
]
f[i][j]
f[i][j]的结果，由此得出式子:
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
+
f
[
i
−
1
]
[
j
−
1
]
f[i][j]=f[i-1][j]+f[i-1][j-1]
f[i][j]=f[i−1][j]+f[i−1][j−1]
边界条件：
f
[
0
]
[
0
]
=
1
f[0][0]=1
f[0][0]=1
f
[
i
]
[
i
]
=
1
f[i][i]=1
f[i][i]=1
代码
#include
using namespace std;
int n,m;
int f[1005][1005];
int main()
{
cin>>n>>m;
for(int i=0;i<=n;i++)
{
f[i][i]=1;
f[i][0]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j f[i][j]=f[i-1][j]+f[i-1][j-1]; cout< return 0; } 至此，我们若将整个 f f f数组按矩阵的格式输出，且去掉矩阵中多余的0： for(int i=0;i<=5;i++) { for(int j=0;j<=5;j++) if(f[i][j]!=0) cout< cout< } 我们会得到以下结果： 程序输出了杨辉三角！！！并且杨辉三角中第 i i i行第 j j j列的数字正是 C i j C^{j}_{i} Cij的结果！！！ 小结 通过动态规划这座桥梁，我们可以将组合数与杨辉三角联系起来，从今以后凭借着 f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j − 1 ] f[i][j]=f[i-1][j]+f[i-1][j-1] f[i][j]=f[i−1][j]+f[i−1][j−1]这个原理，我们在信息学竞赛的道路上，又多了一大解题利器。