加法原理

若完成一件事的方法有 nn 类,其中第 ii 类的方法包括 aia_i 中不同的方法,且这些方式互不重合,则完成这件事共有 a1+a2+a3++ana_1 + a_2 + a_3 + \cdots + a_n 种不同的方法。

乘法原理

若完成一件事的方法有 nn 个步骤,其中第 ii 步骤有 aia_i 中不同的完成方法,且这些步骤互不干扰,则完成这件事共有 a1×a2×a3××ana_1 \times a_2 \times a_3 \times \cdots \times a_n 种不同的方法。

排列数

nn 个不同的元素中依次取出 mm 个元素排成一列,产生的不同排列方法的数量是:

Anm=n!(nm)!=n(n1)  (nm+1)A_n^m = \frac{n!}{(n-m)!} = n \cdot (n - 1) \cdot\ \cdots \ \cdot (n - m + 1)

组合数

nn 个不同的元素中依次取出 mm 个元素组成一个集合(不考虑顺序),产生的不同集合数量是:

Cnm=n!m(nm)!=Anmm!C_n^m = \frac{n!}{m(n-m)!} = \frac{A_n^m}{m!}

性质

Cnm=CnnmC_n^m = C_n^{n - m}

Cnm=Cn1m+Cn1m1C_n^m = C_{n-1}^m + C_{n-1}^{m-1}

i=0nCni=2n\sum_{i = 0} ^ n C_n^i = 2^n

Lucas 定理

pp 是质数,则对应任意整数 1mn1 \le m \le n , 有

CnmCnmodpmmodp×Cn/pm/p(mod p)C_n^m \equiv C_{n \mod p}^{m \mod p} \times C_{n/p} ^ {m/p} (mod \ p)

证明

古代猪文

二项式定理

(a+b)n=k=0nCnkakbnk(a+b) ^ n = \sum\limits_{k=0} ^ n C_n^k a^k b^{n - k}

证明

数学归纳法。当 n=1n=1 时,(a+b)1=Cn0a0b1+Cn1a1b0=a+b(a + b) ^ 1 = C_n^0 a^0 b^1 + C_n ^ 1 a^1 b^0 = a + b 成立

假设当 n=mn = m 时成立,则当 n=m+1n = m + 1 时有:

(a+b)m+1=(a+b)(a+b)m(a+b)^{m+ 1} = (a+ b)(a + b) ^ m

=(a+b)k=0mCmkakbmk= (a + b)\sum\limits^m_{k=0}C_m^ka^kb^{m-k}

=k=0mCmkak+1bmk+k=0mCmkakbmk+1= \sum\limits_{k=0}^m C_m^ka^{k+ 1}b^{m-k} + \sum\limits_{k = 0} ^ mC_m^k a^k b^{m-k+ 1}

=k=0m+1Cmk1akbmk+1+k=0mCmkakbmk+1= \sum\limits_{k=0}^{m+ 1}C_m^{k-1}a^k b^{m-k+1} + \sum_{k=0} ^ m C_m^k a^k b^{m-k+1}

=k=0m+1(Cmk1+Cmk)akbmk+1=\sum\limits_{k = 0} ^ {m +1} (C_m^{k - 1} + C_m^k)a^kb^{m-k+1}

(a+b)n=k=0m+1Cnkakbm+1k(a+b) ^ n = \sum\limits_{k=0} ^ {m+1} C_n^k a^k b^{m+1 - k}

证毕。

裸题:计算系数

多重集的排列数

多重集是指包含重复元素的广义集合。设 S={n1a1,n2a2,,nkak}S = \{n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots,n_k \cdot a_k\} 是由 n1n_1a1a_1n2n_2a2  nka_2 \ \cdots \ n_kaka_k 组成的多重集,记n=n1++nkn = n_1 + \cdots + n_kSS 的全排列数量为:

n!n1!n2!nk!\frac{n!}{n_1!n_2! \cdots n_k!}

多重集的组合数

S={n1a1,n2a2,,nkak}S = \{n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots,n_k \cdot a_k\} 是由 n1n_1a1a_1n2n_2a2  nka_2 \ \cdots \ n_kaka_k 组成的多重集,设 rni(i[i,k],rZ)r \leq n_i (\forall i \in [i,k] , r \in \mathbb{Z})。从 SS 中取出 rr 个元素组成一个多重集(不考虑元素顺序),产生的多重集数量为

Ck+r1k1C_{k + r - 1} ^ {k-1}

抽屉原理

桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有 n+1n+1 个元素放到 nn 个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理

母函数

生成函数即母函数,是组合数学中尤其是计数方面的一个重要理论和工具。

生成函数有普通型生成函数和指数型生成函数两种,其中普通型用的比较多。

形式上说,普通型生成函数用于解决多重集的组合问题,而指数型母函数用于解决多重集的排列问题。

母函数还可以解决递归数列的通项问题(例如使用母函数解决斐波那契数列的通项公式)。

Ignatius and the Princess III

Algorithm 1

考虑暴力递归

#include <bits/stdc++.h> 
using namespace std;

int N; 

int Solve(int N , int M) { //将 n 划分为 最大数不超过 m 的划分数 
    if(N == 1 || M == 1) return 1;
    else if(N < M) return Solve(N , N);
    else if(N == M) return 1 + Solve(N , N - 1);
    else return Solve(N - M , M) + Solve(N , M - 1);
}

int main()  { 
    while(~scanf("%d" ,&N)) {
        printf("%d\n" ,Solve(N , N));
    }
    return 0; 
} 

时间复杂度 O(2n)O(2^n)

Algorithm 2

为了减少计算冗余,我们考虑 dpdp

#include <bits/stdc++.h> 
using namespace std;

int Dp[210][210] , n;

int main() {
    for(int N = 1; N <= 200; N++) {
        for(int M = 1; M <= 200; M++) {
            if((N == 1) || (M == 1)) Dp[N][M] = 1;
            else if(N < M) Dp[N][M] = Dp[N][N];
            else if(N == M) Dp[N][M] = Dp[N][M - 1] + 1;
            else Dp[N][M] = Dp[N][M - 1] + Dp[N - M][M]; 
        }
    } 
    while(~scanf("%d" ,&n)) {
        printf("%d\n" ,Dp[n][n]);
    }
    return 0; 
}

时间复杂度 O(n2)O(n^2)

Algorithm 3

重点:普通型母函数

本题实际上是回到形式幂级数的模板题

我们先用一个简单的栗子展开

从数字 1,2,3,41,2,3,4 中取出一个或多个相加(每个数最多只能用一次),能组成几个数?每个数有几种组合?

我们给出一个公式:

(1+x)(1+x2)(1+x3)(1+x4) = 1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10(1+x)(1+x^2)(1+x^3)(1+ x^4) \ = \ 1 + x + x^2 + 2x^3 + 2x^4 + 2x^5 +2x^6+ 2x^7 + x^8 + x^9 + x^{10}

公式左边的 xx 的幂与组合用到的数字 1,2,3,41,2,3,4 相对应,观察公式左边,包括四个部分,(1+x)(1+x) 中的 xx11 次幂, 1+x21+x^2 中的 x2x^222 次幂,以此类推,刚好是数字 1,2,3,41,2,3,4

  • 公式右边 xx 的幂与表格中的组合数 SS 是对应的。公式右边的 xx 的幂从 111010 , 组合数也是 111010

  • 公式右边的系数与表格中的 NN 相对应,都是 1,1,2,2,2,2,2,1,1,11,1,2,2,2,2,2,1,1,1

因此,用这个公式可以计算上面的组合数问题.

这就是回到形式幂级数的原理:把组合问题的加法与幂级数的乘幂对应起来

解释这个公式也很简单,为了理解,我们将公式写为:

(x0×1+x1×1)(x0×2+x1×2)(x0×3+x1×3)(x0×4+x1×4)(x^{0\times 1} + x^{1 \times 1})(x^{0\times 2} + x^{1 \times 2})(x^{0\times 3} + x^{1 \times 3})(x^{0\times 4} + x^{1 \times 4})

其含义以 (x0×1+x1×1)(x^{0\times 1} + x^{1 \times 1}) 为例, x0×1x^{0 \times 1} 表示用 0011x1×1x^{1 \times 1} 表示用 1111

所以,这个公式的本质就是组合问题的反应:用或者不用数字 11 ,用或者不用数字 22 ,以此类推,公式就是这样构造出来的。

回到本题,母函数显然为:

(x0×1+x1×1+x2×1+)(x0×2+x1×2+x2×2+)(x0×3+x1×3+x2×3+)(x ^{0 \times 1} + x^{1 \times 1} + x ^ {2 \times 1} + \cdots)(x ^{0 \times 2} + x^{1 \times 2} + x ^ {2 \times 2} + \cdots)(x ^{0 \times 3} + x^{1 \times 3} + x ^ {2 \times 3} + \cdots) \cdots

暴力展开多项式即可

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 210;

int Ans[MAXN] , C[MAXN];

int S;

void Solve() {
	for(int i = 0; i <= 200; i++) {
		Ans[i] = 1;
	}
	for(int k = 2; k <= 200; k++) {
		for(int i = 0; i <= 200; i++) {
			for(int j = 0; j + i <= 200; j += k) {
				C[i + j] += Ans[i];
			}
		}
		for(int i = 0; i <= 200; i++) {
			Ans[i] = C[i];
			C[i] = 0;
		}
	}
}

int main() {
	Solve();
	while(~scanf("%d" ,&S)) {
		printf("%d\n" ,Ans[S]);		
	}
	return 0;
}

时间复杂度:O(n3)O(n^3)

既然DP的时间复杂度更优,为什么要用生成函数

优点:容易想、空间小(强行挽回颜面

普通型母函数

定义:
对于任意数列 a0,a1,a2,a3,ana_0 , a_1 , a_2 , a_3 , \cdots a_n

即用如下方法与一个函数联系起来:

G(x)=a0+a1x1+a2x2+a3x3++anxnG(x) = a_0 + a_1 x^1+a_2x^2+a_3 x^3 +\cdots +a_n x^n

则称 G(x)G(x) 是数列的生成函数

其一般形式为:

G(an;x)=n=0anxnG(a_n;x) = \sum\limits_{n = 0} ^ \infty a_nx^n

e.g.e.g. 求斐波那契数列通项

斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:01123581321340、1、1、2、3、5、8、13、21、34、…在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0F(0)=0F(1)=1F(1)=1,F(n)=F(n1)+F(n2)(2n,nN)F(n)=F(n - 1)+F(n - 2)(2 \le n ,n ∈ \mathbb{N})——百度百

我们设 f0=0,f1=1,f2=1,f3=2,,fn=fn1+fn2f_0 = 0 , f_1 = 1,f_2=1,f_3 = 2 , \cdots , f_n = f_{n - 1} + f_{n - 2}

G(x)=i=0fixiG(x) = \sum_{i=0}^\infty f_i x^i

G(x)=f0+f1x+i=2fixiG(x) = f_0 + f_1 x + \sum\limits_{i=2}^\infty f_i x^i

G(x)=x+i=2(fi2+fi1)xiG(x) = x + \sum\limits_{i=2}^\infty (f_{i-2} + f_{i-1}) x^i

G(x)=x+x2i=2fi2xi2+xi=2fi1xi1G(x) = x + x ^ 2 \sum\limits_{i = 2} ^ \infty f_{i-2}x^{i - 2} + x \sum\limits_{i=2}^\infty f_{i-1} x^{i-1}

G(x)=x+x2G(x)+G(x)G(x) = x + x ^ 2 G(x) + G(x)

G(x)=x1xx2G(x) = \frac{x}{1-x-x^2}

考虑到这是封闭形式,我们尝试用待定系数法将其化为广义二项式的形式并将其展开。

设:

x1xx2=A1ax+B1bx\frac{x}{1 - x - x ^ 2} = \frac{A}{1-ax} + \frac{B}{1-bx}

然后进行通分

x1xx2=AAbx+BBax1axbx+abx2\frac{x}{1 - x - x ^ 2} = \frac{A - Abx + B - Bax}{1-ax-bx+abx^2}

解得:

A=15A = \frac{1}{\sqrt{5}}

B=15B = -\frac{1}{\sqrt{5}}

a=1+52a = \frac{1+\sqrt{5}}{2}

b=152b = \frac{1-\sqrt{5}}{2}

那么:

G(x)=15((11+52x)1(1152x)1)G(x) = \frac{1}{\sqrt 5} ((1-\frac{1 + \sqrt{5}}{2}x) ^ {-1} - (1-\frac{1-\sqrt{5}}{2}x)^{-1})

G(x)=15(i=0(1+52x)ii=0(152)i)G(x) = \frac{1}{\sqrt 5}(\sum\limits_{i=0}^ \infty (\frac{1+\sqrt{5}}{2} x) ^ i - \sum\limits_{i=0}^\infty(\frac{1-\sqrt{5}}{2})^i)

G(x)=i=015((1+52)i(152)i)xiG(x) = \sum\limits_{i=0}^\infty \frac{1}{\sqrt 5}((\frac{1+\sqrt{5}}{2}) ^ i - (\frac{1-\sqrt{5}}{2})^i)x^i

所以我们就得到了斐波那契数列的通项公式:

fi=15((1+52)i(152)i)f_i = \frac{1}{\sqrt 5}((\frac{1+\sqrt{5}}{2}) ^ i - (\frac{1-\sqrt{5}}{2})^i)

注: i=0xi=11x\sum\limits_{i=0}^\infty x^i = \frac{1}{1 - x}

回到形式幂级数

见上

指数型母函数

排列组合

分析题目,假设有 33 种 物品 A,B,CA,B,C , 数量分别为 2,3,12,3,1 ,即{A,A,B,B,B,C}\{A,A,B,B,B,C\} ,任选两件物品,则排列是 {AA,AB,BA,AC,CA,BB,BC,CB}\{AA,AB,BA,AC,CA,BB,BC,CB\} ,共 88 种。

针对这个例子,直接给出指数型母函数的解法,我相信你们一定能够理解

G(x)=(1+x1!+x22!)(1+x1!+x22!+x33!)(1+x1!)G(x) = (1 + \frac{x}{1!} + \frac{x^2}{2!})(1+\frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!})(1+\frac{x}{1!})

G(x)=1+3x+4x2+196x3+1912x4+12x5+112x6G(x) = 1+3x + 4x^2 + \frac{19}{6}x^3+\frac{19}{12}x^4 + \frac{1}{2}x^5 + \frac{1}{12} x^6

G(x)=1+3x1!+8x22!+19x33!+38x44!+60x55!+60x66!G(x) = 1 + \frac{3x}{1!} + \frac{8x^2}{2!} + \frac{19x^3}{3!} + \frac{38x^4}{4!} + \frac{60x^5}{5!}+ \frac{60x^6}{6!}

公式的最后一行隐藏了答案,例如 19x33!\frac{19x^3}{3!}x3x^3 的幂 33 表示选 33 个物品,其系数(此处指分母上方) 1919 表示有 1919 种排列。

公式分析:公式写成 (x21!+x22!+x23!)(\frac{x^2}{1!} + \frac{x^2}{2!} + \frac{x^2}{3!}) 的形式,实际上是在处理排列 (要是这都理解不了,排列组合白学了)

为了更容易理解,以可以写成 (1x00!+1x11!+1x22!)(\frac{1x^0}{0!} + \frac{1x^1}{1!} + \frac{1x^2}{2!})

+1x00!\frac{1x^0}{0!},不选 AA 的排列有 11 种,即 {ϕ}\{\phi\}

+1x11!\frac{1x^1}{1!},选一件 AA 的排列有 11 种,即 {A}\{A\}

+$ \frac{1x^2}{2!}$ ,选两件 AA 的排列有 11 种,即 {A,A}\{A,A\}

本题代码与回到形式幂级数相似,请自行编写,需要看的私信找我。

Catalan 数

给定 nn00nn11 ,它们按照某种序列排成长度为 2n2n 的序列,满足任意前缀 00 的个数都不少于 11 的个数,序列的数量有:

Catn=C2nnn+1Cat_n = \frac{C_{2n}^n}{n+1}

裸题

Catalan数的公式,生成函数刚讲完,自行推导吧

洛必达法则

均摊 O(1)O(1) 的解法

CatnCat_n 表示 卡特兰数的第 nn 项,由公式,得 Catn=C2nnn+1Cat_n = \frac{C_{2n}^n}{n+ 1},同理,设 Catn1Cat_{n-1} 表示卡特兰数的第 n1n - 1 项,即为 Catn1=C2n2n1nCat_{n- 1} = \frac{C_{2n-2}^{n-1}}{n}

设:

Catn=Catn1kCat_n = Cat_{n - 1} \cdot k

C2nnn+1=C2n2n1nk\frac{C_{2n}^{n}}{n+1} = \frac{C_{2n-2}^{n-1}}{n} \cdot k

A2nnn!n+1=A2n2n1(n1)!nk\frac{\frac{A_{2n}^n}{n!}}{n+1} = \frac{\frac{A_{2n-2}^{n-1}}{(n-1)!}}{n} \cdot k

A2nn(n+1)!=A2n2n1n!k\frac{A_{2n}^n}{(n+1)!} = \frac{A_{2n-2}^{n-1}}{n!} \cdot k

A2nnn+1=A2n2n1k\frac{A_{2n}^n}{n+1} = A_{2n-2}^{n-1} \cdot k

k=A2nnn+1×1A2n2n1k = \frac{A_{2n}^n}{n+1} \times \frac{1}{A_{2n-2}^{n-1}}

k=(2n)(2n1)(2n2)(2nn+1)n+1×1(2n2)(2n3)(2n4)(2n2n+1+1)k = \frac{(2n)(2n-1)(2n-2) \cdots (2n - n + 1)}{n+1} \times \frac{1}{(2n-2)(2n-3)(2n-4) \cdots (2n-2-n+1+1)}

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

k=4n2n+1k = \frac{4n-2}{n+1}

Catn=Cat1×i=2n4i2i+1Cat_n = Cat_1 \times \prod\limits_{i=2}^{n} \frac{4i-2}{i+1}

Catn=i=2n4i2i+1Cat_n = \prod\limits_{i=2}^{n} \frac{4i-2}{i+1}

例题

图片.png