计数相关

清北学堂 计数

---

上午

推荐图书：《具体数学》《组合数学》（Richard著）
推荐网站：搜索排列

核心：不重不漏

5男人6女人2男孩4女孩选1男人1女人1男孩1女孩的方案：$5\cdot 6\cdot 2\cdot 4=240$

0~9的排列数：$10!$；
首位不为0的话：$9\times9!$

乘法原理：对于某个问题，有很多相互独立子问题，将每个子问题的方案数乘起来是原来问题的答案
加法原理：对于某个问题，不能划分成互不独立的子问题，满足加法原理

若有理数$m/n$是无限小数，则必然是无限循环小数
证明：
考虑鸽笼原理
注意到做竖式除法的时候
写成$n\sqrt m$，而后在m下面写出的数一定是0 ~ n-1中的某个数字
因为是无限小数，所以会写无限多个0~n-1中的某个数字，所以一定会重复

---

组合数基本

加法原理
乘法原理
鸽笼原理（抽屉原理）：有n个笼子，n+1只鸽子，那么至少一个笼子里面有两只或更多鸽子
在图论中的拓展:Ramsey定理

排列

n个元素的集合，写成一个序列的方法有$A(n)=n!$或$P(n)=n!$种
乘法原理应用

定义:0!=1

圆（环）排列：

$\frac{n!}{n}=(n-1)!$
因为可以在任意位置断开，形成一个在链上的排列

错位排列：

1~n，第$i$个人站在第$j$的位置上，其中$i\ne j$
$D_n=(n-1)(D_{n-1}+D_{n-2}$

考虑将这个问题分成很多步，查看分出来的每一步是否等价于当前问题
那么只有在n个人的时候才会考虑第n个人的操作方法
那么n可以站在n-1个位置上，所以有n-1的贡献
所以可以考虑n-1个人中有某个人站在了第n个位置，也就是$D_{n-2}$
再考虑有n-1个人，但是只有n-2个位置（其中一个被n占了，并且第i个人不能站在第n个位置上），此时等价于第i个人不能站在第i号位置上，也就是$D_{n-1}$的情况
即分了两种情况：
第n个人站在第i个位置，并且第i个人站在第n个位置上，此时等价于$D_{n-2}$
第n个人站在第i个位置，并且第i个人没有站在第n个位置上，此时等价于$D_{n-1}$

同时考虑n只能站在1~n-1的位置上，即有(n-1)的贡献
所以得出上述公式$D_n=(n-1){D_{n-1}+D_{n-2}}$

多重集的全排列

多重集：元素可以重复的集合

假定某个多重集中有$n$个元素,$k_1$个$x_1$,$k_2$个$x_2,\cdots,$$k_n$个$x_n$
首先将其中的相同的元素看成不同的元素
那么排列种数为$n!$
再把其中重复的算出来$k_1!k_2!\cdots k_n!$
最后答案为$\frac{n!}{k_1!k_2!\cdots k_n!}$

组合数

一个大小为$n$的集合，选出$m$个元素的方案数$C(n,m)$或$C_n^m$，也记作$n\choose m$
${n\choose m}=\frac{n!}{m!(n-m)!}$

隔板法

$n$个相同的求，放到$m$个不同的盒子里
令$x_i$表示第i个盒子里球的数量
那么问题转化
解方程$x_1+x_2+\cdots+xm=n$
1.每个盒子里至少有一个球
即规定$x_i\ge 1$

隔板法，改变分界点的位置
最前面跟最后面必须有
n-1个空,m-1个板
$ans={n-1\choose m-1}=C(n-1,m-1)$
2.盒子可以为空
即规定$x_i\ge 0$
可以认为是n+m个球即n+m-1个空，m-1个隔板
$ans={n+m-1\choose m-1}=C(n+m-1,m-1)$
3.每个盒子至少两个球
即规定$x_i\ge 2$
可以认为是n-m个球即n-m-1个空，m-1个隔板
$ans={n-m-1\choose m-1}=C(n-m-1,m-1)$

捆绑法

n名男生，m名女生，2名老师排成一行，老师和老师不能相邻，女生和女生不能相邻

[1]
老师可以相邻数量-把两个老师捆绑起来的数量[2]

二项式定理

$(a+b)^n=\sum_{i=0}^na^ib^{n-i}{n\choose i}$

卡特兰数

$1,1,2,5,14,132\cdots$
$C_n=\frac{2n\choose n}{n+1}={2n\choose n}-{2n\choose n-1}$
$C_{n+1}=\sum_{i+1}^nC_iC_{n-i}$

对应的n个问题：
例子：
1.有$n$个$+1$，$n$个$-1$，每个前缀和都$\ge0$的方案数
2.$n$个左括号，$n$个右括号，合法的括号序列数
（左括号看做+1，右括号看做-1）
3.$n$个节点构成的二叉树数量
4.进栈次序是$1,2,\cdots,n$的出栈排列数
（把进栈看做+1，出栈看做-1）
5.正$n+1$边行的三角剖分数量

组合数的计算

求$C(n,m)\bmod p$的值，其中：
1.$n,m\le 10^3,p\le 10^9$
利用组合数递推，直接$n^2$就能做
2.$n,m\le 10^3,p\le 10^9$
①p为质数
求出逆元之后直接暴力求
②p不是质数

将p质因数分解,$p=\prod p_i^{a_i}$，单独考虑每个$p_i^{a_i}$
，如果我们可以求出来每一部分的值，最后就可以用中国剩余定理合并起来

3.$n,m\le 10^{18},p\le 10^3$且p为素数
Lucas定理
${n\choose m}={n\mod p\choose m\mod p}{n/p\choose m/p}\bmod p$

求$m!$和$(n-m)!$的逆元
4.$n,m\le 10^9,p\le 10^5$
做法1：分解质因数
int f(int n)
{return n?n/p+f(n/p):0;}
$\sum_{i=1}n/p^i$

#include<cstdio>
using namespace std;
int n=2333576;
int p=23;
int count(int n){
    if(n>0){
        return n/p+count(n/p);  
    }
    return 0;
}
int count_baoli(int n){
    int cnt = 0;
    for(int i=1;i<=n;i++){
        int t=i;
        while(t%p == 0) cnt++,t/=p;
    }
    return cnt;
}
int count2(int n){
    if(n>0){
        int s = 1;
        if(n/p>0 && ((n/p) & 1)) s = s *(p-1)%pow(p,k) ; // p^k
        s = s*count2(n/p)%pow(p,k); // p^k
        n%=p;
        for(int i=1;i<=n;i++){
            s = s*i%pow(p,k);   // p^k
        }
        return s;
    }
    return 1;
}
int count2_baoli(int n){
    int s = 1;
    for(int i=1;i<=n;i++){
        int t=i;
        while(t%p == 0) t/=p;
        s=s*t%p;
    }
    return s;
}
int main(){
    printf("%d %d\n",count(n),count_baoli(n));
    printf("%d %d\n",count2(n),count2_baoli(n));
    return 0;
}

做法2：
和第二个题思路一样
把p唯一分解
然后用中国剩余定理解决

---

第二类斯特灵数

$S_2(n,k)$
n个数的集合的划分为k个非空集合方法的数目(n个不同的小球放到m个相同的盒子，每个盒子至少放一个球的种数)
$S_2(n,k)=kS_2(n-1,k)+S_2(n-1,k-1)$

把n个不同的小球分到k个可区分的盒子里面且没有空盒子的划分个数：
$k!S_2(n,k)$

第一类斯特灵数

$S_1(n,k)$
将n个不同元素排成k个非空环排列的方法数
$S_1(n,k)=(n-1)S_1(n-1,k)+S_1(n-1,k-1)$

---

下午

整数划分问题

给两个整数$n$和$k$
问：
1.将$n$划分成若干正整数之和的划分数
$\sum_{i=1}^nP(n,i)$
2.将$n$划分成$k$个正整数之和的划分数
$P(n,k)$
3.将$n$划分成最大数不超过$k$的划分数
$\sum_{i=1}^kP(n,i)$
4.将$n$划分成若干奇正整数之和的划分数
5.将$n$划分成若干不同整数之和的划分数
以上5个问题中，$P(i,j)=P(i-1,j-1)+P(i-j,j)$

---

Burnside&Polya

群论

群：给定一个集合$G={a,b,c\cdots}$,和集合上的二元运算$"*"$,并满足：
(1)封闭性:$\forall a,b\in G,\exists c\in G,a*b=c$
(2)结合律:$\forall a,b,c\in G,(a*b)*c=a*(b*c)$
(3)单位元:$\exists e\in G,\forall a\in G,a*e=e*a=a$
(4)逆元:$\forall a\in G,\exists b\in G,a*b=b*a=e,$记$b=a^{-1}$
则称集合$G$在运算$"*"$之下是一个群，简称$G$是群，一般$a*b$简写成$ab$.$"*"$可以是任意运算，如果是具体的乘法$"\times"$,则称为乘法群，如果是具体的加法$"+"$，则称其为加法群。若群$G$中的元素是有限的，则称$G$为有限群，否则称为无限群。有限群中元素的个数称为有限群的阶

.

置换：$n$个元素$1,2,\cdots ,n$之间的一个置换

$$\begin{pmatrix} 1& 2& \cdots &n\\ a_1 &a_2 &\cdots &a_n\\ \end{pmatrix}$$ 表示$1$被$1$到$n$中的某个数$a_1$取代，$2$被$1$到$n$中的某个数$a_2$取代，$\cdots$，直到$n$被$1$中的某个数$a_n$取代，且$a_1,a_2,\cdots a_n$，互不相同

置换群：
置换群的元素是置换，运算是置换的连接。例如：
$\begin{pmatrix}1,2,3,4\\ 3,1,2,4\\\end{pmatrix} \begin{pmatrix}1,2,3,4\\ 4,3,2,1\\\end{pmatrix}= \begin{pmatrix}1,2,3,4\\ 3,1,2,4\\\end{pmatrix} \begin{pmatrix}3,1,2,4\\ 2,4,3,1\\\end{pmatrix}= \begin{pmatrix}1,2,3,4\\ 2,4,3,1\\\end{pmatrix}$
由此可以验证置换群满足群的4个条件

Burnside引理

$G$为$X$的置换群，$C(p)$为$X$中满足在$p$作用下着色不变的着色集大小

$$I=\frac{1}{\vert G\vert}\sum_{i=1}^{\vert G\vert}C(p_i)$$

Polya定理

为上面的Burnside引理中的$C(i)$的计算提供了一种计算方法
假设$p'$表示置换$p$的循环个数
Polya定理告诉我们$C(p)=k^{p'}$(一共$k$种颜色)

---

生成函数系列

泰勒展开

（在某个点附近）把一个函数展开成一个无限的多项式

（已经学过）的泰勒展开：等比求和
$\sum_{i=0}^\infty x^i=\frac{1}{1-x}$
对于泰勒展开的收敛性，并不关心

广义牛顿二项式定理

$(x+y)^n=\sum_{k=0}^\infty C(n,k)x^{n-k}y^k$
其中$C(n,k)=\prod_{i=1}^k(n-i+1)/i$
其中$n$对于分数，负数都对
[3]

形式幂级数

对于一个序列$a_i$，可以定义一个多项式$A(x)=\sum_{i=1}^\infty a_ix^j$
这个叫做原序列的生成函数，是一个形式幂级数。（因为我们不太关心收敛）
$1,1,1\cdots \frac{1}{1-x}$
$1,0,0,\cdots ,1,0,\cdots \frac{1}{1-x^m}$
$1,2,3,\cdots,\frac{1}{(1-x)^2}$
$1,2,4,8,\cdots,\frac{1}{1-2x}$
$C(n,0),C(n,1),C(n,2),\cdots,(1+x)^n$

生成函数的运算

生成函数整体可以做多项式运算（无论用封闭形式还是用多项式形式）
生成函数的乘法相当于做两个集合的组合

微分、积分：形式推导
解递推式
（比如斐波那契数列）
还有FFT……

---

Catalan数通项公式推导

$$D(x)=\sum_{i=0}^\infty d_ix^i$$
$$d_n=\sum_{1\le k\le n}d_{k-1}d_{n-k}$$
Then,
$$D(x)=\sum_{i=0}^\infty(\sum_{k=0}^{i-1}d_kd_{i-k-1})x^i$$
$$(D(x))^2=\sum_{i=0}^\infty(\sum_{k=0}^id_kd_{i-k})x^i$$
Therefore,
$$D(x)=x(D(x))^2+d_0$$
$$D(x)=x(D(x))^2+1$$
Then,
$$D(x)=\frac{1\pm\sqrt{1-4x}}{2x}$$

$D(0)=1,so:D(x)=\frac{1-\sqrt{1-4x}}{2x}$

$$\begin{align*} D(x)&=\frac{1-\sqrt{1-4x}}{2x}\\ &=\frac{1}{2x}(1-(1-4x)^{\frac12})\\ &=\frac{1}{2x}(1-\sum_{i=0}^\infty {\frac12\choose i}(-4x)^i) \end{align*}$$
$$\begin{align*} d_j&=-\frac{1}{2} {\frac{1}{2}\choose {i+1}}(-4)^{i+1}\\ &=-\frac14 \frac{(\frac12 -1)(\frac12-2)\cdots (\frac12 -i)(-4)^{i+1}}{(i+1)!}\\ &=1\frac{(1-2)(1-4)(1-6)\cdots(1-2i)(-2)^i}{(i+1)!}\\ &=\frac{(-1)(-3)(-5)\cdots(-2i+1)(-2)^i}{(i+1)!}\\ &=\frac{1\times 3\times 5\times\cdots \times(2i-1)2^i}{(i+1)!}\\ &=\frac{(2i)!(i+1)}{(i+1)!i!}-\frac{(2i)!(i)}{(i+1)!i!}\\ &=\frac{(2i)!}{i!i!}-\frac{(2i)!}{(i+1)!(i-1)!}\\ &={2i\choose i}-{2i\choose i+1}\ \end{align*}$$

例题：
求这样的$n$位数个数：数字的各个数字都是奇数，而且$1$和$3$必须出现偶数次

解法：
递推考虑$n$位数的结尾
令$a_n$为这样的$n$位数，每个数的各位数字都是奇数，且$1$和$3$出现偶数次
令$b_n$为这样的$n$位数，每个数的各位数字都是奇数，且$1$出现奇数次，$3$出现偶数次（由对称性，也可表示$3$出现奇数次，$1$出现偶数次）
令$c_n$为这样的$n$位数，每个数的各位数字都是奇数，且$1$和$3$出现奇数次
则有:

$$\begin{align*} a_n&=3a_{n-1}+2b{n-1}\\ b_n&=3b_{n-1}+c_{n-1}+a_{n-1}\\ c_n&=3c_{n-1}+2b_{n-1}\\ \end{align*}$$

但是这个式子不对，因为还要考虑$1$和$3$出现$0$次的情况

现在需要减去$1$和$3$没有同时出现的，需要减去$1$没出现、$3$出现偶数次，减去$3$没出现、$1$出现偶数次(由对称性与前一项相等)，加上$1$没出现、$3$没出现的数量。
$1$没出现、$3$出现偶数次($3$没出现、$1$出现偶数次)的数量为$2^{n−1}+2\times 4^{n−1}$。
$1$没出现、$3$没出现的数量为$3^n$

---

加速递推

矩阵乘法
求解递推式（特征值、生成函数）

---

直接指数生成型函数

$$(e^x)^3\left(\frac{e^x+e^{-x}}{2}-1\right)^2$$
对于序列$a_i$，定义生成函数$\sum_{i=0}^\infty\frac{a_i}{i!}x^i$
这样的$1,1,1,\cdot,$对应$e^x$
生成函数的乘法表示了两个集合的排列

---

积性函数

若在$if(\gcd(p,q)=1)$的情况下$f(pq)=f(p)\times f(q)$,则称函数$f$为积性函数
若在任意情况下函数$f$都满足$f(pq)=f(p)\times f(q)$,则称函数$f$为完全积性函数

莫比乌斯反演讲解推荐ppt：PoPoQQQ《莫比乌斯反演》

---

狄利克雷卷积是一种对整数数论函数用约数关系进行的特殊的卷积。
$(f*g)(N)=f(N)*g(N)$
$(f\times g)(N)=\sum_{d\vert N}f(d)\times g(\frac{N}{d})$
如果$f,g$均为积性，那么$f*g,f\times g$也均为积性

几个重要等式：

$$\begin{align*} f=f\times e\\ id=\varphi\times 1\\ e=\mu\times 1\\ \end{align*}$$

• 后面的$\times$基本都代表卷积了
• 函数间的卷积与函数值的乘积不同
• 这里的$1$是个函数，其函数值为$1$
• $"*"$和$"\times"$代表的意义不同！

其中$e=\mu \times 1=[x=1]$

.

$$\begin{align*} &\sum_{i=1}^Ne(\gcd(i,N))\\ =&\sum_{i=1}^N\sum_{d\vert\gcd(i,n)}\mu(d)\\ =&\sum_{i=1}^N\sum_{d\vert i\land d\vert n}\mu(d)\\ =&\sum_{d\vert N}\mu(d)\times \frac{N}{d}\\ =&(\mu\times id)(N)\\ \end{align*}$$

其中最后一行的$\times$表示狄利克雷卷积
.

莫比乌斯反演

$F=f\times 1$
两边同乘$\mu$
$F\times\mu=f\times 1\times\mu$
$F\times\mu=f\times e=f$
从第一个式子到第三个式子也叫莫比乌斯反演

.

$$\begin{align*} &\sum_{i=1}^N\gcd(i,N)\\ =&\sum_{i=1}^N\sum_{d\vert\gcd(i,N)}\varphi(d)\\ =&\sum_{i=1}^N\sum_{d\vert i\land d\vert n}\varphi(d)\\ =&\sum_{d\vert N}\varphi(d)\times\frac{N}{d}\\ \end{align*}$$

某经典式子：

$$\begin{align*} &\sum_{i=1}^N\sum_{j=1}^M\gcd(i,j)\\ =&\sum_{i=1}^N\sum_{j=1}^M\sum_{d\vert\gcd(i,j)}\varphi(d)\\ =&\sum_{i=1}^N\sum_{j=1}^M\sum_{d\vert i\land d\vert j}\varphi(d)\\ =&\sum_{d\le N}\varphi(d)\left[\frac{N}{d}\right]\left[\frac{M}{d}\right] \end{align*}$$

例题：zap
对于给定的$N,M,d$,有多少正整数对$x,y$，满足$x\le N,y\le M$并且$\gcd(x,y)=d$
等价于$x\le\frac{N}{d},y\le\frac{M}{d},$互质的$x,y$的对数

解：

$$\begin{align*} &\sum_{i=1}^N\sum_{j=1}^Me(\gcd(i,j))\\ =&\sum_{i=1}^N\sum_{j=1}^M\sum_{d\vert\gcd(i,j)}\mu(d)\\ =&\sum_{i=1}^N\sum_{j=1}^M\sum_{d\vert i\land d\vert j}\mu(d)\\ =&\sum_{d\le N}\mu(d)\lfloor\frac{N}{d}\rfloor\\ \end{align*}$$

例题2:
与n互素的数的和

$$\begin{align*} &\sum_{i\le n\land \gcd(n,i)=1}i\\ =&\sum_{i\le n}ie(\gcd(n,i))\\ =&\sum_{i\le n}i\sum_{d\vert\gcd(n,i)}\mu(d)\\ =&\sum_{d\vert n}(\mu(d)\sum_{i\le n\land d\vert i}i)\\ =&\sum_{d\vert n}\mu(d)(\frac{n(\frac{n}{d}+1)}{2})\\ =&\frac{n}{2}(\mu\times id+\mu\times 1)\\ =&\frac{n}{2}(\varphi\times e)\\ =&\frac{id*\varphi+e}{2}\\ \end{align*}$$