当前位置: 首页 > news >正文

排列组合 容斥 总结

加法原理

加法原理。很直白的,就是一个用加法来弄的原理。

简单来说,就是做一件事情有 \(n\) 种方法,第 \(i\) 种方法又有 \(a_i\) 个具体的操作方案。那么非常显然,做这件事情就有 \(a_1 + a_2 + \dots + a_{n-1} + a_n = \sum_{i=1}^{n} a_i\) 种方案。

说说具体用途吧:最常见的,DP 里面统计方案数,由于这些解决方案是互不干扰的,也就是说如果选择 \(1\) 类方法就不可能同时选择 \(2\) 类方法,那么很多时候就是把它们加起来啦。

这就是加法原理。

乘法原理

乘法原理,顾名思义,和加法原理一样,当然是用乘法来弄的原理啦!

乘法原理和加法原理不同,它表示的是,做一件事情有 \(n\) 个步骤,第 \(i\) 个步骤又有 \(a_i\) 种具体的操作方案,那么做这件事情一共就有 \(a_1 \times a_2 \times \dots a_{n-1} \times a_n = \prod_{i=1}^{n} a_i\) 中具体的操作方案。

用途吧,就是很多时候考虑统计方案数的时候,要分步骤来考虑——换言之,分类讨论?——总之就是有一个分步骤的阶段的情况下,就要用到乘法原理,把它们乘起来啦。

这就是乘法原理。

全排列

全排列表示有 \(n\) 个互不相同的物品,然后将这些物品全部打乱,重组地去排列,一共有多少种方法。答案显然,\(n \times (n-1) \times (n-2) \times \dots \times 2 \times 1\),定义这个东西为 \(n!\),即 \(n\) 的阶乘。

排列组合

排列,就是指从 \(n\) 个物品中选择 \(m\) 个排成一排。假设它们都互不相同,那么方案数是多少呢?很显然,排在第一个位置有 \(n\) 种选法,第二个位置有 \(n-1\) 种选法,第 \(i\) 个位置有 \(n-i+1\) 种选法,第 \(m\) 个位置有 \(n-m+1\) 种选法,全部乘起来,那就是 \(n \times (n-1) \times (n-2) \times \dots \times (n-m+1)\) 啦!这就定义为 \(A_{n}^{m}\),且有公式 \(A_{n}^{m} = \dfrac{n!}{(n-m)!}\)

组合,同样是从 \(n\) 个物品中选择 \(m\) 个,但是不同的是,它是选择 \(m\) 个,但是只把这东西当做一个集合,并不对其进行排序——对,差别就在于,它比排列少考虑了具体的排序情况!这东西定义为 \(C_{n}^{m}\),也记做 \(\binom{n}{m}\),且有公式 \(C_{n}^{m} = \binom{n}{m} = \dfrac{n!}{(n-m)!\space{}m!}\)。对!就是比排列多除以了一个 \(m!\) 而已,因为不考虑顺序啦。

组合还有一个公式,那就是 \(C_{n}^{m} = C_{n-1}^{m-1} + C_{n-1}^{m}\),这也是求解杨辉三角时的递推公式。为什么呢?因为我们已经考虑完了前 \(n-1\) 个元素的情况,现在多了一个 \(n\) 元素,我们可以考虑选它,那么之前 \(n-1\) 个元素中就只需要选择 \(m-1\) 个了,这就是 \(C_{n-1}^{m-1}\),也可以考虑不选它,那么之前 \(n-1\) 个元素中还需要选择 \(m\) 个,这就是 \(C_{n-1}^{m}\),加法原理加起来就有公式 \(C_{n}^{m} = C_{n-1}^{m-1} + C_{n-1}^{m}\) 啦。

杨辉三角可以 \(O(n^2)\) 预处理出来,因此当 \(n\) 不大且需要使用组合数的时候常用杨辉三角预处理哦。

例题选讲

题太多了,我就挑几道重点讲,其他的带过一下好吧。

http://www.hskmm.com/?act=detail&tid=30385

相关文章:

  • 10.13每日总结
  • 新学期每日总结(第7天)
  • 20232422 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • Day 9
  • 14 10.13
  • 日志|前端框架Vue
  • oop.shiyan1
  • 玄机——第一章 应急响应-Linux日志分析 wp
  • 第四周第五天4.5
  • 深入解析:flutter AudioPlayer的使用问题及处理
  • 11 10.10
  • 12 10.11
  • P3330 [ZJOI2011] 看电影
  • 20232315 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 地址
  • CSP-S 2025 提高级模拟赛 Day6 复盘 B.连通子图
  • 新手村程序
  • Android Camera openCamera - 教程
  • 信号与系统
  • 大作业第一阶段验收小组集体加5分 -
  • 业务定义与指标体系搭建
  • Linux使用笔记
  • [Vulhub靶机]W1R3S靶机渗透
  • 基于zynq实现一个边缘识别视频流(预学习HLS篇)
  • 咬鼠
  • 10月13日日记
  • 分享一个知乎高赞回答生成AI指令:让技术人也能写出有深度的回答
  • 实用指南:C语言速成秘籍——循环结构(while、do while、for)和跳转语句(break,continue)
  • 描述https的加密过程
  • CSP-S 2025 提高级模拟赛 Day6 复盘 A.选择方案