算法题中常用数学概念、公式、方法汇总(其四:组合学)
组合学
加法原理
加法原理是指做一件事情,完成它有n
类方式,第一类方式有M1
种方法,第二类方式有M2
种方法,以此类推,第n
类方式有Mn
种方法,那么完成这件事情共有M1 + M2 + ... + Mn
种方法。
乘法原理
乘法原理是指做一件事,完成它需要分成n
个步骤,做第一 步有M1
种不同的方法,做第二步有M2
种不同的方法,以此类推,做第n
步有Mn
种不同的方法。那么完成这件事共有 N = M1 × M2 × M3 × ... × Mn
种不同的方法。
排列组合
排列(arrangement/permutation)指的是,从给定个数的元素中取出指定个数的元素并进行排序的过程。
组合(combination)指的是,从给定个数的元素中仅仅取出指定个数的元素的过程,不需要考虑排序问题。
考虑从n
个小球中取出m
个小球的问题,若
- 这些小球两两之间是不同的(比如存在编号),那么取出的方式记为 A n m A_n^m Anm?或 A ( n , m ) A(n,m) A(n,m),存在公式
A n m = n × ( n ? 1 ) × ( n ? 2 ) × . . . × ( n ? m + 1 ) = n ! ( n ? m ) ! A_n^m = n×(n-1)×(n-2)×...×(n-m+1) = \frac{n!}{(n-m)!} Anm?=n×(n?1)×(n?2)×...×(n?m+1)=(n?m)!n!?
- 这些小球两两之间是全同的,那么取出的方式记为 C n m C_n^m Cnm?或 C ( n , m ) C(n,m) C(n,m),存在公式
C n m = n × ( n ? 1 ) × ( n ? 2 ) × . . . × ( n ? m + 1 ) m × ( m ? 1 ) × ( m ? 2 ) × . . . × 2 × 1 = n ! m ! ( n ? m ) ! = A n m m ! C_n^m = \frac{n×(n-1)×(n-2)×...×(n-m+1)}{m×(m-1)×(m-2)×...×2×1} = \frac{n!}{m!(n-m)!} = \frac{A_n^m}{m!} Cnm?=m×(m?1)×(m?2)×...×2×1n×(n?1)×(n?2)×...×(n?m+1)?=m!(n?m)!n!?=m!Anm??
组合恒等式
对于组合而言,存在以下恒等式成立
C
n
m
=
C
n
n
?
m
C_n^m = C_n^{n-m}
Cnm?=Cnn?m?
C
n
m
+
C
n
m
+
1
=
C
n
+
1
m
+
1
C_n^m + C_n^{m+1}= C_{n+1}^{m+1}
Cnm?+Cnm+1?=Cn+1m+1?
C
n
0
+
C
n
1
+
C
n
2
+
C
n
3
+
.
.
.
+
C
n
n
?
1
+
C
n
n
=
∑
i
=
0
n
C
n
i
=
2
n
C_n^0 + C_n^1+C_n^2+C_n^3+...+C_n^{n-1}+C_n^n = \sum_{i=0}^{n}C_n^i = 2^n
Cn0?+Cn1?+Cn2?+Cn3?+...+Cnn?1?+Cnn?=i=0∑n?Cni?=2n
其中最后一个恒等式可以用二项式定理求证。
二项式定理
二项式定理是指,两个数之和的整数次幂可以展开为两整数的多项式之和,具体形式如下
( x + y ) n = C n 0 x 0 y n + C n 1 x 1 y n ? 1 + C n 2 x 2 y n ? 2 + . . . C n n ? 1 x n ? 1 y 1 + C n n x n y 0 = ∑ i = 0 n C n i x i y n ? i (x+y)^n = C_n^0x^0y^n + C_n^1x^1y^{n-1} + C_n^2x^2y^{n-2} + ... C_n^{n-1}x^{n-1}y^1 + C_n^nx^ny^0 = \sum_{i=0}^{n}C_n^ix^iy^{n-i} (x+y)n=Cn0?x0yn+Cn1?x1yn?1+Cn2?x2yn?2+...Cnn?1?xn?1y1+Cnn?xny0=i=0∑n?Cni?xiyn?i
代入 x = 1 x =1 x=1和 y = 1 y = 1 y=1,即可得到式子 C n 0 + C n 1 + C n 2 + C n 3 + . . . + C n n ? 1 + C n n = ∑ i = 0 n C n i = 2 n C_n^0 + C_n^1+C_n^2+C_n^3+...+C_n^{n-1}+C_n^n = \sum_{i=0}^{n}C_n^i = 2^n Cn0?+Cn1?+Cn2?+Cn3?+...+Cnn?1?+Cnn?=i=0∑n?Cni?=2n
华为OD算法/大厂面试高频题算法练习冲刺训练
-
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!
-
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!
-
60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁
-
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
-
可查看链接 大厂真题汇总 & OD真题汇总(持续更新)
-
绿色聊天软件戳
od1336
了解更多
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!