组合数学笔记

作者: 壮志_凌云 | 来源:发表于2019-10-11 20:53 被阅读0次

组合数学笔记
笔记
组合数学1-漫谈组合数学
组合数学
组合数学
组合数学
组合数学
程序员的数学 - 读书笔记目录
程序员的数学 - 归纳与递归
程序员的数学 - 排列组合

0001：从 $n$ 个不同的元素中取 $r$ 个可重复元素的组合数为： $\left(\begin{array}{c}n+r-1 \\r\end{array}\right)$

方程 $x_1 + x_2 + \dots + x_n = r, n \in N, r \in Z^+$ 的非负整数解的个数为： $\left(\begin{array}{c}n+r-1 \\r\end{array}\right)$

0002：~~从 $n$ 个不同的元素中取 $r$ 个最多可出现 $k(1 \leq k \leq r)$ 次元素的组合数为： $\left( \begin{array}{c} n+r-\lceil \frac{r}{k} \rceil \\r\end{array}\right)$~~

~~抛掷 $n$ 个骰子，点数之和为 $r, n \leq r \leq 6n$ 的组合数为： $\left(\begin{array}{c} r-\lceil \frac{r-n}{5} \rceil \\ r-n \end{array}\right)$~~

0003：从 $n$ 个不同的元素中取 $r$ 个不相邻元素的组合数为： $\left(\begin{array}{c}n-r+1 \\r\end{array}\right)$

0004：组合数公式： $\left(\begin{array}{c}n \\r\end{array}\right) = \left(\begin{array}{c}n - 1 \\ r \end{array}\right) +\left(\begin{array}{c}n - 1 \\ r - 1 \end{array}\right), n - 1 \geq r$ ，由此公式可推出：

$\left(\begin{array}{c}n + 1 \\ r \end{array}\right) = \left(\begin{array}{c}n \\ r \end{array}\right) +\left(\begin{array}{c}n - 1 \\ r - 1 \end{array}\right) + \dots +\left(\begin{array}{c}n - r + 1 \\ 1 \end{array}\right) +\left(\begin{array}{c}n - r \\ 0 \end{array}\right) = \sum_{i = 0}^{r} \left(\begin{array}{c}n - i \\ r - i \end{array}\right), n \geq r$

$\left(\begin{array}{c}n + 1 \\ r + 1 \end{array}\right) = \left(\begin{array}{c}n \\ r \end{array}\right) +\left(\begin{array}{c}n - 1 \\ r \end{array}\right) + \dots +\left(\begin{array}{c} r + 1 \\ r \end{array}\right) +\left(\begin{array}{c} r \\ r \end{array}\right) = \sum_{i = 0}^{n - r} \left(\begin{array}{c}n - i \\ r \end{array}\right), n \geq r + 1$

0005：组合数公式： $\left(\begin{array}{c}n \\ l \end{array}\right) \left(\begin{array}{c}l \\ r \end{array}\right) =\left(\begin{array}{c}n \\ r \end{array}\right) \left(\begin{array}{c}n - r \\ l - r \end{array}\right), n \geq l \geq r$

0006：组合数公式：

$\left(\begin{array}{c}m + n \\ r \end{array}\right) =\left(\begin{array}{c}m \\ 0 \end{array}\right) \left(\begin{array}{c}n \\ r \end{array}\right) +\left(\begin{array}{c}m \\ 1 \end{array}\right) \left(\begin{array}{c}n \\ r - 1 \end{array}\right) +\dots +\left(\begin{array}{c}m \\ r \end{array}\right) \left(\begin{array}{c}n \\ 0 \end{array}\right) =\sum_{i=0}^r\left(\begin{array}{c}m \\ i \end{array}\right) \left(\begin{array}{c}n \\ r - i \end{array}\right), r \leq min \{ m, n\}$

由此公式可推出：

$\left(\begin{array}{c}m + n \\ m \end{array}\right) =\left(\begin{array}{c}m \\ 0 \end{array}\right) \left(\begin{array}{c}n \\ 0 \end{array}\right) +\left(\begin{array}{c}m \\ 1 \end{array}\right) \left(\begin{array}{c}n \\ 1 \end{array}\right) +\dots +\left(\begin{array}{c}m \\ m \end{array}\right) \left(\begin{array}{c}n \\ m \end{array}\right) =\sum_{i=0}^m\left(\begin{array}{c}m \\ i \end{array}\right) \left(\begin{array}{c}n \\ i \end{array}\right), n \geq m$

$\left(\begin{array}{c}2n \\ n \end{array}\right) =\left(\begin{array}{c}n \\ 0 \end{array}\right) ^2+\left(\begin{array}{c}n \\ 1 \end{array}\right)^2 +\dots +\left(\begin{array}{c}n \\ n \end{array}\right) ^2 =\sum_{i=0}^n\left(\begin{array}{c}n \\ i \end{array}\right)^2$

0007： $x, y$ 坐标系中从 $(0, 0)$ 点沿两个坐标轴方向移动到 $(m, n)$ 点的最短路径中（其中 $m < n$ ），经过的点的坐标始终满足 $x < y$ 的路径数量为：

$\frac{(m + n - 1)!}{m! n!} (n - m)$

此结论可解决下面的问题：

电影院的票价为50元， $n$ 个人持50元， $m (m \leq n)$ 个人持100元，每人只买一张票，相互之间不拆借，售票处开始营业时没有钱。能使售票顺利进行，不出现找不出钱的排队方式数量为：

$\frac{(m + n)!}{m! (n+1)!} (n + 1 - m)$

顺利售票的概率为： $1 - \frac{m}{n+1}$

最小概率为： $\frac{1}{n+1}$

0008：阶乘公式：

$\sum_{i=1}^{n} i \cdot i! = \sum_{i=1}^{n} (i+1-1) \cdot i! = \sum_{i=1}^{n} [(i+1)! - i!] = (n+1)! - 1$

$(2n)! = (2n)!!(2n-1)!! = 2^nn!(2n-1)!!$

0009：组合数函数 $f(r) = \left(\begin{array}{c}n \\r\end{array}\right), n \geq r \geq 1$ ，先递增后递减。函数在 $\frac{n-1}{2}, \frac{n+1}{2} \ (n为奇数)$ 或 $\frac{n}{2} \ (n为偶数)$ 处取得最大值。

0010：分堆排列组合数： $n$ 个有区别的小球放入 $m$ 个盒子里，每个盒子里放入 $k_i, i =1,2, \dots ,m$ 个小球，其中 $\sum_{i=1}^m k_i = n$ ，则：

若盒子是有标志的，则分堆方案数为： $\frac{n!}{ \prod_{i=1}^m k_i! }$ ，且有：

$\sum_{k_1 + k_2 + \dots + k_m = n} \frac{n!}{ \prod_{i=1}^m k_i! } = m^n$ （每个小球放入时有 $m$ 个选择）

若盒子是无标志的，则分堆方案数为： $\frac{n!}{ m! \prod_{i=1}^m k_i! }$

0011：证明： $n^2, n \in N$ 的正因数的个数是奇数；

方法一：

根据算术基本定理，必存在质数 $P_1,P_2,\dots,P_m$ 和非负整数 $a_1,a_2,\dots,a_m$ ，使：

$n = \prod_{i=1}^m P_m^{a_m}, \ \ \ N = n^2 = \prod_{i=1}^m P_m^{2a_m}$

可以看出 $N$ 可以分解为 $m$ 个质因数幂的乘积，故 $N$ 的因数个数为：

$\prod_{i=1}^m (2a_m+1)$ ，这是一个奇数，证毕。

方法二：

设 $a, 1 \leq a < n$ ，是 $n^2$ 的一个正因数，则存在自然数 $b, n < b \leq n^2$ ，满足 $n^2 = a * b$ 。

可以看出 $a, b$ 成对出现，这样的正因数有偶数个。

$n$ 也是 $n^2$ 的一个正因数，所以所有正因数的总个数是奇数。

证毕。

0012：证明：

$0*0! + 1*1!+2*2!+\dots+(n-1)*(n-1)! = \sum_{j=0}^{n-1} (j*j!) = n!-1,n \ge 1$

使用母函数的证明方法：

设 $a_n = \sum_{j=0}^{n-1} (j*j!)$ ，则有递推关系：

$a_n - a_{n-1} = (n-1)*(n-1)!, n \ge 2, a_1 = 0$ ；

设 $b_n = \frac{a_n}{n!}$ ，可得递推关系：

$nb_n - b_{n-1} = n-1, n \ge 2, b_1 = 0$ ；

设 $b_n$ 的母函数为： $G(x) = b_1x+b_2x^2+\dots+b_nx^n+\dots$

根据 $b_n$ 的递推关系可得：

$\frac{dG(x)}{dx} - G(x) = x(1-x)^{-2},G(0) = 0$

解微分方程可得： $G(x) = (1-x)^{-1} - e^x$

故， $b_n = 1-\frac{1}{n!}$ ， $a_n = b_n*n! = n! - 1$

证毕。

0013：证明：所有的正整数 $n$ 都可以表示为（下标）不同的 Fibonacci 数之和。

使用数学归纳法证明， $n = 1$ 时命题显然成立，假设 $n = k$ 时命题成立，即：

存在自然数 $1 \leq l_1 < l_2 < \dots <l_m$ ，满足： $k = \sum_{j=1}^m F_{l_j}$ ，则：

$k+1 = F_1 + F_{l_1} + F_{l_2} + \dots + + F_{l_m}$ ，分析如下：

若 $l_1 > 1$ ，则命题成立；若 $l_1 = 1$ ，则 $l_2 \geq 2$ ，且：

$k+1 = F_1 + F_2 + F_{l_2} + F_{l_3} + \dots + + F_{l_m}$

若 $l_2 > 2$ ，则命题成立；若 $l_2 = 2$ ，则 $l_3 \geq 3$ ，且：

$k+1 = F_3 + F_2 + F_{l_3} + F_{l_4} + \dots + + F_{l_m}$

若 $l_3 > 3$ ，则命题成立；若 $l_3 = 3$ ，则 $l_4 \geq 4$ ，且：

$k+1 = F_4 + F_3 + F_{l_4} + F_{l_5} + \dots + + F_{l_m}$

以此类推，将这样的分析进行下去，直到：

$k+1 = F_{m} + F_{m-1} + F_{l_m}$ ，其中， $l_m \geq m$ ，则：

若 $l_m > m$ ，则命题成立；若 $l_m = m$ ，则有：

$k+1 = F_{m + 1} + F_{m}$ ，此时命题成立。

由上可得，当 $n = k + 1$ 时命题也成立。

证毕。

0014：设 $F_n$ 是斐波那契数列， $a,b,c$ 是正整数，证明：

$F_{a+b+c+3} = F_{a+2} ( F_{b+2} F_{c+1} + F_{b+1} F_c) + F_{a+1} ( F_{b+1} F_{c+1} + F_b F_c )$

解：利用递推关系 $F_n = F_{n-1} + F_{n-2}$ 可化简等式的右边为：

$F_{a+2} ( F_{b+2} F_{c+1} + F_{b+1} F_c) + F_{a+1} ( F_{b+1} F_{c+1} + F_b F_c )$

$= F_{a+2} F_{b+2} F_{c+2} + F_{a+1} F_{b+1} F_{c+1} - F_a F_b F_c$

将通项公式 $F_n = \frac{\alpha^n - \beta^n}{\sqrt{5}}, \alpha = \frac{1 + \sqrt{5}}{2}, \beta = \frac{1 - \sqrt{5}}{2}$ 代入上式，并利用关系式

$\alpha + \beta = 1, \alpha \beta = -1, 1 + \alpha^2 \beta = \beta, 1 + \alpha \beta^2 = \alpha$ 可得：

$F_{a+2} F_{b+2} F_{c+2} + F_{a+1} F_{b+1} F_{c+1} - F_a F_b F_c$

$= \frac{1}{5 \sqrt{5}} ( \alpha^{a+b+c+6} + \alpha^{a+b+c+3} - \alpha^{a+b+c} - \beta^{a+b+c+6} - \beta^{a+b+c+3} + \beta^{a+b+c})$

$= \frac{1}{5} ( F_{a+b+c+6} + F_{a+b+c+3} - F_{a+b+c} )$

$= F_{a+b+c+3}$

证毕。

0015：将整数序列 $\{1,2,\dots,2^8\}$ 任意剖分为 $P$ 和 $Q$ 两部分，证明这两部分中的一个必包含三个构成等比关系的数。

解：使用反证法。假设 $P$ 和 $Q$ 中都不包含能够构成等比关系的数，则 $1,2^4,2^8$ 这3个数必不能属于同一部分，下面分别讨论之。

1. 若 $1, 2^4 \in P$ ，则 $2^8 \in Q$ ，则有：

$\implies 2^2,2^8 \in Q$

$\implies 1, 2^4,2^5 \in P$

$\implies 2^2,2^3,2^6,2^8 \in Q$

$\implies 1,2, 2^4,2^5,2^7 \in P$

$\implies 矛盾$

2. 若 $2^4,2^8 \in P$ ，则 $1 \in Q$ ，则有：

$\implies 1, 2^6 \in Q$

$\implies 2^3,2^4,2^8 \in P$

$\implies 1, 2^2,2^5,2^6 \in Q$

$\implies 2,2^3,2^4,2^7,2^8 \in P$

$\implies 矛盾$

3. 若 $2^4 \in P$ ，则 $1, 2^8 \in Q$ ，这分两种情况来讨论。

3.1 若 $2^4,2^6 \in P$ ， $1, 2^8 \in Q$ ，则有：

$\implies 1,2^2,2^5, 2^8 \in Q$

$\implies 矛盾$

3.2 若 $2^4 \in P$ ， $1,2^6, 2^8 \in Q$ ，则有：

$\implies 2^3,2^4,2^7 \in P$

$\implies 1,2^2,2^5,2^6, 2^8 \in Q$

$\implies 矛盾$

综上，在所有情况下均推出了矛盾，所以假设不正确，命题得证。

0016：证明循环群的子群也是循环群。

证明：设 $G$ 是循环群， $x$ 是 $G$ 的生成元， $H$ 是 $G$ 的子群。

则有 $\forall p \in H, \exists i \in N, x^i = p$ ，设 $S = \{i | x^i \in H \}, k = S_{min}$

下面证明 $H$ 的所有元素都是 $x^k$ 的整数幂。

假设 $\exists m, r \in N, r < k, x^{mk+r} \in H$ ,

则有： $x^{-mk}x^{mk+r} = x^r \in H$ ，即 $r \in S$ 且 $r < k$

这与 $k = S_{min}$ 相矛盾，所以 $x^k$ 是 $H$ 的一个生成元，故 $H$ 也是循环群，命题得证。

0017：证明有限群中元素的阶能够整除群的阶。

证明：设 $G$ 为有限群， $x$ 是 $G$ 中的任意一个元素， $r = |x|, g = |G|$ 。

易证 $H = \{ x^1, x^2, \dots,x^r = e \}$ 是 $G$ 的一个子群，若任意子群的阶都能够整除群的阶，则问题就得以证明，下面对此事实进行证明。

设 $H$ 是 $G$ 的任意子群， $x, y$ 是 $G$ 的任意两个元素。

若 $x \notin H$ ，则 $xH \cap H = \oslash$

证明：假设 $xH \cap H \neq \oslash$ ，则 $\exists a, b \in H, xa = b, x = ba^{-1}\in H$ ，这与 $x \notin H$ 矛盾

$\forall x \in G, |xH| = |H|$

证明：假设 $|xH| < |H|$ ，则 $\exists a, b \in H, xa = xb, a = b$ ，这与 $a \neq b$ 矛盾

$\forall x,y \in G, xH \cap yH = \oslash，或，xH = yH$

证明：若 $xH \cap yH = \oslash$ ，则命题成立。

若 $xH \cap yH \neq \oslash$ ，则 $\exists a, b \in H, xa = yb, x = yba^{-1}, y = xab^{-1}$

$\forall p \in H, xp = yba^{-1}p \in yH, xH \subset yH$

$\forall p \in H, yp = xab^{-1}p \in xH, yH \subset xH$

故， $xH = yH$

设 $|H| = h$ , $x_1, \dots, x_{g-h} \in G - H , I = x_1H + \dots + x_{g - h}H$ ，则 $I = G - H$

证明：

$\forall x \in G - H, xH \cap H = \oslash, xH \subset G - H, I \subset G - H$

$\forall x \in G - H, \exists p \in H, y \in G - H, xp = y, x = yp^{-1} \in I, G - H \subset I$

故， $I = G - H$

综上，可得 $G = H + I = I = H + x_1H + \dots + x_{g - h}H$

设 $A_1 = H + x_1H$ ，则 $|A_1| = 2h$

设 $A_2 = H + x_1H + X_2H$ ，则 $|A_2| = 2h, or, 3h$

依次类推，可得 $|G| = |A_{g-d}| = n|H|,n >= 1$

即 $G$ 的阶是 $H$ 的整数倍，由此可以得出以下结论：

1. 有限群的任意子群的阶能够整除群的阶；

2. 有限群的任意元素的阶能够整除群的阶；

命题证明完毕。

占位符

组合数学笔记
0001：从个不同的元素中取个可重复元素的组合数为：方程的非负整数解的个数为： 0002：从个不同的...
笔记
金融学笔记：投资组合。我们常常说投资组合可以降低风险，但是很少有人知道这是有着数学原理的。 1952年，芝加哥大...
组合数学1-漫谈组合数学
1. 什么是组合数学数学发展史：初等→分析→组合组合数学：抽象代数，集合论，数论，群论，拓扑学幻方n阶幻方定义...
组合数学
把实际问题转换为数学问题，通过数学模型找出解决算法这门课重点是2和3 还没有形式化方法证明<=4
组合数学
组合数学是离散数学的一个分支。专门研究计数的问题。数学的发展历史组合数学的三大问题存在性是否存在合理的解计...
组合数学
## 加法原则与乘法原则 P17 gggg ff
组合数学
1.1 加法原则与乘法原则 P17 1.2 排列与组合 C（n,r）P（n,r）C * r! = P 1.4 模型...
程序员的数学 - 读书笔记目录
《程序员的数学》读书笔记目录 0的作用罗马计数法余数的运用逻辑运算排列组合归纳与递归
程序员的数学 - 归纳与递归
《程序员的数学》读书笔记目录 0的作用罗马计数法余数的运用逻辑运算排列组合归纳与递归归纳 induct...
程序员的数学 - 排列组合
《程序员的数学》读书笔记目录 0的作用罗马计数法余数的运用逻辑运算排列组合归纳与递归认清计数对象工具...

组合数学笔记

相关文章