Kiến thức

[Chuyên Đề] Đại số tổ hợp-Hoán vị, chỉnh hợp, tổ hợp và ứng dụng

NỘI DUNG

Đ1 : Hoán vị, chỉnh hợp, tổ hợp và ứng dụng .

Lý thuyết: * Qui tắc cộng, qui tắc nhân.

* Hoán vị, chỉnh hợp; tổ hợp.

Các dạng toán ứng dụng.

1.1. Dạng 1: Rút gọn biểu thức đại số tổ hợp.

1.2. Dạng 2: Chứng minh đẳng thức; bất đẳng thức đại số tổ hợp.

1.3. Dạng 3: Giải phương trình; bất phương trình đại số tổ hợp.

1.4. Dạng 4: Các bài toán đếm số phương án.

Đ2: Nhị thức Newtơn và ứng dụng.

Lý thuyết: Nhị thức Newtơn.

Các dạng toán ứng dụng.

2.1. Dạng 1: Tính tổng tổ hợp.

2.2. Dạng 2: Chứng minh đẳng thức; bất đẳng thức đại số tổ hợp.

2.3. Dạng 3: Xác định hệ số của số hạng trong khai triển nhị thức Newtơn.

Đ1: hoán vị, chỉnh hợp, tổ hợp và ứng dụng.

Lý thuyết:

I. Qui tắc cộng, qui tắc nhân.

1. Quy tắc cộng: Nếu có m1 cách chọn đối tượng x1, có m2 cách chọn đối tượng x2,… mn cách chọn đối tượng xn và nếu cách chọn đối tượng xi không trùng với đối tượng xj nào( i khác j; i, j = 1,2,….,n) thì có m1 + m2 +….+ mn cách chọn một trong các đối tượng đã cho.

2. Quy tắc nhân: Nếu một phép chọn được thực hiện qua n bước liên tiếp, bước 1 có m1 cách, bước 2 có m2 cách,…. bước n có mn cách, thì phép chọn đó được thực hiện theo m1.m2…mn cách khác nhau.

II. Hoán vị, chỉnh hợp; tổ hợp.

  1. Hoán vị: * ĐN: Cho tập hợp A gồm n phần tử ( n$ ge $1). Mỗi cách sắp thứ tự n phần tử của tập hợp A được gọi là một hoán vị của n phần tử đó.

* Số hoán vị của n phần tử :

Pn = n! = 1.2.3.4.5….n $(forall n in N;{rm{ n}} ge {rm{1)}}$; Qui ước $0! = 1$.

2. Chỉnh hợp: * ĐN: Cho tập hợp A gồm n phần tử. Mỗi bộ gồm k (1$ le $ k $ le $n) phần tử sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử của A.
*Số chỉnh hợp chập k của n phần tử :
$mathop Anolimits_n^k = n(n – 1)…(n – k + 1)$ (1$ le $ k $ le $n)
$A_n^k = frac{{n!}}{{(n – k)!}}{rm{ }}$ (1$ le $ k $ le $n)
3. Tổ hợp: * ĐN: Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k (0$ le $ k $ le $n) phần tử của A được gọi là một tổ hợp chập k của n phần tử đã cho.
* Số tổ hợp chập k của n phần tử :
$mathop Cnolimits_n^k = frac{{n!}}{{k!(n – k)!}}$ (0$ le $ k $ le $n)

Các dạng toán thường gặp:

1.1. Dạng 1: Rút gọn biểu thức đại số tổ hợp.

1.2. Dạng 2: Chứng minh đẳng thức; bất đẳng thức đại số tổ hợp.

1.3. Dạng 3: Giải phương trình; bất phương trình đại số tổ hợp.

1.4. Dạng 4: Các bài toán đếm số phương án.

1- Dạng 1: rút gọn biểu thức đại số tổ hợp.

1. Phương pháp:

Sử dụng các công thức sau để rút gọn biểu thức đại số tổ hợp:
* ${P_n} = n!{rm{ }}$ ($n in {N^*}$)
* $A_n^k = frac{{n!}}{{(n – k)!}}{rm{ }}$ (1$ le $ k $ le $n)
* $C_n^k = frac{{n!}}{{k!(n – k)!}}$ (0$ le $ k $ le $n)

Một số ví dụ:
VÍ DỤ 1 Rút gọn biểu thức: ${A_{{rm{ }}n}} = sumlimits_{k = 2}^n {frac{{k – 1}}{{k!}}} $

Bài giải

Ta có nhận xét:
$frac{{k – 1}}{{k!}} = frac{1}{{left( {k – 1} right)!}} – frac{1}{{k!}}$
Suy ra ${A_n} = sumlimits_{k = 2}^n {frac{{k – 1}}{{k!}}} = frac{1}{{1!}} – frac{1}{{2!}} + frac{1}{{2!}} – frac{1}{{3!}} + … + frac{1}{{left( {n – 1} right)!}} – frac{1}{{n!}} = 1 – frac{1}{{n!}}$

Ví dụ 2: Rút gọn biểu thức: $A = frac{{A_n^6 + A_n^5}}{{A_n^4}}$

Bài giải

Ta có $A = frac{{n(n – 1)…(n – 5) + n(n – 1)…(n – 4)}}{{n(n – 1)…(n – 3)}} = n – 4 + (n – 4)(n – 5) = {(n – 4)^2}$

Ví dụ 3: Rút gọn biểu thức: $A = C_n^1 + 2frac{{C_n^2}}{{C_n^1}} + … + nfrac{{C_n^n}}{{C_n^{n – 1}}}$

Bài giải:

Ta lần lượt có: $C_n^1 = n$
$2frac{{C_n^2}}{{C_n^1}} = 2.frac{{frac{{n!}}{{2!.(n – 2)!}}}}{{frac{{n!}}{{1!.(n – 1)!}}}} = n – 1$
$begin{array}{l}
…\
nfrac{{C_n^n}}{{C_n^{n – 1}}} = frac{1}{{frac{{n!}}{{1!.(n – 1)!}}}} = 1
end{array}$
${rm{suy ra :}}A = n + n – 1 + … + 2 + 1 = frac{{n(n + 1)}}{2}.$

Bài tập tự luyện:

<1> Rút gọn biểu thức: ${C_n} = sumlimits_{k = 1}^n {frac{1}{{k(k + 1)}}} {rm{ }}$
<2>Rút gọn biểu thức: $A = frac{{5!}}{{m(m + 1)}}{rm{.}}frac{{(m + 1)!}}{{3!(m – 1)!}}{rm{ }}$
<3> Rút gọn biểu thức: $B = frac{{A_{49}^{12} + A_{49}^{11}}}{{A_{49}^{10}}}{rm{ – }}frac{{A_{17}^{10} + A_{17}^9}}{{A_{17}^8}}{rm{ }}$

2-Dạng 2: chứng minh đẳng thức, bất đẳng thức

1. Phương pháp: Thực hiện các bước sau:
·Sử dụng các công thức:
${P_n} = n!{rm{ }}$ ($n in {N^*}$)
$A_n^k = frac{{n!}}{{(n – k)!}}{rm{ }}$ (1$ le $ k $ le $n)
$C_n^k = frac{{n!}}{{k!(n – k)!}}$ (0$ le $ k $ le $n)
$C_n^k = C_{n – 1}^{k – 1} + C_{n – 1}^k{rm{ }}(0 < k < n)$
đưa đẳng thức, bất đẳng thức đại số tổ hợp thành đẳng thức, bất đẳng thức đại số thông thường.
·Chứng minh đẳng thức, bất đẳng thức đại số thông thường suy ra đpcm.

2. Một số ví dụ:
Ví dụ 1: CMR với k, n $ in $ N, (3$ le $ k $ le $n) ta có:

$A_{n + k}^{n + 2} + A_{n + k}^{n + 1} = {k^2}A_{n + k}^n$

Bài giải

$begin{array}{l}
VT = A_{n + k}^{n + 2} + A_{n + k}^{n + 1} = frac{{(n + k)!}}{{(k – 2)!}} + frac{{(n + k)!}}{{(k – 1)!}} = frac{{(n + k)!}}{{(k – 2)!}}left( {1 + frac{1}{{k – 1}}} right) = \
{rm{ }} = frac{{k(n + k)!}}{{(k – 1)(k – 2)!}} = frac{{{k^2}(n + k)!}}{{k(k – 1).(k – 2)!}} = frac{{{k^2}(n + k)!}}{{k!}} = {k^2}A_{n + k}^n = VP
end{array}$

Ví dụ 2: Chứng minh rằng:
${n^n} < {(n!)^2} < {(frac{{n + 1}}{2})^{2n}}{rm{ }}({rm{ }}n in Z,{rm{ }}n > 2)$ (1)

Bài giải

Biến đổi BĐT (1) về dạng:
${n^n} < {(1.2.3….n)^2} < {(frac{{n + 1}}{2})^{2n}}$
$ Leftrightarrow {n^n} < [(1.n)2.(n – 1)].3.(n – 2)…..k(n – k + 1){]^2} < {(frac{{n + 1}}{2})^{2n}}$ (2)
a.Ta có đánh giá: $k(n – k + 1) ge n{rm{ (*) }}(forall k < n,k > 1)$ do
$(*) Leftrightarrow n(k – 1) – k(k – 1) > 0 Leftrightarrow (n – k)(k – 1) ge 0$ đúng $forall k < n,k > 1$
áp dụng BĐT (*) với k = 2,…, n -1 ta được
$left. begin{array}{l}
1.n ge n\
2.(n – 1) > n\
….\
k(n – k + 1) > n\
…\
n.1 ge n
end{array} right}$ n bất đẳng thức.
Suy ra: $[(1.n)2.(n – 1)].3.(n – 2)…..k(n – k + 1)…(n – 1).2(n.1){]^2} > {n^n}{rm{ a)}}$

b. Sử dụng BĐT Côsi tacó :
$k(n – k + 1) le {rm{ }}{(frac{{k + n – k + 1}}{2})^2} = {(frac{{n + 1}}{2})^2}$ (**) $forall k ge 0,n ge k$
áp dụng BĐT (**) với k =1,2,…, n ta được
$left. begin{array}{l}
1.n le {left[ {frac{{n + 1}}{2}} right]^2}\
2(n – 1) le {left[ {frac{{n + 1}}{2}} right]^2}\
……..\
k(n – k + 1) le {left[ {frac{{n + 1}}{2}} right]^2}\
……..\
(n – 1)2 le {left[ {frac{{n + 1}}{2}} right]^2}\
1.n le {left[ {frac{{n + 1}}{2}} right]^2}
end{array} right}n{rm{ BDT}}$
Suy ra:$(1.n)[2.(n – 1)].3.(n – 2)…..k(n – k + 1)…(n – 1)2(n.1) < {left[ {frac{{n + 1}}{2}} right]^{2n}}$
Từ a) và b) suy ra (2) được chứng minh , suy ra (1) được chứng minh..
Ví dụ 3: CMR
a. $C_n^k + 3C_n^{k – 1} + 3C_n^{k – 2} + C_n^{k – 3} = C_{n + 3}^k$
b. $C_{n + 2}^k = C_n^k + 2C_n^{k – 1} + C_n^{k – 2}(2 le k le n)$
c. $2C_n^k + 5C_n^{k + 1} + 4C_n^{k + 2} + C_n^{k + 3} = C_{n + 3}^{k + 3} + C_{n + 2}^{k + 2}$
Bài giải
a.
Ta có :
$begin{array}{l}
VT = (C_n^k + C_n^{k – 1}) + 2(C_n^{k – 1} + C_n^{k – 2}) + (C_n^{k – 2} + C_n^{k – 3})\
= C_{n + 1}^k + 2C_{n + 1}^{k – 1} + C_{n + 1}^{k – 2} = (C_{n + 1}^k + C_{n + 1}^{k – 1}) + (C_{n + 1}^{k – 1} + C_{n + 1}^{k – 2})\
= C_{n + 2}^k + C_{n + 2}^{k – 1} = C_{n + 3}^k = VP
end{array}$
b. Ta có: $C_{n + 2}^k = C_n^k + 2C_n^{k – 1} + C_n^{k – 2}(2 le k le n)$
Nên $VP = left( {C_n^{k – 1} + C_n^k} right) + left( {C_n^{k – 1} + C_n^{k – 2}} right) = left( {C_{n + 1}^{k – 1} + C_{n + 1}^k} right) = left( {C_{n + 2}^k} right) = VT$
c. $VT{rm{ }} = 2left( {C_n^k + C_n^{k + 1}} right) + 3(C_n^{k + 1} + C_n^{k + 1}) + (C_n^{k + 2} + C_n^{k + 3})$
$ = 2left( {C_{n + 1}^{k + 1}} right) + 3left( {C_{n + 1}^{k + 2}} right) + left( { + C_{n + 1}^{k + 3}} right){rm{ }}$
$begin{array}{l}
= 2left( {C_{n + 1}^{k + 1} + C_{n + 1}^{k + 2}} right) + left( {C_{n + 1}^{k + 2} + C_{n + 1}^{k + 3}} right){rm{ }}\
= 2left( {C_{n + 2}^{k + 2}} right) + left( {C_{n + 2}^{k + 3}} right)\
= left( {C_{n + 2}^{k + 2}} right) + left( {C_{n + 2}^{k + 2} + C_{n + 3}^{k + 3}} right) = left( {C_{n + 2}^{k + 2} + C_{n + 2}^{k + 3}} right) = VP
end{array}$

Ví dụ 4: CMR: $C_{2n + k}^n.C_{2n – k}^n le {(C_{2n}^n)^2}{rm{ }}(0 le k le n){rm{ }}(1)$
Bài giải
Ta có:
$begin{array}{l}
C_{2n + k}^n.C_{2n – k}^n le {(C_{2n}^n)^2}{rm{ (}}0 le k le n){rm{ }}(1)\
Leftrightarrow frac{{left( {2n + k} right)!}}{{left( {n + k} right)!.n!}}.frac{{left( {2n – k} right)!}}{{left( {n – k} right)!.n!}} le {left( {frac{{left( {2n} right)!}}{{n!.n!}}} right)^2} Leftrightarrow left[ {(n + k + 1)…(n + k + n)} right]left[ {(n – k + 1)…(n – k + n)} right] le {left[ {(n + 1)…(n + n)} right]^2}\
Leftrightarrow left[ {(n + k + 1)(n + k + 2)…(n + k + n)} right]left[ {(n – k + 1)(n – k + 2)…(n – k + n)} right] le {left[ {(n + 1)…(n + n)} right]^2}\
Leftrightarrow left[ {(n + k + 1)(n – k + 1)} right]…left[ {(n + k + n)(n – k + n)} right] le {left[ {(n + 1)…(n + n)} right]^2}(*)
end{array}$
Theo BĐT Cauchy ta có
$(n + k + i)(n – k + i) le {left( {n + i} right)^2}{rm{ }}forall {rm{ 0}} le {rm{k}} le {rm{n; }}$ i = $1…n$
Cho $i = overline {1,n} $ ta được BĐT (*)
Vậy BĐT (*) đúng =>(1) được chứng minh

3. Bài tập tương tự
Bài 1:
$n.C_{m + n}^n = (m + 1)C_{m + n}^{m + 1}{rm{ }}(m,n in {Z^ + })$
Bài 2: $C_{1 + n}^2 = C_n^2 + n{rm{ }}(n ge 2,n in {Z^ + })$
Bài 3: $C_n^r.C_r^k = C_n^k.C_{n – r}^{r – k}{rm{ }}(r,k,n in N,r le n,k le r)$
Bài 4: $C_{2n}^2 + C_{2n}^{n – 1} = frac{1}{2}C_{2n + 2}^{n + 1}{rm{ }}(n in {Z^ + })$
Bài 5: $C_n^r = frac{n}{r}C_{n – 1}^{r – 1}$
Bài 6*: $C_n^1 + 2.frac{{C_n^2}}{{C_n^1}} + 3frac{{C_n^3}}{{C_n^2}} + … + pfrac{{C_n^p}}{{C_n^{p – 1}}} + …. + nfrac{{C_n^n}}{{C_n^{n – 1}}} = frac{{nleft( {n + 1} right)}}{2}{rm{ }}$
Bài 7: $forall n in N,n ge 2{rm{ }}$ ta có ${rm{ }}frac{1}{{A_2^2}} + frac{1}{{A_3^2}} + … + frac{1}{{A_n^2}} = frac{{left( {n – 1} right)}}{n}{rm{ }}$
Bài 8: CMR: $k(k – 1)C_n^k = n(n – 1)C_{n – 2}^{k – 2}$
Bài 9: $C_n^k = C_{n – 1}^{k – 1} + C_{n – 1}^k(0 < k < n)$
Bài 10: CMR: $C_{2n + k}^n.C_{2n – k}^n le {(C_{2n}^n)^2}{rm{ }}0 le k le n)(1)$
Bài 11: CMR: $A_n^k = A_{n – 1}^k + kA_{n – 1}^{k – 1}{rm{ }}$
Bài 12: CMR: ${P_1} + 2{P_2} + 3{P_3} + … + n{P_n} = {P_{n + 1}} – 1$
Bài 13: CMR: $2C_n^k + 5C_n^{k + 1} + 4C_n^{k + 2} + C_n^{k + 3} = C_{m + 2}^{k + 2} + C_{m + 3}^{k + 3}$
Bài 14: CMR: $C_n^k + 2C_n^{k – 1} + C_n^{k – 2} = C_{n + 2}^k(2 le k le n,)$
Bài 15: CMR: $a.{rm{ }}C_n^r.C_r^k = C_n^k.C_{r – k}^{n – k}(r le n,k le r;n,r,k in Z)$
$begin{array}{l}
b.{rm{ }}C_n^r = frac{n}{r}C_{r – 1}^{r – 1}{rm{ }}(r < n)\
c.{rm{ }}C_n^r = C_{n – 1}^{r – 1}{rm{ + }}C_{n – 2}^{r – 2}{rm{ + }}…{rm{ + }}C_{r – 1}^{r – 1}{rm{ }}(r < n){rm{ }}
end{array}$
Bài 16: CMR:
$begin{array}{l}
{rm{ }}1)C_5^0.C_n^k + C_5^1.C_n^{k – 1} + C_5^2.C_n^{k – 2} + … + C_5^5.C_n^{k – 5} = C_{n + 5}^ka\
{rm{2)}}C_n^r = C_{n – 1}^{r – 1} + C_{n – 2}^{r – 2} + …. + C_{r – 1}^{r – 1}\
{rm{3)}}C_n^k + 4.C_n^{k – 1} + 6.C_n^{k – 2} + 4.C_n^{k – 3} + C_n^{k – 4} = C_{n + 4}^k\
{rm{4)}}C_n^{k – 3} + C_n^k + 3.C_n^{k – 1} + 3C_n^{k – 2} = C_{n + 3}^k
end{array}$
$5)C_n^{m + 1} + C_n^{m – 1} + 2C_n^m = C_{n + 2}^{m + 1}$
$begin{array}{l}
{rm{6)}}C_n^{k – 3} + C_n^k + 3C_n^{k – 1} + 3C_n^{k – 2} = C_{n + 3}^k\
{rm{7)2}}C_n^k + 5.C_n^{k + 1} + 4.C_n^{k + 2} + C_n^{k + 3} = C_{n + 2}^{k + 2} + C_{n + 3}^{k + 3}
end{array}$
Bài 17: $C_{2001}^k + C_{2001}^{k + 1} le C_{2001}^{1000} + C_{2001}^{1001}{rm{ (0}} le {rm{k}} le {rm{2000)}}$ ( ĐHQGHN – A –99- 00 )
Bài 18: CMR:
$frac{{{2^{100}}}}{{10sqrt 2 }} < C_{scriptstyleatop
scriptstyle100}^{50} < frac{{{2^{100}}}}{{10sqrt 2 }}$

 

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Check Also
Close
Back to top button