「CSP-S 数学」排列与组合.md

发表于 | 更新于 | 分类于 ，

计数原理、排列、组合、递推关系、等差数列求和公式、自然数平方和公式、二项式定理。

计数原理

加法原理

做一件事有$n$种途径，每种途径有$p_i$个不同的方案，则做这件事的方案数为
$$
\sum_{i=1}^n p_i
$$

乘法原理
做一件事有 个步骤，每个步骤有 个不同的方案，则做这件事的方案数为

容斥原理
统计多个集合的并的元素数量：先加上所有集合的元素的元素数量，再减去『多加的』每两个集合相交的元素数量，再加上『多减的』每三个集合相交的元素数量 ……

即等式左边是多个集合的并的元素数量，等式右边每一项是几个几何的交的元素数量，每一项的符号取决于元素数量的奇偶。

排列
全排列
把 个元素按照不同顺序排列，设总方案数为 （定义 ），考虑第一个元素摆放的位置，得出公式

即 。

普通排列
从 个元素中取 个，按照不同顺序排列，设总方案数为 ，每次选一个数，第一次有 种选择，第二次有 种选择，直到第 次有 种选择，即

将上式与 对比，缺少 及之后的项，即

有重复元素的全排列
从 种元素，第 种有 个，设 ，为了保证答案不重复，可以先求出 ，再除去每种元素重复的情况，即

组合
组合数
从 n 个元素中选择 k 个，顺序无关，设总方案数为 。把排列数 看做先从 n 各种选择 k 个元素，再对 k 个元素做全排列，即

移项得

组合数的性质
全选或全不选只有一种方案。

选择 个拿走相当于选择 个留下。

考虑最后一个选还是不选（Pascal 公式，常用来递推计算组合数表）。

可重复选择的组合
从 n 种无限多的元素中选择 k 个，共有 种方案。

组合数的计算
组合数表
用 Pascal 公式递推，组合数太大要开高精度或者取模。

BigInt combo[MAXN + 1][MAXN + 1];

inline void makeComboTable() {
for (int i = 1; i <= MAXN; i++) {
combo[i][0] = combo[i][i] = 1;
for (int j = 1; j < i; j++){
combo[i][j] = combo[i - 1][j] + combo[i - 1][j - 1];
}
}
}

inline BigInt &C(int n, int k) {
return combo[n][k];
}
单个计算
书上有用 double 来算的，因为中间乘法 long long 可能会溢出，不知道那样会不会损失精度。

long long C(long long n, long long k) {
long long result = 1;
for (int i = 1; i <= k; i++) {
result = result * (n - i + 1) / i;
}
return result;
}
递推关系
Fibonacci 数列
楼梯上共有 个台阶，一次可以走一个或两个，总方案数为

边界为

Catalan 数
给定一个凸 边形，用 条不相交的直线将它剖分成 个三角形，设方案总数为 。

对每个顶点编号，第 个顶点编号为 。作三角形 （），该三角形左边是一个 边形，右边是一个 边形，即

公式
等差数列
设数列 对于任意的 满足 ，则有

求和公式为

自然数平方和

不会证。

二项式定理

「随想」Welcome, 2019

发表于 | 更新于 | 分类于 ，


2019转眼三个月就过去了，有点时光飞逝而过的感觉，在工作学习生活上有一些感想，记录一下20190519。
2020已经过了大半，这一年发生了许多事情，新冠疫情，水灾，中美对抗，中国挺过来了，这一切终将过去，在历史
上划上浓重的一笔！

benny

发表于 | 更新于

Markdown 基本语法

1.1 标题

Markdown中包含了6级的标题，每级标题的字号是不一样的，由1-6递减，分别为#，##，…,######. 一二级标题自带分格线

1.1.1 二级标题

1.2 段落与分隔线

1.2.1 段落

在Markdown中写作一个段落的方法很简单，我们使用一个空行来表示就好了

1.2.2 分隔线

1.3 粗体及斜体

**文字** 显示为粗体

*文字* 显示为斜体

今天是个不一样的_日子_

1.4 引用代码

程序员在blog中添加代码是最经常不过的了，可以通过如下的方式添加一段代码，也可以指定代码的种类。
使用首尾各三个```。在开头的三个```后可以添加语言名称

1.5 添加图片和链接

  • 添加链接，使用两个中括号来表示，前一个中括号为链接说明，后一个中括号为链接地址。格式如下：[]()

计蒜客 30999

  • 添加图片，在添加链接的的前一个中括号前添加一个!(当然是半角的)号。格式：！[]()

c

d

1.6 有序列表和无序列表

有序列表 数字.空格
无序列表 * 空格

  1. 工作
  2. 学习
  3. 生活
  • 工作
  • 学习
  • 生活

1.7 任务列表

购物清单

  • 一次性水杯
  • 西瓜
  • 豆浆
  • 可口可乐
  • 小茗同学

Markdown 高级语法

2.1 表格

Header1 Header2 Header3
item 1 1. one
2. two
3. three		 50
item 2 4. four
5. five
6. six		 60

2.2 流程图

Github上的语法说明：Markdown流程图说明

1
st=>start: Start

  春天来了，又到了万物复苏的季节。

1
2
3
4
5
#include <cstdio>
int main()
{
    return 0;
}

这是一个示例图片。

图片显示在 N 段文字的右边。

N 与图片高度有关。

刷屏行。

刷屏行。

到这里应该不会受影响了，本行应该延伸到了图片的正下方，所以我要足够长才能确保不同的屏幕下都看到效果。

Header1 Header2
item 1 1. one
2. two
3. three

$9 = 3 \times 3$

bbb $ E = mc ^ 2$
$$ A=a \bullet i+b \bullet j=[i,j] \bullet [a;b]=基\bullet坐标 \tag{3}$$
$$
E=mc^2
$$

$$
\sum_{i=0}^n i^2 = \frac{(n^2+n)(2n+1)}{6}
$$