计数初步（持续更新中）

计数初步

---

Outline

• 计数原理
• 组合数/二项式系数
• 错位排列
• 卡特兰数/卡塔兰数
• 斯特林数/斯特灵数
• 三元环计数

加法原理

乘法原理

定义

计算

小♂试牛刀

• $\sum_{i=1}^nX_i=m,(X_i>0)$∑i=1n​Xi​=m,(Xi​>0)的方案数。

  （把m个相同小球放在n个不同盒子，盒子不能为空的方案数）

• $\sum_{i=1}^nX_i=m,(X_i>=0)$∑i=1n​Xi​=m,(Xi​>=0)的方案数。

  （把m个相同小球放在n个不同盒子，盒子可以为空的方案数）

• $\sum_{i=1}^nX_i=m,(X_i>=k)$∑i=1n​Xi​=m,(Xi​>=k)的方案数。

  （通过给所有盒子钦定都先有k个小球，然后转化为问题2）

• 有m种颜色，第i种颜色恰好用$X_i$Xi​次$(\sum_{i=1}^mX_i=n)$(∑i=1m​Xi​=n)，用这些颜色给一个长度为n的序列上色的方案数。

  • $ans=C_n^{x_1}C_{n-x_1}^{x_2}C_{n-x_1-x_2}^{x_3}…C_{n-x_1-x_2...-x_{m-1}}^{x_m}$ans=Cnx1​​Cn−x1​x2​​Cn−x1​−x2​x3​​…Cn−x1​−x2​...−xm−1​xm​​
  • $ans=\frac{n!}{\Pi_{i=1}^{m}x_i!}$ans=Πi=1m​xi​!n!​

• $n × m$n×m的棋盘，每次都只能向上或者向右，$(1,1)$(1,1)->$(n,m)$(n,m)的方案数。

  （总共走了n+m-2步，把向上走的n-1步任意穿插在里面，$ans=C_{n+m-2}^{n-1}$ans=Cn+m−2n−1​）

• $n × m$n×m的棋盘，有两个棋子分别位于(1,2),(2,1)，这两个棋子同时移动，每次只能向上或者向右，(1,2)->(n-1,m),(2,1)->(n,m-1)，同时两个棋子的路径交集为空的方案数。

  （考虑容斥，先求出两个点到终点任意走的方案数为ans1和ans2，减去不合法的方案数。画一下图，发现两条路径交叉，可以看做从(1,2)->(n,m-1),(2,1)->(n-1,m)。求出分别方案数ans3,和ans4。$ans=ans1*ans2-ans3*ans4$ans=ans1∗ans2−ans3∗ans4）

圆排列