3-3. 組合

Combination Formula

  • n n 件相異物不允許重複取 r r 件組合的方法數: Crn \text{C}^n_r = C \text{C} (n n , r r ) = (nr) \dbinom{n}{r} = n(n−1)...(n−r+1)r! \dfrac{ n(n - 1)...(n - r + 1)}{r!} = n!(n−r)!r! \dfrac{n!}{(n - r)!r!} , n≥r n \ge r

    ∵ \because 組合 = 無次序排列 = Prnr! \dfrac{\text{P}^n_r}{r!}

  • n n 件相異物允許重複取 r r 件組合的方法數: (n+r−1r) \dbinom{n + r - 1}{r} = (n+r−1)!r!(n−1)! \dfrac{(n + r - 1)!}{r!(n - 1)!}

    ex. ^{ex.} 4 件相異物 A, B, C, D 無次序取 7 件作組合:

取 A B C D
AABBCCD xx xx xx xx xx xx x x
AACCCCD xx xx xxxx xxxx x x

→ \rightarrow 等同於: r r 個 x x 與 n n - 1 1 個間隔的不全相異物排列，其等價問題:

  1. r r 個相同球放入 n n 個相異箱子，允許空箱之方法數
  2. x1 x_1 + x2 x_2 + ... + xn x_n = r r 之非負整數整數解個數

→ \rightarrow Corollary: n \color{red}{n} 個箱內必有物 ⇒(n+(r−n)−1r−n) \Rightarrow \dbinom{n + (r {\color{red}{- n}}) - 1}{r {\color{red}{- n}}} = (r−1r−n) \dbinom{r - 1}{r - n} = (r−1n−1) \dbinom{r - 1}{n - 1}

  1. r r 個相同球放入 n n 個相異箱子，不允許空箱之方法數
  2. x1 x_1 + x2 x_2 + ... + xn x_n = r r 之正整數整數解個數

Example Example :
\quad x1 x_1 + x2 x_2 + ... + xn≤r x_n \le r 之非負或正整數整數解個數?
solution solution :
\quad 令 xn+1 x_{n + 1} = r r - (x1 x_1 + x2 x_2 + ... + xn x_n ) ⇒x1 \Rightarrow x_1 + x2 x_2 + ... + xn x_n + xn+1 x_{n + 1} = r r , xn+1≥ x_{n + 1} \ge (正整數: > > ) 0 0 , 其中 xn+1 x_{n + 1} 稱為鬆弛變數 (slack variable)

Theorem of Combination

(nr) \dbinom{n}{r} = (n−1r) \dbinom{n - 1}{r} + (r−1r−n) \dbinom{r - 1}{r - n}

proof:

利用組合證法，n n 個相異物取 r r 個組合，固定一物 A A

  • 不取 A A : (n−1r) \dbinom{n - 1}{r}
  • 取到 A A : (n−1r−1) \dbinom{n - 1}{r - 1}

∵ \because 「沒取到 A A 」與「有取到 A A 」為互斥事件
∴(nr) \therefore \dbinom{n}{r} = (n−1r) \dbinom{n - 1}{r} + (r−1r−n) \dbinom{r - 1}{r - n}

Corollary of Combination

(nr) \dbinom{n}{r} = (n−2r−2) \dbinom{n - 2}{r - 2} + 2(n−2r−1) 2 \dbinom{n - 2}{r - 1} + (n−2r) \dbinom{n - 2}{r}

固定一物 A A 和 B B

  • 取到 A A 和 B B : (n−2r−2) \dbinom{n - 2}{r - 2}
  • 不取 A A 或 B B : (n−2r−1) \dbinom{n - 2}{r - 1}
  • 不取 A A 和 B B : (n−2r) \dbinom{n - 2}{r}

Vandermonde's Convolution

(r+sn) \dbinom{r + s}{n} = (r0)(sn) \dbinom{r}{0} \dbinom{s}{n} + (r1)(sn−1) \dbinom{r}{1} \dbinom{s}{n - 1} + ... + (rn)(s0) \dbinom{r}{n} \dbinom{s}{0} = ∑k=0n(rk)(sn−k) \displaystyle\sum_{k=0}^{n} \dbinom{r}{k} \dbinom{s}{n - k}

⇒r \Rightarrow r = s s = n n 代入: (2nn) \dbinom{2n}{n} = (n0)2 \dbinom{n}{0}^2 + (n1)2 \dbinom{n}{1}^2 + ... + (nn)2 \dbinom{n}{n}^2 = ∑k=0n(nk)2 \displaystyle\sum_{k=0}^{n} \dbinom{n}{k}^2

Binomial Theorem

(x x + y y )n ^n = ∑k=0n(nr)xryn−r \displaystyle\sum_{k=0}^{n} \dbinom{n}{r} x^r y^{n - r} , n∈Z+ n \in Z^+

proof:

(x x + y y )n ^n 展開後 xryn−r x^r y^{n - r} 之係數 (nr) \dbinom{n}{r} 相當於「 n n 個 bits 中恰含 r r 個 1 與 n n - r r 個 0 之 bit string 個數」

Corollary of Binomial Theorem

(x1 x_1 + x2 x_2 + ... + xk x_k )n ^n = ∑n=∑i=1knk,0≤ni≤nk(nn1,n2,...,nk)x1n1x2n2 \displaystyle\sum_{\tiny{n = \displaystyle\sum_{i=1}^{k} n_k, \; 0 \le n_i \le n_k}} \dbinom{n}{n_1, n_2, ..., n_k} {x_1}^{n_1} {x_2}^{n_2} ... xkn2 {x_k}^{n_2} , n∈Z+ n \in Z^+

Copyright© saberLiou all rights reserved.            last updated at 2019-09-02 11:36:32

results matching ""

    No results matching ""