Comb problem
十二重计数法ψ(｀∇´)ψ
一些有意思的题ψ(｀∇´)ψ
一个四色定理的方案数计数ψ(｀∇´)ψ
1 2 3 4 5 | |
给这个地图上色，问方案数。
先考虑确定 A 区域和 B 区域的颜色是否相同。
因为 A，B 区域的颜色决策会导致 E,C 的颜色决策数改变。
- 如果 A, B 同色，那么 D 就有 3 种方案，然后 E, C 就各有 2 种方案，答案 \(4\times 1 \times 3 \times 2 \times 2 = 48\)。
- 如果 A, B 不同色，那么 D 只有 2 种方案，E, C 各自只有一种，答案 \(4 \times 3 \times 2 \times 1 \times 1 = 24\)。
最终答案 \(48 + 24 = 72\)。
这里能抽象出来的一个小 Trick：
所以对于这种 方案数问题，在某一个决策会影响之后的决策数量的时候就要分类讨论。
一个插板法的应用ψ(｀∇´)ψ
扔 \(7\) 个质地均匀的骰子，出现和为 \(10\) 的概率 为 \(\dfrac{n}{6^7}\)，\(n\) 应该等于多少？
可以转化为插板法，答案是 \(\dbinom{10 - 1}{7 - 1}\)，因为变量都是 \(\le 6\) 的，多了不够了，所以直接这么做没有问题。
另外一个插板法的应用ψ(｀∇´)ψ
定义 \(D(n)\) 表示将正整数 \(n\) 分解为如下形式的方案数：\(n = f_1 \times f_2 \times f_i \dots\)，其中 \(i \ge 1, f_i \ge 1\)，\((f_i, f_{j}); (f_j, f_i)\) 是不同的方案。
求 \(D(96)\)。
首先发现 \(96 = 2^5 \times 3\)，把 \(3\) 拿出来先不管，
然后 \(2^5\) 显然可以分成 \(2^{c_1}, 2^{c_2},\dots 2^{c_m}, m \le 5, c_i \ge 0\)
然后对于 \(m = i\) 的情况，可以把 \(3\) 放到这些数里面插板（可以是头尾），或者直接乘到这些数上面，所以此时的方案数是 \((i + 1 + i) \times i!\)，因为还可以全排列。
然后就只能对于每个情况硬算了。。。。。
最后更新:
September 14, 2023