C1 排列組合

S0 計數原理

1）加法原理：$\mathbb{S}={\mathbb{S}}_1+{\mathbb{S}}_2+?+{\mathbb{S}}_{\mathbb{k}},{\mathbb{S}}_i\cap {\mathbb{S}}_j=??|\mathbb{S}|=\sum _i|{\mathbb{S}}_i|$

2）減法原理：$\mathbb{U}=\mathbb{S}+\mathbb{A},\mathbb{S}\cap \mathbb{A}=??|\mathbb{S}|=|\mathbb{U}|?|\mathbb{A}|$

3）乘法原理：$|\mathbb{A}\times \mathbb{B}|=|\mathbb{A}|\times |\mathbb{B}|,\mathbb{A}、\mathbb{B}$ 的集合特征不應當有依賴關系

• 技巧：
  • 約束性強的元素先分層
  • 不相鄰問題：隔板法；減法（捆綁使之相鄰）

4）除法原理：$\mathbb{A}$ 中每 $k$ 個元素具備相同特征，則 $|\mathbb{S}|=|\mathbb{A}|/\mathbb{k}$

S1 排列與組合

1）排列：順序有關計數

• $n$ 元集 $r$ 線性排列個數：$P(n,r)=A_n^r=\frac{n!}{(n?r)!}$

  • 循環排列個數：$P(n,r)/r=\frac{n!}{r(n?r)!}$

    圓桌 ≠ 項鏈：順逆時針前者不同后者相同

  • 遞推：$A_n^k=n{A}_{n?1}^{n?1}=A_{n?1}^k+k{A}_{n?1}^{k?1}$

• 無限重 $k$ 元多重集 $r$ 線性排列：$k^r$

  循環排列：$\frac{1}{r}\sum _{d|r}?(\frac{r}{d})k^d$

• 有限 $k$ 元多重集，重數為 $n_1,n_2,?,n_k$，線性排列數： $\frac{n!}{n_1!n_2!?n_k!}$

  • 證明：

    法一：$A_n^{n_1}{A}_{n?n_1}^{n_2}{A}_{n?n_1?n_2}^{n_3}?A_{n?n_1???n_{k?1}}^{n_k}=n!/{\prod }_i{n}_i!$

    法二：$n$ 個元素指派到 $k$ 個不同部分

  • $n$ 個不同元素分配到 $k$ 個容量為 $n_1,n_2,?,n_k$ 的盒子，不計盒子順序：僅當 $n_1=?=n_k$ 成立 $\frac{n!}{k!n_1!n_2!?n_k!}$

  • 生成方式：$g(x)=(1+x_1+x_1^2+?+x_1^{n_1})(1+x_1+x_1^2+?+x_1^{n_2})?$

2）組合：順序無關計數

• $n$ 元集 $r$ 組合個數：$C(n,r)=C_n^r=\frac{n!}{(n?r)!}$

• 無限 $k$ 元多重集 $r$ 組合：$C_{r+k?1}^r$$=C_{r+k?1}^{k?1}$

  即 $\sum _{i=1}^k{x}_i=r,x_i\ge 0$ 的解數 $a_r$

  組合意義解法：使用隔板法解決生成函數法：$g(x) = \frac{1}{(1-x)^k}=\sum\limits_{r=0}^\infin a_r x^r$（[負二項式系數]()）

• 有限 $k$ 元多重集，重數為 $n_1,n_2,?,n_k$，$r$ 組合：

• 計算無限重情況下的組合數 $\mathbb{S}$
• 將無限重換成有限重，計算 $x_i\ge n_i+1$ , $\sum _{i=1}^k{x}_i=r$ 的組合數 ${\mathbb{A}}_i$
• 由容斥原理，所求為 $\underset{i=1}{\overset{n}{?}}\overline{A_i}$

思路：第一層——有序無序，第二層——是否有重復元素

S2 二項式系數

1）起源：帕斯卡三角形

1
1 1
1 2 1
1 3 3 1
……

2）組合數-格路徑意義：從 (0,0) 到 (n,k)，限制每次只能到正下或斜右下，路徑總數

3）二項式定理：$(x+y{)}^n=\sum _{k=0}^n{C}_n^k{x}^k{y}^{n?k}$

• 多項式定理：$(x_1+x_2+?+x_k{)}^n=\sum (\genfrac{}{}{0ex}{}{n}{n_1{n}_2?n_k})x_1^{n_1}{x}_2^{n_2}?x_k^{n_k}$
  • 多項式系數：$\left(\genfrac{}{}{0ex}{}{n}{n_1{n}_2?n_k}\right)=\frac{n!}{n_1!n_2!?n_k!}$
  • $\left(\genfrac{}{}{0ex}{}{n}{n_1{n}_2?n_k}\right)=\left(\genfrac{}{}{0ex}{}{n?1}{n_1?1n_2?n_k}\right)+\left(\genfrac{}{}{0ex}{}{n?1}{n_1{n}_2?1?n_k}\right)+?+\left(\genfrac{}{}{0ex}{}{n?1}{n_1{n}_2?n_k?1}\right)$
• 廣義二項式系數：$C_a^k=?\begin{array}{ll}\frac{\prod _{i=0}^{k?1}(a?k)}{k!}& k\ge 1\\ 0& k=0\end{array}$
  • 牛頓二項式定理：$0<|x|<|y|,(x+y{)}^a=\sum _{k=0}^{\infty }{C}_a^k{x}^k{y}^{n?k}$
  • 負二項式系數：$C_{?n}^k=(?1{)}^k{C}_{n+k?1}^k$

    • 負二項分布：$\frac{1}{(1?px{)}^n}=\sum _{k=0}^{\infty }{C}_{?n}^k(?px{)}^k=\sum _{k=0}^{\infty }{C}_{n+k?1}^k(px{)}^k$

      第 $n$ 次成功前失敗次數的分布

4）組合數恒等式：

• $C_n^r=C_n^{n?r}$
• $\frac{r}{n}{C}_n^r=C_{n?1}^{r?1}$
• $\sum _{k=0}^n{C}_n^k=2^n$
  • $$$\sum _{k=0}^{n}k{C}_n^k=n{2}^{n?1}$
  • $\sum _{k=0}^{?n/2?}{C}_n^{2k+1}=\sum _{k=0}^{?n/2?}{C}_n^{2k}=2^{n?1}$
  • $\sum _{k=0}^n(C_n^k{)}^2=C_{2n}^n$
    • $\sum _{k=0}^n{C}_{m_1}^k{C}_{m_2}^{n?k}=C_{m_1+m_2}^n$(Vandemonde卷積公式)
• $C_n^k=C_{n?1}^k+C_{n?1}^{k?1}$ (Pascal公式)
  • $C_{n+1}^{p+1}=\sum _{k=0}^n{C}_k^p=\sum _{k=0}^n{C}_k^{k?p}$
  • $C_{r+k+1}^k=\sum _{i=0}^k{C}_{r+i}^i,r\in R$
• $C_n^m{C}_m^k=C_n^k{C}_{n?m}^{m?k}$

5）單峰性：$C_n^0<?<C_n^{?n/2?}=C_n^{?(n+1)/2?}>?>C_n^n$

S3 偏序

1）反鏈：$n$ 元素集 $\mathbb{S}$ 冪集的子集 $\mathcal{A}$，元素互不包含；

• Sperner 定理：$n$ 元集的任何反鏈至多包含 $C_n^{?n/2?}$ 個集合；

  記 ${\mathbb{A}}_k$ 為含有 $k$ 個元素的子集，則最大反鏈由所有 $\{\begin{array}{ll}{\mathbb{A}}_k& n=2k\\ {\mathbb{A}}_{k?1}={\mathbb{A}}_{k+1}& n=2k?1\end{array}$ 構成

2）鏈：$n$ 元素集 $\mathbb{S}$ 冪集的子集 $\mathcal{A}$，且構成其上一個全序 <$\mathcal{A},?$>

• 最大鏈：包含各種大小的集合各一個
  • 若 $|\mathbb{K}|=k$ 則包含 $\mathbb{K}$ 的最大鏈個數 $k!(n?k)!$

3）命題：反鏈與鏈至多只有一個公共元素 由定義易得

4）推廣：若 <$\mathbb{X},\le$>是有限偏序集：

• 定義推廣：
  • 鏈與反鏈：$\mathbb{X}$ 的子集，反鏈中任意元素不可比，鏈中任意元素可比
• 性質：

  • $\mathbb{X}$ 分成反鏈的個數的上確界 = 是最大鏈長度

  • $\mathbb{X}$ 分成鏈的個數的上確界 = 最大反鏈大小(Dilworth 定理)

    <$\mathcal{P}(\mathbb{X}),?$>上的鏈剖分的歸納生成

    假設 $\mathbb{X}_n = \{1,2,\cdots,n\}$ 顯然有 $\mathbb{X}_1$ 的鏈剖分：$\varnothing \sube \{1\}$ 對 $\mathbb{X}_{n-1}$ 的每一條鏈 $\mathbb{A}_1\sube \mathbb{A}_2 \sube \cdots \sube \mathbb{A}_k$：$\mathbb{X}_n$ 的鏈剖分由兩部分組成：$\mathbb{A}_1\sube \mathbb{A}_2 \sube \cdots \sube \mathbb{A}_k \sube \ \mathbb{A}_k\cup \{n\}$$\mathbb{A}_1 \cup \{n\} \sube \mathbb{A}_2 \cup \{n\}\sube \cdots \sube \mathbb{A}_{k-1} \cup \{n\}，k\ge 2$

    至此給出了 Sperner 定理的一個構造性證明

總結

以上是生活随笔為你收集整理的组合数学$1排列组合的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。