算法题中常用数学概念、公式、方法汇总(其四:组合学)

2023-12-27 14:31:13

组合学

加法原理

加法原理是指做一件事情,完成它有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=0n?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=0n?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=0n?Cni?=2n


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

文章来源:https://blog.csdn.net/weixin_48157259/article/details/135242191
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。