计数问题
T路计数
有一个这样的问题，一个\(n\times m\)的矩形，从左上角走到右下角总共有多少种方法（只能往下或者右走），有两种方法求解，第一种用动态规划；第二种，左上走到右下共需要走\(m+n\)中方法，从中选\(n\)步往下走，则方法数为\(\displaystyle \tbinom{m+n}{n}\)；
那么可能会有这样一种想法，如果按走马的方式来进行，我们只能\(dp\)了；
卡特兰数
\[C_n = \frac{(2n-2)!}{n!(n-1)!}\]
它表示，由\((0, 0)\)到\((2n, 0)\)，中途不经过\(x\)轴且位于上半平面（下半平面）的\(\text{T}\)路的条数；\(\text{T}\)路由若干\(\text{T}\)步（由\((x,y)\)到\((x+1,y+1)\)或\((x+1, y -1)\)）组成；
多少场球赛
\(100\)个球队进行比赛，每场比赛淘汰掉一队，问最终进行多少场比赛；每场淘汰\(1\)队，\(100\)队最终剩下\(1\)队，所以是\(99\)场比赛；
反向思考
一个班级男生\(m\)个，女生\(n\)个，其中有一对双胞胎兄妹，现在需要从男生中选取一个班长，女生中选取一个团支书，并且不能同时选择该兄妹，问有多少种方法；
如果直接思考，需要分类讨论；可以这样，不考虑特殊约束共\(m\times n\)种，特殊情况一种，那么总共\(m\times n - 1\)种
一些实际问题
- 把\(r\)件相同的物品分给\(n\)个人的不同方法为\(C_{n+r-1}^{r}\)；
- 把\(r\)件相同的物品分给\(n(n\le r)\)个人，使得每人至少分得一件物品的不同方法为\(C_{r-1}^{r-n}\)，隔板法公式；
- 把\(6\)本不同的书平均分为\(3\)堆，分法为\(\frac{C_6^2C_4^2C_2^2}{A_3^3}\)
- \(6\)本书分成\(3\)堆，一份\(4\)本，另外两份都是\(1\)本，方法\(\frac{C_6^4C_2^1C_1^1}{A_2^2}\)
- 对于简单环形染色问题，要求相邻区域颜色不同，一般跳格分类讨论：计数原理
排列
圆排列
\(n\)个数字取\(r\)个围成一个圆，问有多少种方法（圆平面内旋转圆得到的视为同一种）；将一个\(k\)个元素的圆排列，从某个间隔位置分开得到一个线性排列共有\(k\)种方法。也就是说一个圆排列对应\(k\)种线性排列，那么\(A_n^r\)种线性排列对应的圆排列k数为\(\frac{A_n^r}{r}\)；
项链排列
将一个圆排列翻转\(360\)度得到的两种圆排列视为同一种；则项链排列数为\(\frac{A_n^r}{2r}(3\leq r\leq n )\)；
多重排列
将一个含有重复字母的字符串重排，共有多少种排列；
如pingpang，现在将同一种字母看成不同字母，求出排列数之后除以冗余度，那么p1p2n1n2g1g2ia，共\(\frac{8!}{2!2!2!}\)种排列
若有\(n\)个元素，\(r_1\)个\(x_1\)，\(r_2\)个\(x_2\)，\(\dots{}r_t\)个\(x_t\)， 那么全排列数为\(\frac{n!}{r_1!r_2\dots r_t!}\)；二项式定理前的系数可以按这种方式理解；
隔板法
\(6\)个洞口，洞口每次只能进入一个乒乓球，一组编号为\(1\dots9\)的\(9\)个乒乓球滚入洞口的方案有多少；
这题很妙，用隔板法\(+\)可重排列；
如果不考虑编号，那么直接使用隔板法；现在对于某种隔板的结果，我们可以把\(9\)个编号分配给这些小球，那么就有\(9!\)种分配法；
或者另外一种思路，将\(5\)个隔板编号，共\(14\)个元素全排，之后除以隔板的冗余度；
或者，先用隔板将区域划分好，然后往里面放有编号的小球，编号为\(1\)的小球有\(6\)种放法，编号为\(2\)的小球有\(7\)种，\(\dots\)
看到这里，我不禁感叹，数学真的太棒了；
另外，解决这个问题的一个重要前提就是把给定的问题转换成数学模型；
对于分区域的问题，通常可以用隔板法解决；
母函数
对于一个序列\(C_0、C_1\dots C_n\)，我们称\(G(x)=C_0 + C_1x^1+\dots +c_nx^n\)为该序列的母函数；
假如我们有\(m\)个骰子，对于\(m\)个骰子的和，可以定义母函数\(G(x)=(x+x^2+x^3+x^4+x^5+x^6)^m\)，其中\(x^k\)前的系数表示骰子和为\(k\)的骰子点数的可能情况数；
若有\(1、2、4、8、16、32\)克的砝码，问能称出哪几种重量？有几种可能方案？
\[\begin{aligned} G(x) &= (1 + x)(1 + x^2)(1 + x^4)(1 + x^8)(1 + x^{16})(1 +x^{32})\\ &=(1 + x + x^2 + \dots + x^{63})\\ &=\sum_{k=0}^{63}x^k \end{aligned}\]
\(G\)的每一项\((1+x^k)\)表示选或者不选质量为\(k\)的砝码；
整数拆分
若整数\(n\)拆分成\(1、2、3\dots m\)的和，并允许重复，求其母函数：
\[ \begin{aligned} G_1(x) & = (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots)\dots (1 +x^m + x^{2m} + \dots)\\ & = \frac{1}{1-x} \frac{1}{1-x^2} \dots \frac{1}{1-x^m} \end{aligned}\]
其中\(G\)的\((1+x^m+\dots)\)表示数字\(m\)选取的情况，我认为这里也可以考虑每个数字的选取情况（最多\(n\)项，即每项都为1），那么
\[ G(x) = (1 + x + x^2 + \dots + x^m)\dots(1 + x + x^2 + \dots + x^m)\]
上面\(G(x)\)共n项
ref
1.https://www.bilibili.com/video/BV1vZ4y1j7gf?p=25&spm_id_from=pageDriver