5

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

20240603补天ing

离散数学2024-04-19第3-5节 (zju.edu.cn)

加法原理

加法原理就是，你有2个不同的苹果，5个相同的橘子，你只能吃一种水果，你有几种选择？

显然是 \(2+1=3\) 种

乘法原理

乘法原理就是，你有2个不同的苹果，5个不同的橘子，你只能吃一个苹果和一个橘子，你有几种选择？

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

Pigeonhole Principle

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

n个东西放入k个盒子，至少有一个盒子有至少 [n/k] (往上取整)个东西给

但是，题目很难！！！！

\(q_j\) 有 \(n\) 种取值可能，即 \(2n\) 里面的所有奇数，那么 \(n+1\) 个数这么分解之后肯定有两个数的 \(q_j\) 一样，我们记为 \(q_i=q_j\)

于是这俩是可除的，因数为2

Subsequence

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

麻了原来其它科目默认我们会的概念都来自这个离散数学，我是本末倒置了，最后才来学离散

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

例题

Permutations and Combinations

排列组合

不重复的

可重复的（广义）排列组合

隔板法

隔板法公式化

将物品放入箱子问题

生成排列组合

字典序

对于排列，我们定义一个东西叫字典序（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\) 剩下的元素从小到大排序放在后面，完成

这个算法挺好理解的，可以画折线图看看，有空我补一下怎么理解

相信很多人之前穷举都是有意无意采用了这种办法，因为这种是最直觉最直观的办法

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