数论 - 组合数(杨辉三角组合数)
我们都知道一个结论:组合数当n,m都很小的时候可以利用杨辉三角直接求
那么为什么呢?
组合数:
我们高中学到的组合数:
C
n
m
C^m_n
Cnm:从n个物品里面找出m个物品所有的方案*
C
n
m
=
n
!
m
!
(
n
−
m
)
!
C^m_n=\frac{n!}{m!(n-m)!}
Cnm=m!(n−m)!n!
杨辉三角:
杨辉三角,是二项式系数在三角形中的一种几何排列,中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲,帕斯卡(1623----1662)在1654年发现这一规律,所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年,比贾宪迟600年----百度
像这样
这样
那么这东西为什么会和组合数有关系呢?
当我用DP的思想:
C
n
m
=
从
n
个
物
品
中
选
择
m
个
物
品
有
多
少
种
选
法
C^m_n=从n个物品中选择m个物品有多少种选法
Cnm=从n个物品中选择m个物品有多少种选法
对应的动态转移:
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
−
1
]
+
f
[
i
−
1
]
[
j
]
f[i][j]=f[i - 1][j - 1] + f[i - 1][j]
f[i][j]=f[i−1][j−1]+f[i−1][j]
#include <iostream>
using namespace std;
int f[101][101];
int main()
{
f[0][0] = 1;
for(int i = 1; i <= 6; i ++)
for(int j = 0; j < i; j ++)
f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
for(int i = 1; i <= 6; i ++)
{
for(int j = 0; j < i; j ++)
cout << f[i][j] << " ";
cout << endl;
}
return 0;
}
运行出来的结果让我震惊了
刚好就是杨辉三角
从这个角度正好解释了他们俩的关系
其实这时候想想杨辉三角的值就是等于它肩膀上两个值的和
刚好对应
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
−
1
]
+
f
[
i
−
1
]
[
j
]
f[i][j]=f[i - 1][j - 1] + f[i - 1][j]
f[i][j]=f[i−1][j−1]+f[i−1][j]