基础知识

1.加法原理与乘法原理

加法原理：

如果一件做一件事的方法可以分为$n$个互不相同的类，并且其中的第$i$类有$m_i$种方法

那么完成这件事一共有$\sum\limits_{i = 1}^n m_i$种方法

乘法原理：

如果一件事要分$n$步，并且其中的第$i$步有$m_i$种方法

那么完成这件事一共有$\prod\limits_{i = 1}^n m_i$种方法

2.无重复的排列组合

排列：

从$n$个元素中，有序地取出$m$个元素称作$n$个数中取$m$个数的排列

记为$P_n^m$，或者$A_n^m$

由乘法原理，可以得到$P_n^m = \frac{n!}{(n - m)!}$

组合：

从$n$个元素中，无序地取出$m$个元素称作$n$个数中取$m$个数的组合

记做$C_n^m$，并且有$C_n^m = P_n^m * \frac{1}{m!} = \frac{n!}{m!(n- m)!}$

3.斯特林数

第一类斯特林数：

把$n$个不同的小球放进$m$个相同的圆排列，记为$s(n, m)$

$s(n + 1, m) = s(n, m - 1) + n * s(n, m)$

第二类斯特林数：

把$n$个不同的小球放进$m$个相同的盒子，记为$S(n, m)$

$S(n + 1, m) = S(n, m - 1) + m * S(n, m)$

4.二项式定理

$$(a + b)^n = \sum\limits_{i = 0}^n a^i b^{n - i} \binom{n}{i}$$

常用的二项式定理的其他形式：

$$(1 + 1)^n = 2^n = \sum\limits_{i = 0}^n * \binom{n}{i}$$

$$(1 - 1)^n = 0 = \sum\limits_{i = 0}^n (-1)^i * \binom{n}{i}$$

$$(2 - 1)^n = 1 = \sum\limits_{i = 0}^n 2^i * (-1)^{n - i} * \binom{n}{i}$$

$$(2 + 1)^n = 3^n = \sum\limits_{i = 0}^n 2^i * \binom{n}{i}$$

$$(1 + x)^n = \sum\limits_{i = 0}^n x^i * \binom{n}{i}$$

5.卡特兰数

对于给定的长为$n$的入栈序列，对应的可能的出栈数列的方案数

记做$C_n$

$C_n = C(2n, n) - C(2n, n - 1)$

$C_n = \frac{C(2n, n)}{n + 1}$

$C_n = C_{n - 1} * \frac{4n - 2}{n + 1}$

$C_n = \sum\limits_{i = 0}^{n - 1} C_i * C_{n - i - 1}$

6.容斥原理

公式有点难打，就不打了，应该都知道吧...

还有一个排斥原理，跟容斥原理很相近

（容斥原理其实是一种套路）

基础知识点差不多就这么多吧

只要你够强，什么都可以推出来的...

通过大量的练习来锻炼计数的能力吧

练习

部分题目是口胡的，如果发现不对请指出

T1.忐忑子集

如果$\{1, 2, ..., 9\}$的某个非空子集中所有元素之和是3的倍数，则称该子集为忐忑子集，试问有多少忐忑子集

爆搜一下就出来了

让我们先来看看数学组的方法：

如果$\{1, 2, ..., 9\}$的某个非空子集是忐忑子集，那么它的补集也是忐忑子集.

因此，我们只需考虑元素$\leqslant 4$的忐忑子集的个数.

只有1个元素的忐忑子集有$3$个

两数之和被3整除的充要条件是两个数被3除的余数只能是$(0, 0), (1, 2)$

而被$3$除余数为$0, 1, 2$的各有$3$个，因此含$2$个元素的忐忑子集的个数为$\binom{3}{2} + \binom{3}{1} * \binom{3}{1} = 12$

含有3个元素只可能是$(0, 0,0 ), (1, 1, 1), (2, 2, 2), (0, 1, 2)$，因此有${\binom{3}{1}}^3 + 3 * \binom{3}{3}$种方案

含有4元素同理只可能是$(0, 0, 1, 2), (1, 1, 1, 0), (0, 2,2,2), (1, 1, 2, 2)$，对应有$42$种方案

全集也是一个忐忑集合

因此最终有$2(3 + 12 + 30 + 42) + 1 = 175$种

非常漂亮的思路

下面我们再看看信息组的做法...

设$f[i][0 / 1/ 2]$表示在集合$\{1, 2..., i\}$中和模3的余数为$0, 1, 2$的子集有多少个

那么每次新增$i + 1$时，考虑选或不选转移即可

复杂度$O(n)$

#include <cstdio>
using namespace std;

int f[20][3];

int main() {
    f[1][0] = 1; f[1][1] = 1;
    for(int i = 1; i <= 10; i ++)
    for(int j = 0; j <= 2; j ++) {    
        f[i + 1][j] += f[i][j];
        f[i + 1][(i + 1 + j) % 3] += f[i][j];
    }
    printf("%d\n", f[9][0] - 1);
    return 0;
}

简单多了，不是吗....

那么，我们能做到$O(1)$吗？答案是不可以的（其实是$O(\log n)$）

下面的$i / 3$默认下取整

当$i\;mod\;3 = 0$时，$f[i][0 / 1 / 2]$分别为$\frac{2^i + 2*2^{i / 3}}{3}, \frac{2^i - 2^{i / 3}}{3}, \frac{2^i - 2^{i / 3}}{3}$

当$i \;mod\;3 = 1$时，$f[i][0 / 1/ 2]$分别为$\frac{2^i + 2^{i / 3}}{3}, \frac{2^i + 2^{i / 3}}{3}, \frac{2^i - 2*2^{i / 3}}{3}$

当$i\;mod\;3 = 2$时，$f[i][0 / 1 / 2]$分别为$\frac{2^i + 2*2^{i / 3}}{3}, \frac{2^i - 2^{i / 3}}{3}, \frac{2^i - 2^{i / 3}}{3}$

快乐矩乘不就完事了

T2.运动会

安排$n$名同学参加$m$个运动项目，要求甲乙两同学不参加同一项目，且每个项目都有人参加，每个人只参加一个项目，求满足要求的不同方案数

补集转化

首先，$n$个不同的人放进$m$个相同的盒子的方案数为$S(n, m)$，即第二类斯特林数（百度百科？）

$n$个不同的人放进$m$个不同的盒子的方案数记做$f(n, m) = S(n, m) * m!$

暂时不考虑甲乙同学，那么有$f(n, m)$种可能

再考虑甲乙同学，把两个人看做一个整体，那么方案数有$f(n - 1, m)$种

最终答案即为$f(n, m) - f(n - 1, m)$

复杂度$O(n^2)$

组合数学学习笔记

原文：https://www.cnblogs.com/reverymoon/p/9499304.html