组合数作业+经典模型总结

模型总结

Feature 1（吸收公式）
\(\binom {n}{k}=\frac {n} {k}\binom {n-1} {k-1}\)，\(k\binom {n}{k}=n\binom {n-1}{k-1}\)，\(\frac {\binom {n} {k}}{n}\)。
PF：暴力展开或乱搞。（
Feature 2：\(\sum_{k=0}^nk\binom {n} {k}=n2^{n-1}\)。
PF：考虑 \(n\) 个数中选 \(k\) 个，每个数均摊贡献 \(1\)。就等于考虑每个数，其他数有 \(2^{n-1}\) 种选法，那么这个数就有 \(2^{n-1}\) 的贡献。
Feature 2：$$

作业

哈哈哈打完了证明放在本地 Typora 中第二天来看被关机了。

哈哈我谢谢这位巨佬。膜拜您！！！/bx

重打真好玩！！还能加强对公式的记忆让我们练出更熟练的推式子技巧你说是吧！！！

1

\(x^5y^{13}\) の coefficient：\(-\binom {18} {5}3^52^{13}\)。

\(x^8y^9\) の coefficient：\(0\)。

2

pro1：bridge：\((2+1)^n\)。

pro2：\((r+1)^n\)。

3

bridge：\((3-1)^n\)。

4

\(ans=(-9)^n\)。

5

左式的组合意义为从 \(n\) 个数中选 \(k\) 个其中最后三个数至少有一个被选的方案数。

对应右式的选数的最后一个位置在 \(n\)、\(n-1\)、\(n-2\) 的方案数和。

6

\(n\) 为奇数时所有的组合数系数和为 \(0\)，原式 \(=0\)。

\(n\) 为偶数时发现构造这个 \(\binom {n} {k}^2\) 比较棘手。然后不会等会补。

7

Way1：

\(=\binom {0} {3}\binom {n} {k}+\binom {1} {3}\binom {n} {k-1}+\binom {2} {3}\binom {n} {k-2}+\binom {3} {3}\binom {n} {k-3}\)。

由组合意义知 \(=\binom {n+3} {k}\)。

Way2：

\(=\binom {n+1} {k}+2\binom {n+1} {k-1}+\binom {n+1} {k-2}\)

\(=\binom {n+2} {k}+\binom {n+2} {k-1}\)

\(=\binom {n+3} {k}\)

本质是杨辉三角。（？

8

即证 \(\binom {r} {r-k}(r-k)=\binom {r-1} {r-k-1}r\)。

令 \(t = r-k\)。

即证 \(\binom {r} {t}t=\binom {r-1} {t-1}r\)。发现这就是那啥公式。（当然也可以暴力展开。

9

发现我们很想把 \(\binom {n} {k}(k+1)\) 化成标准形式（？，于是想到分子分母同乘 \(n+1\)。

原式=\(\frac {1-(1-1)^n} {n+1}=\frac {1} {n+1}\)。

10

pro1：即钦定最后一个数选哪里。

pro2（组合意义）：考虑 \(m^2\) 即长度 \(m\) 的数列中的无序二元组个数，令其为 \((a,b)\)。若 \(a=b\)，这样的组合有 \(\binom {1} {n}\) 个。若 \(a\ne b\)，这样的组合有 \(2\binom {2} {n}\) 个，即证。

11

组合意义同上：\(a=6,b=6,c=1\)。

Some Problem

Number of Ways
\(\sum_{i=1}^n\sum_{j=1}^n\binom {|i-j|+k} {k}\)
利用上面的 Feature 3，
\(=\sum_{i=1}^n(\binom {|i-1|+k+1} {k+1}+\binom {|n-i|+k+1} {k+1}-1)\)（\(-1\) 是因为两种情况的交集为 \(1\)）
\(=\sum_{i=1}^n(\binom {(i-1)+(k+1)} {k+1}+\binom {(n-i)+k+1} {k+1}-1)\)
\(=2\times \binom {n+k+1} {k+2}-n\)