pdf

1. 一個 \(n\) 個元素的集合的子集個數為 \(2^n\)。
   證明：每個數選或者不選。

2. 一個我們稱一個序列 \(\alpha=(\alpha_1,\alpha_2,\alpha_3,...,\alpha_k)\) 為 \(n\) 的一個 \(composition\)，當且僅當 \(\forall i,\alpha_i>0,\sum \alpha_i=n\)，則 \(n\) 的 \(composition\) 的個數為 \(2^{n-1}\)。
   證明：插板，\(n-1\) 個板插或者不插。

3. 一個大小為 \(k\) 的 \(composition\) 的貢獻為 \(k\)，\(n\) 的所有 \(composition\) 的貢獻之和為 \((n+1)2^{n-2}\)
   證明：把每個 \(composition\) 取反之后對應唯一對應另外一個不同的 \(composition\)，這倆的權值之和正好是 \(n+1\)，共 \(2^{n-2}\) 對這樣的 \(composition\)。

4. \(k\) 為偶數的 \(composition\) 一個有 \(2^{n-2}\) 個。
   證明：在第一個位置翻轉上面的板即可。

5. 有 \(k\) 個集合，每一個集合 \(S_1\sim S_{k}\) 都是 \(\left\{1,2,...,n\right\}\) 的子集，要求計數。

   1. \(S_1\subseteq S_{2}\subseteq \dots\subseteq S_{k}\) 。
      答案：\((k+1)^n\)，考慮每一個數最先出現的集合的編號。
   2. 所有 \(S\) 互相之間沒有交集。
      答案：\((k+1)^n\)，考慮每一個數出現在哪個位置。
   3. 所有 \(S\) 的交集為空。
      答案：\((2^k-1)^n\)，每一個數除了全都是 \(1\) 之外都行。

6. 證明組合數公式。
   排列數/階乘。

7. 證明二項式定理。
   每一個是選了 \(x\) 還是 \(y\)。

8. 從 \((0,0)\) 到 \((n,m)\) 的路徑條數。
   \(\binom{n+m}{n}\)，\(n+m\) 步中選出來 \(n\) 個向上走。

9. \(2\binom{2n-1}{n}=\binom{2n}{n}\)。
   證明：格路計數，欽定第一個走的方向。

10. \(\forall n\ge 1,\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0\) 。
    證明：二項式定理/容斥。

11. \(\sum_{k=0}^{n}\binom{x}{k}\binom{y}{n-k}=\binom{x+y}{n}\)。
    證明：從 \(x+y\) 個元素中選 \(n\) 個元素，枚舉前 \(x\) 中選了幾個。

12. \(\sum_{k=0}^n\binom{x+k}{k}=\binom{x+n+1}{n}\)。
    證明：從 \(x+n+1\) 中選擇 \(n\) 個，枚舉第一個沒選的位置即可。

13. \(\sum_{k=0}^n\binom{2k}{k}\binom{2(n-k)}{n-k}=4^n\)。
    證明：先考慮等號左邊的式子，考慮把組合數刻畫成格路計數，即我們去枚舉一個直線 \(y=x\) 上的點 \((k,k)\)，我們要數的就是對于每一個 \(k\)，計算必須經過 \((k,k)\) 的從 \((0,0)\) 走到 \((n,n)\) 的方案數，那么也就是對于每一條從 \((0,0)\) 到 \((n,n)\) 的路徑，我們定義他的權值是經過直線 \(y=x\) 的次數。
    等號右邊的式子，可以看作是 \(2^{2n}\)，也就是從 \((0,0)\) 走 \(2n\) 步的所有路徑的方案數。
    接下來考慮構造出來這樣的雙射。
    下面的步驟參考 quora博客
    現在考慮每一條路徑，我們找到他的每一個和 \(y=x\) 的交點，那么我們可以從后往前考慮每一個交點，如果我們能把這個交點之后的路徑映射到不固定終點的路徑，那么我們的工作就完成了，記 \(S(2k)\) 除起點不經過 \(y=x\) 的走 \(2k\) 步的路徑條數，那么現在我們要證明的就是 \(S(2k)=\binom{2k}{k}\)。
    所有走 \(2k\) 步且第一步走向右邊的路徑都可以劃分到這四類中：

    • \(N1\)：除了起點，不經過 \(y=x\) 的路徑。
    • \(N2\)：經過了 \(y=x\)，終點不在 \(y=x\)，向右走的次數多于向上走的。
    • \(N3\)：經過了 \(y=x\)，終點不在 \(y=x\)，向上走的次數多于向右走的。
    • \(N4\)：終點在 \(y=x\) 的路徑。
      顯然有 \(N2=N3\)，而且如果一條路徑是 \(N3\)，向上走的次數多于向右走的顯然是其充要條件，那么計數 \(N3\)，我們可以枚舉向上走了多少次。
      于是有 \(N3=\binom{2k-1}{k+1}+\binom{2k-1}{k+2}+\dots+\binom{2k-1}{2k-1}\)。
      而又有 \(N2=N3\)，把組合數稍微變換一下可以得到 \(N2=\binom{2k-1}{0}+\binom{2k-1}{1}+\dots+\binom{2k-1}{k-2}\)。
      根據定義顯然有 \(N1+N2+N3+N4=2^{2k-1}=\binom{2k-1}{0}+\binom{2k-1}{1}+\dots+\binom{2k-1}{2k-1}\)，\(N4=\binom{2k-1}{k}\)。
      于是我們就可以得到 \(N1=\binom{2k-1}{k-1}\)。
      則 \(S(2k)=2\times N1=\binom{2k}{k}\)。
      至此，我們證明了 \(S(2k)=\binom{2k}{k}\)。