杨辉三角详解
杨辉三角是什么?
杨慧三角是二项式系数在三角形中的一种集合排列!!
换一种说法: 杨辉三角是二项式系数, 通过数据三角形表示, 发现的数学规律.
杨辉三角与二项式系数联系
定义:
在数学里, 二项式系数, 或组合数, 是定义为形如
(
1
+
x
)
n
(1 + x)^n
(
1
+
x
)
n
展开后x的系数(其中n为自然数, k为整数)
那么一般二项式
(
x
+
y
)
n
(x + y)^n
(
x
+
y
)
n
的幂可用二项式系数记为
C
n
r
C^r_n
C
n
r
通常来讲，二项式系数代表的是从n件物品中，无序地选取k件的方法总数.
证明二项式系数与组合数之间的联系:
假设n = 4, k = 2. 通过组合数公式可以得到组合数为 6.
假如我们把
(
1
+
x
)
4
(1 + x)^4
(
1
+
x
)
4
展开并标记每一个x, 就会得到:
(
1
+
x
1
)
(
1
+
x
2
)
(
1
+
x
3
)
(
1
+
x
4
)
(1+x_1)(1+x_2)(1+x_3)(1+x_4)
(
1
+
x
1
)
(
1
+
x
2
)
(
1
+
x
3
)
(
1
+
x
4
)
上式等于:
(
1
+
x
1
)
⋯
(
1
+
x
4
)
=
⋯
+
x
1
x
2
+
x
1
x
3
+
x
1
x
4
+
x
2
x
3
+
x
2
x
4
+
x
3
x
4
+
⋯
(1+x_1)⋯(1+x_4)=⋯+x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_3x_4+⋯
(
1
+
x
1
)
⋯
(
1
+
x
4
)
=
⋯
+
x
1
x
2
+
x
1
x
3
+
x
1
x
4
+
x
2
x
3
+
x
2
x
4
+
x
3
x
4
+
⋯
假如把标记去掉, 那么
x
2
x^2
x
2
的系数正好是等于6, 与
C
4
2
C_4^2
C
4
2
相符合
也就证明了：
(
1
+
x
)
n
(1+x)^n
(
1
+
x
)
n
中
x
k
x^k
x
k
的系数正好等于从n个元素中选取k个元素的组合数（
C
n
k
C^k_n
C
n
k
）
.
杨辉三角代码实现的递推公式
C
[
i
]
[
j
]
=
C
[
i
−
1
]
[
j
]
+
C
[
i
−
1
]
[
j
−
1
]
;
C[i][j]=C[i−1][j]+C[i−1][j−1];
C
[
i
]
[
j
]
=
C
[
i
−
1
]
[
j
]
+
C
[
i
−
1
]
[
j
−
1
]
;
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
递推:
#include<bits/stdc++.h>
using namespace std;
map<int, map<int, int> >mp;
int main()
{
mp[0][0] = 1;
//输入一个row, col表示待查找的行和列, 输出其对应杨辉三角的值
int row, col; cin >> row >> col;
for(int i = 1;i <= row; i++)
for(int j = 1;j <= i; j++){
mp[i][j]=mp[i - 1][j] + mp[i - 1][j - 1];
if(i == row && j == col){ cout << mp[i][j]; return 0; }
}
return 0;
}
组合数公式:
C
n
m
=
A
n
m
m
!
=
n
!
m
!
(
n
−
m
)
!
C^m_n=\frac{A^m_n}{m!}=\frac{n!}{m!(n−m)!}
C
n
m
=
m
!
A
n
m
=
m
!
(
n
−
m
)
!
n
!
#include<bits/stdc++.h>
using namespace std;
//求阶乘
int fun1(int num){
int ans = 1;
for(int i = 1;i <= num; i++){
ans *= i;
}
return ans;
}
// 求组合数
int fun2(int a, int b){
return fun1(a) / (fun1(a) * fun1(a - b));
}
int main()
{
int row, col;
cin >> row >> col;
cout << fun2(row - 1, col - 1);
}