Skip to content

计数

:material-circle-edit-outline: 约 521 个字 :material-clock-time-two-outline: 预计阅读时间 2 分钟

加法原理

你有2个不同的苹果，5个相同的橘子，你只能吃一种水果，你有几种选择？显然是 \(2+1=3\) 种

不相交的集合之并的基数，等于各自基数之和

乘法原理

你有2个不同的苹果，5个不同的橘子，你只能吃一个苹果和一个橘子，你有几种选择？

显然是 \(2*5=10\) 种

有限集笛卡尔积的基数，等于各自基数相乘

从有限集笛卡尔积选取一个元素的任务，可以分解为各有限集选一个的积

Pigeonhole Principle

题目很难！！！！

n+1 个东西放入 n 个盒子，至少有一个盒子有两个东西

n 个东西放入 k 个盒子，至少有一个盒子有至少 [n/k]+1 个东西

Subsequence

序列和子序列，单调递增序列

长度为 \(n^2+1\) 的序列一定有一个长度为 \(n+1\) 的严格增/严格减的子序列

不可重复的 Permutations and Combinations

排序

image-20240603115407142

组合

image-20240603115416594

二项式定理，组合常用公式，什么帕斯卡范蒙德

image-20240603115550369

image-20240603115456401

可重复的 Permutations and Combinations

隔板法

image-20240603125131403

全是题目

生成排列组合

lexicographic ordering 字典序，一个序列 precede 先于另一个序列

我们希望找到一个算法，从最小的字典序一个一个往下推，推出最大的字典序，就能穷举排列了

最小的显然是12345，那么我们的问题就变成从第k小的找出第k+1小的

办法就是：

  1. 首先，从当前序列后面往前，找出第一对前小后大的相邻元素 \({a_j,a_{j+1}}\) ，这意味着 \(a_{j+1}\sim a_n\) 是降序
  2. 然后，我们从 \(a_{j+1}\sim a_n\) 里面比 \(a_j\) 大的元素，取其中最小的放在 \(a_j\) 的位置
  3. 最后，我们将 \(a_j\) 和 \(a_{j+1}\sim a_n\) 剩下的元素从小到大排序放在后面，完成

image-20240603130539779

由此我们可以按照字典序推算出所有的排列组合，达到快速无重复穷举的目的