Bài giảng quy tắc đếm, hoán vị, chỉnh hợp và tổ hợp

Trang 1

TỔ HỢP XÁC SUẤT

BÀI GIẢNG QUY TẮC ĐẾM – HOÁN VỊ - CHỈNH HỢP – TỔ HỢP

Mục tiêu

 Kiến thức

+ Nắm vững quy tắc cộng, quy tắc nhân.

+ Hiểu và phân biệt được các khái niệm: Hoán vị, chỉnh hợp, tổ hợp.

 Kĩ năng

+ Vận dụng được quy tắc cộng và nhân cho các bài toán đếm.

+ Giải được các dạng toán đếm liên quan đến tổ hợp, chỉnh hợp.

+ Giải được phương trình liên quan đến công thức tổ hợp, chỉnh hợp.

TOANMATH.com Trang 2

I. LÍ THUYẾT TRỌNG TÂM

1. Các quy tắc đếm

a) Quy tắc cộng

Định nghĩa

Một công việc nào đó có thể được thực hiện theo một

trong hai phương án A hoặc B . Nếu phương án A có m

cách thực hiện, phương án B có n cách thực hiện và

không trùng với bất kì cách nào trong phương án A thì

công việc đó có m n  cách thực hiện.

Công thức

Nếu , A B là các tập hợp không giao nhau thì

   . n A B n A n B   

b) Quy tắc nhân

Định nghĩa

Một công việc nào đó có thể bao gồm hai công đoạn A và

B . Nếu công đoạn A có m cách thực hiện và ứng với mỗi

cách đó có n cách thực hiện công đoạn B thì công việc đó

có . m n cách thực hiện.

Công thức

Nếu , A B là các tập hữu hạn phần tử thì

   . . n A B n A n B  

2. Hoán vị

Định nghĩa

Một tập hợp gồm n phần tử   1 . n  Mỗi cách sắp xếp n

phần tử theo một thứ tự đượ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ử là: ! 1.2.3... . nP n n  

Hoán vị lặp

Cho k phần tử khác nhau 1 2 , ,..., . k a a a Mỗi cách sắp xếp

n phần tử trong đó gồm 1n phần tử 1 2 ; a n phần tử 2;...; k a n

phần tử   1 2 , ,..., k k a n n n n  theo một thứ tự được gọi là

một hoán vị lặp cấp n kiểu   1 2 , ,..., k n n n của k phần tử.

Mở rộng: Một công việc được hoàn thành

bởi một trong k phương án

1 2 3 , , ,..., . k A A A A Nếu phương án 1A có 1 m

cách thực hiện, phương án 2 A có 2 m cách

thực hiện,…phương án kA có k m cách thực

hiện và các cách thực hiện của các phương

án trên không trùng nhau thì công việc đó

có 1 2 3 ... k m m m m     cách thực hiện.

Cho các tập 1 2 , ,..., n A A A đôi một rời nhau.

Khi đó:

1 2 1 2 ... ... . n n A A A A A A       

Mở rộng: Một công việc được hoàn thành

bởi k hành động 1 2 3 , , ,..., k A A A A liên tiếp.

Nếu hành động 1A có 1 m cách thực hiện,

hành động 2 A có 2 m cách thực hiện,...,

hành động kA có k m cách thực hiện thì

công việc đó có 1 2 3 . . ... k m m m m cách hoàn

thành.

Cho các tập 1 2 , ,..., n A A A hữu hạn phần tử.

Khi đó:

1 2 1 2 ... . ... . n n A A A A A A    

Quy ước: 0! 1. 

  ! 1 ! . n n n  

   ! 1 . 2 ... ! n p p n p   

( với , , n p n p    ).

     ! 1 . 2 ... ! n n p n p n n p      

TOANMATH.com Trang 3

Số hoán vị lặp cấp n kiểu   1 2 , ,..., k n n n của k phần tử là:

  1 2 1 2

! , ,..., . ! !... ! n k k

n P n n n n n n 

Hoán vị vòng quanh

Cho tập A gồm n phần tử. Mỗi cách sắp xếp n phần tử

của tập A thành một dãy kín được gọi là một hoán vị vòng

quanh của n phần tử.

Số hoán vị vòng quanh của n phần tử là:

  1 !. n Q n  

3. Chỉnh hợp

Định nghĩa

Cho tập hợp A gồm n phần tử. Mỗi cách sắp xếp k phần

tử của   1 A k n   theo một thứ tự được gọi là một chỉnh

hợp chập k của n phần tử của tập A .

Số chỉnh hợp chập k của n phần tử:

      ! 1 2 ... 1 .!

k n n A n n n n k n k       

Chỉnh hợp lặp

Cho tập A gồm n phần tử. Một dãy gồm k phần tử của

A , trong đó mỗi phần tử có thể được lặp lại nhiều lần,

được sắp xếp theo một thứ tự nhất định được gọi là một

chỉnh hợp lặp chập k của n phần tử của tập .A

Số chỉnh hợp lặp chập k của n phần tử: k k n A n  .

4. Tổ hợp

Định nghĩa

Cho tập A gồm n phần tử. Mỗi tập con gồm

  1 k k 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ử.

Số tổ hợp chập k của n phần tử:

  ! . ! ! !

k k n n A n C k k n k   

Tính chất

0 1; n n n C C   ; k n k n n C C  

(với , , n p n p    ).

Công thức này đúng cho trường hợp

0 k  hoặc . k n 

Khi k n  thì !. n n n A P n  

Quy ước: 0 1 n C 

Phân biệt chỉnh hợp và tổ …