Chuyên đề Đại số tổ hợp

Đại số tổ hợp - Trang 1 - Người soạn: Phạm Văn Luật

ĐẠI SỐ TỔ HỢP I. HOÁN VỊ − CHỈNH HỢP − TỔ HỢP: 1.Qui tắc cộng và qui tắc nhân: a) Qui tắc cộng : Nếu có m1 cách chọn đối tượng x1, 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 bất kỳ cách chọn đối tượng xj nào (i≠j; i,j=1,2,…,n) thì có m1+m2+…+mn cách chọn một trong các đối tượng đã cho. Cách khác: Một công việc được thực hiện qua nhiều trường hợp độc lập nhau. Trường hợp 1 có m1 cách thực hiện, trường hợp 2 có m2 cách thực hiện, …trường hợp n có mn cách thực hiện thì số cách thực hiện cả công việc là m1+m2+…+mn. b) Qui tắc nhân : Nếu 1 phép chọn được thực hiện qua n bước liên tiếp nhau, 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. Cách khác: Một công việc được thực hiện qua nhiều giai đoạn:Giai đoạn 1 có m1 cách thực hiện, giai đoạn 2 có m2 cách thực hiện, …giai đoạn n có mn cách thực hiện thì số cách thực hiện cả công việc là m1 . m2 . … .mn 2.Hoán vị: A. Hoán vị thẳng: a) Định nghĩa: Cho tập hợp A gồm n phần tử . Mỗi cách sắp thứ tự n phần tử (n≥1) của tập hợp A được gọi là 1 hoán vị của n phần tử đó. b) Định lý: Nếu ký hiệu số hoán vị của n phần tử là Pn, thì:

n 1.2.3 )... 2 n )( 1 n ( n Pn = − − = ! Qui ước: 0!=1 B. Hoán vị có lặp lại: a) Định nghĩa: Có n vật, sắp vào n vị trí. Trong đó:

n1 vật giống nhau n2 vật giống nhau …. nk vật giống nhau ( Hẳn nhiên là n= n1+n2+…+nk) b) Định lý: Số hoán vị có lặp lại của n vật trên là:

! n !... n ! n

!n

k 2 1

Đại số tổ hợp - Trang 2 - Người soạn: Phạm Văn Luật C. Hoán vị tròn : a) Định nghĩa: Có n vật, sắp vào n vị trí chung quanh một đường tròn. b) Định lý: Số hoán vị tròn của n vật trên là: Pn−1= (n−1)! 3.Chỉnh hợp: a) Định nghĩa: Cho tập hợp A gồm n phần tử. Mỗi bộ gồm k (1 ) k n ≤ ≤ phần tử sắp thứ tự của tập hợp A được gọi là 1 chỉnh hợp chập k của của n phần tử . b) Số chỉnh hợp chập k của n phần tử la ø :

)! k n (

!n )1 k n )...( 2 n )( 1 n ( n A k

n − = + − − − =

Đặc biệt: Khi

n n n k n A P = ⇒ =

4.Tổ hợp: a) Định nghĩa: Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k ) 0 ( n k ≤ ≤ phần tử của A được gọi là 1 tổ hợp chập k của n phần tử đã cho.

b) Số tổ hợp chập k của n phần tử la ø : )! k n (!k

!n C

k n − =

c) Tính chất:

1)

k n n k n C C

− =

2)

k n k n k n C C C = + −

−

− 1 1 1

3)

k n k n C !k A =

II.CÔNG THỨC NHỊ THỨC NEWTON: 1.Công thức nhị thức Newton: Với hai số thực a và b và n∈N ta có công thức:

n n n k k n k n 1 n 1

n n 0 n n b C ... b a C ... b a C a C ) b a ( + + + + + = +

− −

2.Các tính chất:

a) Vế phải có n+1 số hạng. b) Trong mỗi số hạng tổng số mũ của a và b là n. c) Số hạng thứ k+1 của công thức khai triển có dạng :

k k n k n 1 k b a C T − + = ) n ,..., 3,2,1,0 k ( =

d) Các hệ số cách đều số hạng đầu và cuối là bằng nhau.

n n n 2 n 1

n 0 n 2 C ... C C C ) e = + + + + .

0 C )1 ( ... C C C )f

n n n 2 n 1 n 0 n = − + + + − .

ThuVienDeThi.com