杨辉三角与组合数

相信大部分OIer已经对杨辉三角很熟悉了，我第一次做杨辉三角的时候是刚学完for循环，有一道题是打印杨辉三角的，那时起，我就对这个几何图形的构造方式充满了兴趣。最近，在老师的引导下，我学习了有关杨辉三角的一个小秘密。本文将简单介绍杨辉三角与组合数之间的联系。

杨辉三角

百度百科

如果将 $(a+b)^n$ ( $n$ 为非负整数)的每一项按字母 $a$ 的次数由小到大排列，就可以得到下面的等式：
$(a+b)^0=1$ ，它只有一项，系数为 $1$ ；
$(a+b)^1=a+b$ ，它有两项，系数分别是 $1$ ， $1$ ；
$(a+b)^2=a^2+2ab+b^2$ ，它有三项，系数分别是 $1$ ， $2$ ， $1$ ；
$(a+b)^3=a^3+3a^2b+3ab^2+b^3$ ，它有三项，系数分别是 $1$ ， $3$ ， $3$ ， $1$ ；
……
观察右表，我们发现每一行的首末都是1，并且下一行的数比上一行多1个，中间各数都写在上一行两数中间，且等于它们的和，按照这个规律可以继续将这个表写下去：

图片来源于网络，文段选自《北师大版义务教育教科书·数学》七年级下册第25页

杨辉三角在教科书里，最初是被用来探究 $(a+b)^n$ 的展开问题，通过发掘 $(a+b)^0$ ， $(a+b)^1$ ， $(a+b)^2$ ， $(a+b)^3$ 的展开式，寻找到了展开式项数规律与各项系数的规律，将这两个规律进行有序排列，得到了杨辉三角。

组合数

百度百科
组合数是指从 $n$ 个元素中选出 $m$ 个元素的所有组合个数，在高中数学作为选修课程，在信息学竞赛中作为必修课程，不仅出现在NOIP初赛，还有可能隐含在上机测试的题目中。
通用计算公式： $C^{m}_{n}=\frac{n!}{m!(n-m)!},C^{0}_{n}=1$
如果在求多个组合数的问题情况下，用程序实现组合数计算公式的时间复杂度会大大增加，下面通过杨辉三角与组合数的联系，使这时间复杂度降低。

二者联系

解决问题：用动态规划求从 $n$ 个元素中选出 $m$ 个元素的所有组合个数

设 $f[i][j]$ 为已在 $i$ 个元素中抽取了 $j$ 个元素，对于上一步描述，有可能是：

这一步没有抽取元素，之前已经抽了 $j$ 个元素： $f[i-1][j]$
这一步抽取了一个元素，之前已经抽了 $j-1$ 个元素： $f[i-1][j-1]$

将这两种情况加起来便是 $f[i][j]$ 的结果，由此得出式子: $f[i][j]=f[i-1][j]+f[i-1][j-1]$

边界条件：

$f[0][0]=1$
$f[i][i]=1$

代码

#include<iostream>

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<i;j++)
			f[i][j]=f[i-1][j]+f[i-1][j-1];
	cout<<f[n][m];
	return 0;
}

至此，我们若将整个 $f$ 数组按矩阵的格式输出，且去掉矩阵中多余的0：

for(int i=0;i<=5;i++)
{
	for(int j=0;j<=5;j++)
		if(f[i][j]!=0)
			cout<<f[i][j]<<' ';
	cout<<endl;
}

我们会得到以下结果：
杨辉三角与组合数

程序输出了杨辉三角！！！并且杨辉三角中第 $i$ 行第 $j$ 列的数字正是 $C^{j}_{i}$ 的结果！！！

小结

通过动态规划这座桥梁，我们可以将组合数与杨辉三角联系起来，从今以后凭借着 $f[i][j]=f[i-1][j]+f[i-1][j-1]$ 这个原理，我们在信息学竞赛的道路上，又多了一大解题利器。

杨辉三角与组合数