1-3章节

最重要总结:

• $k$ 个球
• $n$ 个盒子(互相不一样),编号 $1,2,3, \cdots, n$

	球不可重复放到同一个盒子	球可重复放到同一个盒子
有区别的球	$\frac{n!}{(n-k)!}$	$n^k$
无区别的球	$\binom{n}{k}$	$\binom{n+k-1}{k}$

第一章 计数的基本知识

1. 集合的定义
2. 集合的基或大小
3. 定理(1) 分类加法原理
4. 定理(2) 分步乘法原理
5. 子集的集合: 幂集
6. 集合的子集数量

书没有讲的内容的补充:

1. 分类加法原理的的集合表示与证明
2. 如果一个集合的元素是由若干个互不相交的集合的元素组成的, 那么集合的大小就是各个子集的大小的和
3. 分步乘法原理的集合证明
4. 如何一个集合的元素是可分步构造得到的, 那么集合的大小就是各个步骤的大小的乘积
5. 幂集的定义
6. 子集数量的证明

课后练习

例11 :TODO

第二章 排列组合

四种基本类型的问题一: 有重排序

1. 开张日: 共有 $n$ 种口味的冰淇淋, 取 $k$ 勺冰淇淋的,顺序有区别, 问共有多少种方案?

   Open in Excalidraw

2. 把 $k$ 有区别的球放到 $n$ 有区别的盒子中, 每个盒子放任意多个球, 问共有多少种方案?

   Open in Excalidraw

四种基本类型的问题二: 无重排序

1. 从 $n$ 盒子里面取 $k$ 次球, 每个盒子一个球,球的顺序不同方案不同,问共有多少种方案?

   Open in Excalidraw

2. 把 $k$ 个有区别的球放到 $n$ 有区别的盒子中, 每个盒子只能放一个球, 问共有多少种方案?

$$P(n,k) = \frac{n!}{(n-k)!}$$

四种基本类型的问题三: 组合

1. 把 $k$ 无区别的球放到 $n$ 有区别的盒子中, 每个盒子最多放一个, 问共有多少种方案?
2. 有$n$个盒子中每个盒子中有一个没有编号球, 每个盒子取放一个球 ,不考虑顺序, 问共有多少种方案?

$$\binom{n}{k} = \frac{n!}{k!(n-k)!} \text{ 读作: n选k}$$

证明:

1. 每个球上都有编号, 编号为 $1,2,3, \cdots, k$
2. 有一个人,叫做小A,只取1 2 3,如果考虑顺序:

  1. 1 2 3
  2. 1 3 2
  3. 2 1 3
  4. 2 3 1
  5. 3 1 2
  6. 3 2 1
  共 $3!$ 种方案

2. 小$A$ 把取到的球给 小$B$,小B 把球打乱,因为他不考虑顺序,所以对于小$B$来说, 这些是一种方案

于是得到公式

$$\binom{n}{k} \cdot k! = \frac{n!}{(n-k)!} \\ \binom{n}{k} = \frac{n!}{k!(n-k)!}$$

• $n$个元素的集合A,其中含有 $k$ 个元素的子集的个数为 $\binom{n}{k}$
• 组合是一组不同对象的子集,不考虑顺序
• 组合数的递推关系
• 组合数的性质
  • $\binom{n}{k} = \binom{n}{n-k}$
  • $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$
• 同样的方式: 思考圆排列
• 一种DP问题: 走格子

第三章 星星,杠杠和多项式

四种基本类型的问题四:

1. 共有$k$个无区别的球, 每个盒子可以放任意多个球,每个盒子至少放一个球,$n \leqslant k$, 问共有多少种方案?
2. 共有$k$个无区别的球, 每个盒子可以放任意多个球, 问共有多少种方案?
3. $x + y + z = k$

把 $k$ 无区别的球放到 $n$ 有区别的盒子中, 每个盒子放任意多个球, 问共有多少种方案?