TỔ HỢP, CHỈNH HỢP - CÁC PHƯƠNG PHÁP TÍNH TỔNG

I. LÝ THUYẾT
Chỉnh hợp:
Cho tập hợp $A$ gồm $n$ phần tử; $n$$ \geqslant $1. Một chỉnh hợp chập $k$ các phần tử của $A$ là một cách sắp xếp $k$ phần tử khác nhau của $A$; $1 \leqslant k \leqslant n;\,\,k \in \mathbb{N}$.
Số các chỉnh hợp chập $k$ của $n$ phần tử: $A_n^k = \frac{{n!}}{{(n - k)!}}$
Hoán vị:
Cho tập hợp $A$ gồm $n$ phần tử; $n > 0$. Một hoán vị $n$ phần tử của $A$ là một chỉnh hợp chập $n$ các phần tử của $A$ (Hay một cách sắp xếp thứ tự các $n$ phần tử của $A$).
Số các hoán vị $n$ phần tử của $A$: ${P_n} = A_n^n = n!$
Tổ hợp:
Cho tập hợp $A$ gồm $n$ phần tử; $n > 0$. Một tổ hợp chập $k$ các phần tử của $A$ là một tập hợp con của $A$ có $k$ phần tử ; $0 \leqslant k \leqslant n;\,\,k \in \mathbb{N}$.
Số các tổ hợp chập $k$ của $n$ phần tử: $C_n^k = \frac{{n!}}{{k!.(n - k)!}}$

Các công thức quan trọng của $P_n, C_n^k, A_n^k$
•    $C_n^k = \frac{{A_n^k}}{{{P_k}}}$
•    $C_n^k = C_n^{n - k}$
•    $C_n^k = C_{n - 1}^k + C_{n - 1}^{k - 1}$
•    $k.C_n^k = n.C_{n - 1}^{k - 1}\quad (1 \leqslant k \leqslant n;k \in \mathbb{N};n \in N;n > 1)$       
•    $k.(k - 1).C_n^k = n.(n - 1).C_{n - 2}^{k - 2};\quad \forall k;n \in \mathbb{N};2 \leqslant k \leqslant n$
•    $k.(k - 1)(k - 2).C_n^k = n.(n - 1)(n - 2).C_{n - 3}^{k - 3};\quad \forall k;n \in \mathbb{N};3 \leqslant k \leqslant n$
•    $\frac{1}{{k + 1}}.C_n^k = \frac{1}{{n + 1}}.C_{n + 1}^{k + 1}\quad (\forall k \in \mathbb{N};0 \leqslant k \leqslant n;n \in {\mathbb{N}^*}$    
Nhị thức Newton
${(a + b)^n} = C_n^0.{a^n} + C_n^1.{a^{n - 1}}.b + C_n^2.{a^{n - 2}}.{b^2} + ... $
                                        $+ C_n^k.{a^{n - k}}.{b^k} + ... + C_n^n.{b^n}$$ = \sum\limits_{k = 0}^n {C_n^k.{a^{n - k}}.{b^k}} $$(\forall n \in {\mathbb{N}^*})$

Ta cũng có thể khai triển:
${(a + b)^n} = C_n^0.{b^n} + C_n^1.{b^{n - 1}}.a + C_n^2.{b^{n - 2}}.{a^2} + ... $
                                       $+ C_n^k.{b^{n - k}}.{a^k} + ... + C_n^n.{a^n}$$ = \sum\limits_{k = 0}^n {C_n^k.{a^k}.{b^{n - k}}} $ $(\forall n \in {\mathbb{N}^*})$
Một số đẳng thức rút ra từ nhị thức Newton:
$C_n^0 + C_n^1 + ..... + C_n^k + ..... + C_n^n = {2^n}\quad \forall n \in {\mathbb{N}^*}$
$C_n^0 - C_n^1 + ..... + {( - 1)^k}.C_n^k + ..... + {( - 1)^n}.C_n^n = \quad \forall n \in {\mathbb{N}^*}$
${(1 + x)^{2n}} = \sum\limits_{k = 0}^{2n} {{x^k}.C_{2n}^k} $;     ${(1 - x)^{2n}} = \sum\limits_{k = 0}^{2n} {{{( - 1)}^k}{x^k}.C_{2n}^k} $
${(1 + x)^{2n + 1}} = \sum\limits_{k = 0}^{2n} {{x^k}.C_{2n + 1}^k} $; ${(1 - x)^{2n + 1}} = \sum\limits_{k = 0}^{2n} {{{( - 1)}^k}{x^k}.C_{2n + 1}^k} $

II. BÀI TẬP
Phương pháp:
1.  Quan sát biểu thức cần tính để đưa ra nhị thức Newton thích hợp.
2.  Áp dụng các biến đổi tổ hợp, chỉnh hợp quen thuộc
3.  Xác định công thức tổng quát và chứng minh
4.  Sử dụng công cụ đạo hàm hoặc tích phân

Bài 1:
Rút gọn:  ${\operatorname{S} _k} = C_n^0 - C_n^1 + C_n^2 - C_n^3 + ... + {( - 1)^k}C_n^k;\quad 0 \leqslant k \leqslant n;\,\,\,\,k \in \mathbb{N};n \in {\mathbb{N}^*}$
Hướng dẫn:
Nếu $k<n$ thì ta có
${\operatorname{S} _k} = C_n^0 - (C_{n - 1}^0 + C_{n - 1}^1) + (C_{n - 1}^1 + C_{n - 1}^2) - (C_{n - 1}^2 + C_{n - 1}^3) + ... $
                               $+ {( - 1)^k}(C_{n - 1}^{k - 1} + C_{n - 1}^k);0 \leqslant k \leqslant n;\,\,\,\,k \in \mathbb{N};n \in {\mathbb{N}^*}$
Rút gọn suy ra: ${S_k} = {( - 1)^k}.C_{n - 1}^k$
Nếu $k = n$ thì ${\operatorname{S} _k} = C_n^0 - C_n^1 + C_n^2 - C_n^3 + ... + {( - 1)^n}C_n^n = 0$

Bài 2:
Tính S = $C_{4n}^1 + C_{4n}^3 + C_{4n}^4 + .... + C_{4n}^{2n - 1}$
Hướng dẫn:
Áp dụng công thức $C_n^k = C_n^{n - k}$ ta có:
$C_{4n}^1 = C_{4n}^{4n - 1};C_{4n}^3 = C_{4n}^{4n - 3};....;C_{4n}^{2n - 1} = C_{4n}^{2n + 1}$
Vì vậy $S =$ $C_{4n}^{4n - 1} + C_{4n}^{4n - 3} + .... + C_{4n}^{2n + 1}$
Suy ra
$2S = $$C_{4n}^1 + C_{4n}^3 + C_{4n}^4 + .... + C_{4n}^{2n - 1} + C_{4n}^{2n + 1} + ..... + C_{4n}^{4n - 1} = {2^{4n}} - C_{4n}^0 - C_{4n}^{4n}$
 $ \Rightarrow S = {2^{4n - 2}}$

Bài 3: 
Tính các tổng sau:
a. ${S_2} = C_n^0 + 2C_n^1 + 3C_n^2 + ... + (n + 1)C_n^n;\quad n \in \mathbb{N};n > 1$      
b. ${S_3} = C_n^2 + 2C_n^3 + 3C_n^4 + ... + (n - 1)C_n^n;\quad n \in {\mathbb{N}^*};n \geqslant 2$   
c. ${S_4} = n{.2^{n - 1}}.C_n^0 + (n - 1){.2^{n - 2}}.3.C_n^1 + (n - 2){.2^{n - 3}}{.3^2}.C_n^2 + ... + {3^{n - 1}}.C_n^{n - 1};\quad n \in \mathbb{N};n > 1$
d. ${S_5} = {4.5^3}.C_{2009}^0 + {5.5^4}.C_{2009}^1 + ... + {2013.5^{2012}}.C_{2009}^{2009}$
Hướng dẫn:
a.  ${S_2} = C_n^0 + 2C_n^1 + 3C_n^2 + ... + (n + 1)C_n^n;\quad n \in {\mathbb{N}^*}$    
$ \Rightarrow {S_2} = \sum\limits_{k = 0}^n {(k + 1).C_n^k = } \;0.C_n^0 + \sum\limits_{k = 1}^n {k.C_n^k}  + \sum\limits_{k = 0}^n {C_n^k} $
$ \Rightarrow {S_2} = \sum\limits_k^n {n.C_{n - 1}^{k - 1}}  + \sum\limits_{k = 0}^n {C_n^k} $
$\begin{array}
   \Rightarrow {S_2} = n{.2^{n - 1}} + {2^n}  \\
   \Rightarrow {S_2} = (n + 2){.2^{n - 1}};\quad \forall n \in \mathbb{N};n > 1  \\
\end{array} $
b. ${S_3} = C_n^2 + 2C_n^3 + 3C_n^4 + ... + (n - 1)C_n^n;\quad n \in {\mathbb{N}^*};n \geqslant 2$
$ \Rightarrow {S_3} = \sum\limits_{k = 2}^n {(k - 1).C_n^k = } \;\sum\limits_{k = 2}^n {k.C_n^k}  - \sum\limits_{k = 2}^n {C_n^k} $
$ \Rightarrow {S_3} = \;\sum\limits_{k = 1}^n {k.C_n^k}  - C_n^1 - \sum\limits_{k = 0}^n {C_n^k}  + C_n^0 + C_n^1$
$ \Rightarrow {S_3} = \sum\limits_{k = 1}^n {n.C_{n - 1}^{k - 1}}  - C_n^1 - \sum\limits_{k = 0}^n {C_n^k}  + C_n^0 + C_n^1$
$\begin{array}
   \Rightarrow {S_3} = n{.2^{n - 1}} - {2^n} + 1  \\
   \Rightarrow {S_3} = (n - 2){.2^{n - 1}} + 1;\quad \forall n \in \mathbb{N};n \geqslant 2  \\
\end{array} $
c. ${S_4} = n{.2^{n - 1}}.C_n^0 + (n - 1){.2^{n - 2}}.3.C_n^1 + (n - 2){.2^{n - 3}}{.3^2}.C_n^2 + ... + {3^{n - 1}}.C_n^{n - 1};\quad n \in {\mathbb{N}^*}$
$ \Rightarrow {S_4} = \sum\limits_{k = 0}^{n - 1} {(n - k){{.2}^{n - k - 1}}{{.3}^k}.C_n^k = } \;\sum\limits_{k = 0}^{n - 1} {{2^{n - k - 1}}{{.3}^k}.(n - k).C_n^{n - k}} $
$ \Rightarrow {S_4} = \sum\limits_{k = 0}^{n - 1} {{2^{n - k - 1}}{{.3}^k}.n.C_{n - 1}^{n - k - 1}} $
$\begin{array}
   \Rightarrow {S_4} = n({2^{n - 1}}{.3^0}.C_{n - 1}^{n - 1} + {2^{n - 2}}{.3^2}.C_{n - 1}^{n - 2} + ... + {2^0}{.3^{n - 1}}.C_{n - 1}^0)  \\
   \Rightarrow {S_4} = n.{(2 + 3)^{n - 1}}  \\
   \Rightarrow {S_4} = n{.5^{n - 1}};\quad \forall n \in \mathbb{N};n > 1  \\
\end{array} $
d. ${S_5} = {4.5^3}.C_{2009}^0 + {5.5^4}.C_{2009}^1 + ... + {2013.5^{2012}}.C_{2009}^{2009}$
$\begin{array}
   \Rightarrow {S_5} = \sum\limits_{k = 0}^{2009} {(k + 4){{.5}^{k + 3}}.C_{2009}^k}  = \sum\limits_{k = 0}^{2009} {k{{.5}^{k + 3}}.C_{2009}^k}  + \sum\limits_{k = 0}^{2009} {{{4.5}^{k + 3}}.C_{2009}^k}   \\
   \Rightarrow {S_5} = \sum\limits_{k = 0}^{2009} {{5^{k + 3}}.k.C_{2009}^k}  + \sum\limits_{k = 0}^{2009} {{{4.5}^{k + 3}}.C_{2009}^k}   \\
   \Rightarrow {S_5} = {5^{0 + 3}}.0.C_{2009}^0 + \sum\limits_{k = 1}^{2009} {{5^4}{{.5}^{k - 1}}.2009.C_{2008}^{k - 1}}  + \sum\limits_{k = 0}^{2009} {{{4.5}^3}{{.5}^k}.C_{2009}^k}   \\
   \Rightarrow {S_5} = {2009.5^4}.({5^0}C_{2008}^0 + {5^1}C_{2008}^1 + ... + {5^{2008}}C_{2008}^{2008}) +   \\
  \quad \quad \quad \quad  + {4.5^3}.({5^0}C_{2009}^0 + {5^1}C_{2009}^1 + ... + {5^{2009}}C_{2009}^{2009})  \\
   \Rightarrow {S_5} = {2009.5^4}{.6^{2008}} + {4.5^3}{.6^{2009}}  \\
   \Rightarrow {S_5} = {10069.5^3}{.6^{2008}}  \\
\end{array} $

Bài 4:
Tính $S = C_n^0 - 2C_n^1 + 3C_n^2 - ... + {( - 1)^n}.(n + 1)C_n^n;\quad n \in \mathbb{N}$
Hướng dẫn:
Ta sử dụng công cụ đạo hàm:
Xét đa thức $f(x) = x(1+x)^n =$ $C_n^0x + C_n^1{x^2} + C_n^2{x^3} + ... + C_n^n{x^{n + 1}};\quad n \in {\mathbb{N}^*}$  $D=R$
Ta có ${f^'}(x) = $$C_n^0 + C_n^1.2x + C_n^23{x^2} + ... + C_n^n.(n + 1){x^n} = {(1 + x)^n} + nx{(1 + x)^{n - 1}}$
$ \Rightarrow {f^'}( - 1) = $$C_n^0 - 2C_n^1 + 3C_n^2 - ... + {( - 1)^n}.(n + 1)C_n^n = {f^'}( - 1) = 0$

Lưu ý: Để tính các tổng
${S_1} = C_n^0 + 2aC_n^1 + 3{a^2}C_n^2 + ... + (n + 1){a^n}C_n^n;\quad $
${S_2} = C_{2n}^0 + 3{a^2}C_{2n}^2 + 5{a^4}C_{2n}^4 + ... + (2n + 1){a^{2n}}C_{2n}^{2n};\quad $
Ta xét đa thức $f(x) = x(1+x)^n$ và chứng tỏ rằng $S_1=f’(a)$;
Ta xét đa thức $g(x) = x(1+x)^{2n}$ và chứng tỏ rằng $2S_2=g’(a)+g’(-a); 2S3=g’(a)-g’(-a)$

Bài 5:
Tính $S = {1^2}C_n^1 + {2^2}C_n^2 + {3^2}C_n^3 + ... + {n^2}C_n^n$.
Hướng dẫn:
Ta sử dụng công cụ đạo hàm:
${\left( {1 + x} \right)^n} = C_n^0 + C_n^1x + C_n^2{x^2} + ... + C_n^n{x^n}$
Đạo hàm 2 vế ta được
$n{\left( {1 + x} \right)^{n - 1}} = C_n^1 + C_n^2.2x + ... + C_n^n.n{x^{n - 1}}$
Nhân 2 vế với x
$nx{\left( {1 + x} \right)^{n - 1}} = C_n^1x + C_n^2.2{x^2} + ... + C_n^n.n{x^n}$
Đạo hàm 2 vế lần nữa ta được
$n{(1 + x)^{n - 1}} + n(n - 1)x{(1 + x)^{n - 2}} = C_n^1 + C_n^2{2^2}x + ... + C_n^n{n^2}{x^{n - 1}}$
Thế $x = 1$ ta được
$n{.2^{n - 1}} + n(n - 1){2^{n - 2}} = S$
Hay $S = n(n + 1){2^{n - 2}}$

Bài 6:
Tính  ${S_1} = C_n^0 + \frac{1}{2}.C_n^1 + \frac{1}{3}.C_n^2 + ... + \frac{1}{{n + 1}}.C_n^n\quad ;n \in {\mathbb{N}^*}$
Hướng dẫn:
Ta sử dụng công cụ tích phân:
Xét đa thức $f(x) = $${(1 + x)^n} = C_n^0 + x.C_n^1 + {x^2}.C_n^2 + ... + {x^n}.C_n^n\quad \forall x \in \mathbb{R};n \in {\mathbb{N}^*}$
Suy ra:  $\int\limits_0^1 {f(x)dx}  = $$C_n^0 + \frac{1}{2}.C_n^1 + \frac{1}{3}.C_n^2 + ... + \frac{1}{{n + 1}}.C_n^n = {S_1} $
$\Rightarrow {S_1} = \frac{{{{(1 + x)}^{n + 1}}}}{{n + 1}}\left| {\begin{array}{*{20}{c}}
  1 \\
  0
\end{array} = \frac{{{2^{n + 1}} - 1}}{{n + 1}}} \right.$

Lưu ý: Để tính các tổng
$S = (b - a)C_n^0 + \frac{{{b^2} - {a^2}}}{2}.C_n^1 + \frac{{{b^3} - {a^3}}}{3}.C_n^2 + ... + \frac{{{b^{n + 1}} - {a^{n + 1}}}}{{n + 1}}.C_n^n\quad ;n \in {\mathbb{N}^*}$
Hãy chứng tỏ rằng $S = $$\int\limits_a^b {f(x)dx} ;\,\,f(x) = {(1 + x)^n}$

Bài 7:
$S = \frac{1}{2}C_n^0 - \frac{1}{3}C_n^1 + \frac{1}{4}C_n^2 - ... + {( - 1)^n}\frac{1}{{n + 2}}C_n^n$
Hướng dẫn:
 $\int\limits_0^1 {x{{(1 - x)}^n}dx = \int\limits_0^1 {\left[ {C_o^nx - C_n^1{x^2} + C_n^2{x^3} - ... + C_n^n{x^{n + 1}}} \right]} } dx$
Tính $\int\limits_0^1 {x{{(1 - x)}^n}dx} $. Đặt $u = 1 - x \Rightarrow du =  - dx$, $\left\{ {\begin{array}{*{20}{c}}
  {x = 0 \Rightarrow u = 1} \\
  {x = 1 \Rightarrow u = 0}
\end{array}} \right.$.
$\int\limits_0^1 {x{{(1 - x)}^n}dx}  = \int\limits_0^1 {(1 - u){u^n}du = \left. {\frac{{{u^{n + 1}}}}{{n + 1}}} \right|} _0^1 - \left. {\frac{{{u^{n + 2}}}}{{n + 2}}} \right|_0^1$
$= \frac{1}{{n + 1}} - \frac{1}{{n + 2}} = \frac{1}{{(n + 1)(n + 2)}}$
$\begin{array}
  \int\limits_0^1 {\left[ {C_n^0x - C_n^1{x^2} + C_n^2{x^3} - ... + {{( - 1)}^n}C_n^n{x^{n + 1}}} \right]} dx  \\
   = \left. {\left[ {C_n^0\frac{{{x^2}}}{2} - C_n^1\frac{{{x^3}}}{3} + C_n^2\frac{{{x^4}}}{4} - ... + {{( - 1)}^n}C_n^n\frac{{{x^{n + 2}}}}{{n + 2}}} \right]} \right|_0^1  \\
   = \frac{1}{2}C_n^0 - \frac{1}{3}C_n^1 + \frac{1}{4}C_n^2 - ... + {( - 1)^n}\frac{1}{{n + 2}}C_n^n  \\
   = S  \\
\end{array} $
Vậy $S = \frac{1}{{(n + 1)(n + 2)}}$

Các phương pháp đạo hàm và tích phân trong tổ hợp sẽ được trình bày chi tiết ở các chuyên đề:

-  Sử dụng công cụ đạo hàm trong giải toán tổ hợp

-  Sử dụng công cụ tích phân trong giải toán tổ hợp

BÀI TẬP TỰ GIẢI:
Bài 1:
Tính tổng
a. ${S_1} = {1.2^0}.C_n^1 + {2.2^1}.C_n^2 + {3.2^2}.C_n^3 + ..... + n{.2^{n - 1}}.C_n^n\quad \forall n \in \mathbb{N};n > 1$
b. ${S_2} = 2.C_{2n + 1}^2 + 4.C_{2n + 1}^4 + ..... + 2n.C_{2n + 1}^{2n}$
c. ${S_3} = 2.C_{2n}^2 + 4.C_{2n}^4 + ..... + 2n.C_{2n}^{2n}$
Bài 2:
Cho $a > 0; $$n \in {\mathbb{N}^*}$. Hãy tính tổng
a. ${S_1} = 1.2.C_{n + 1}^1 + 3.4.{a^2}.C_{n + 1}^2 + ..... + (2n + 1)(2n + 2).{a^{2n}}.C_{n + 1}^{n + 1}$
b. ${S_2} = C_n^0 + 2a.C_n^1 + 3{a^2}.C_n^2 + ..... + (n + 1){a^n}.C_n^n$
c. ${S_3} = C_{2n}^0 + 3{a^2}.C_{2n}^2 + 5{a^4}.C_{2n}^4 + ..... + (2n + 1){a^{2n}}.C_{2n}^{2n}$
d. ${S_4} = 2a.C_{2n}^1 + 4{a^3}.C_{2n}^3 + 6{a^5}.C_{2n}^5 + ..... + 2n.{a^{2n - 1}}.C_{2n}^{2n - 1}$
Bài 3:
Tính $S = \frac{1}{3}C_n^0 + \frac{1}{4}C_n^1 + \frac{1}{5}C_n^2 + ... + \frac{1}{{n + 3}}C_n^n$
Bài 4:
Tính tổng $S = \frac{1}{{n + 1}}C_n^0 - \frac{1}{n}C_n^1 + \frac{1}{{n - 1}}C_n^2 - ... + {\left( { - 1} \right)^n}C_n^n$
Bài 5:
Tính
$S = {2012.3^{2011}}C_{2012}^0 - {2011.3^{2010}}C_{2012}^1 + {2010.3^{2009}}C_{2012}^2 - ... + 2.3C_{2012}^{2010} - C_{2012}^{2011}$
Bài 6:
Tính tổng
a. ${S_1} = C_n^0 + \frac{1}{2}.C_n^1 + \frac{1}{3}.C_n^2 + ... + \frac{1}{{n + 1}}.C_n^n\quad ;n \in {\mathbb{N}^*}$
b. ${S_2} = \frac{{{2^2}}}{2}.C_n^1 + \frac{{{2^3}}}{3}.C_n^2 + \frac{{{2^4}}}{4}.C_n^3 + ... + \frac{{{2^{n + 1}}}}{{n + 1}}.C_n^n\quad (n \in \mathbb{N};n > 1)$
c. ${S_3} = \frac{1}{2}.C_{2n}^1 + \frac{1}{4}.C_{2n}^3 + \frac{1}{6}.C_{2n}^5 + ... + \frac{1}{{2n}}.C_{2n}^{2n - 1}\quad (n \in \mathbb{N};n > 1)$
d. ${S_4} = 2.C_n^0 + \frac{{{3^2} - 1}}{2}.C_n^1 + \frac{{{3^3} - 1}}{3}.C_n^2 + \frac{{{3^4} - 1}}{4}.C_n^3 + ... + \frac{{{3^{n + 1}} - 1}}{{n + 1}}.C_n^n\quad (n \in {\mathbb{N}^*})$
e. ${S_5} = {2^0}C_n^0 - \frac{{{2^2}}}{2}.C_n^1 + \frac{{{2^3}}}{3}.C_n^2 - \frac{{{2^4}}}{4}.C_n^3 + ... + {( - 1)^n}\frac{{{2^{n + 1}}}}{{n + 1}}.C_n^n\quad (n \in {\mathbb{N}^*})$
f.  ${S_6} = \frac{{b - a}}{1}C_n^0 + \frac{{{b^2} - {a^2}}}{2}.C_n^1 + \frac{{{b^3} - {a^3}}}{3}.C_n^2 + ... + \frac{{{b^{n + 1}} - {a^{n + 1}}}}{{n + 1}}.C_n^n\quad (n \in {\mathbb{N}^*};a;b \in \mathbb{R})$