Chương 1: Các kiến thức cơ sở

CHƯƠNG 1. CÁC KIẾN THỨC CƠ SỞ

1.1. Các khái niệm cơ bản

1.2. Lý thuyết tổ hợp

1.3. Hai nguyên lý cơ bản

1.4. Lý thuyết số và các hệ đếm

1.5. Bài tập

LÝ THUYẾT TỔ HỢP

2. Chỉnh hợp lặp.

1. Khái niệm.

3. Chỉnh hợp không lặp.

4. Hoán vị.

5. Tổ hợp.

6. Tổ hợp lặp.

7. Hoán vị của tập hợp có các phần tử giống nhau.

8. Một số công thức tổ hợp.

9. Một số ví dụ.

KHÁI NIỆM

Lý thuyết tổ hợp nghiên cứu:

1. Các cấu hình tổ hợp,

2. Các phương pháp lựa chọn phần tử hoặc bộ các phần tử trong

tập hợp hữu hạn theo các cách khác nhau.

→ Là cơ sở để xây dựng thuật toán vét cạn, các thuật toán sinh

phần tử mới, các thuật toán lựa chọn phương án tối ưu, v..v…

Một số bài toán:

1. Các bài toán đếm,

2. Các bài toán về sự tồn tại,

3. Các phương pháp biểu diễn các cấu hình tổ hợp…

CHỈNH HỢP LẶP

KN: Chỉnh hợp lặp chập k của tập n phần tử là một cách sắp

xếp có thứ tự k phần tử lấy từ tập gồm n phần tử đã cho, mỗi

phần tử có thể được lấy lặp lại.

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

 Tập A = {1, 2, 3, 4, 5} n = 5.

Ví dụ 1:

Các bộ (1, 1, 2) ; (1, 2, 1) ; (2, 3, 5) và (2, 3, 2 ) là các chỉnh

hợp lặp chập 3 từ 5 phần tử.

CHỈNH HỢP LẶP

 Ví dụ 2.

• Từ tập  = { a, b, c } có thể đặt được bao nhiêu tên biến có độ dài

4 ký tự?

• Giải: Mỗi tên biến có 4 ký tự được chọn từ tập  là một bộ 4 phần

tử được lấy từ tập  vậy có số tên biến có 4 ký tự được chọn từ 

là N()xN()xN()xN() = 3x3x3x3 = 81.

 Ví dụ 3.

• Các dãy nhị phân có độ dài n là một chỉnh hợp lặp chập n từ hai

phần tử {0, 1}. Vậy theo công thức chỉnh hợp lặp chập n từ 2 phần

tử là : 2n.

CHỈNH HỢP KHÔNG LẶP

KN: Chỉnh hợp không lặp chập k từ n phần tử (gọi tắt là

chỉnh hợp chập k) là một cách sắp xếp có thứ tự k phần

tử của tập n phần tử, mỗi phần tử không được lấy lặp

lại.

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

CHỈNH HỢP KHÔNG LẶP

• Tập A = {1, 2, 3, 4, 5} các bộ (2, 3, 5); (2, 5, 3) là các chỉnh hợp

không lặp chập 3 từ 5 phần tử, còn các bộ (1, 1, 2) ; (1, 2, 1) ; và

(2, 3, 2) không phải là chỉnh hợp không lặp chập 3 từ 5 phần tử,

nhưng mặt khác đó lại là chỉnh hợp lặp chập 3 từ 5 phần tử.

Ví dụ 4.

• Có bao nhiêu số có 4 chữ số khác nhau được chọn từ các số sau B

= {1,3, 4, 5, 7, 6}?

• Giải: Số các số có 4 chữ số khác nhau được chọn từ tập B là số

chỉnh hợp chập 4 của 6:

•

Ví dụ 5.

(số)

HOÁN VỊ

KN: Hoán vị của n phần tử khác nhau là một cách sắp

xếp có thứ tự n phần tử đó.

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

 Có bốn người rủ nhau đi chụp ảnh là Anh, Bắc, Cúc,

Ví dụ 6:

Dương. Hãy tính xem có bao nhiêu kiểu ảnh chụp mà tất cả

 Số kiểu ảnh = (kiểu)

bốn người đứng thành một hàng ?

TỔ HỢP

KN:Tổ hợp chập k từ n phần tử là cách chọn không phân

biệt thứ tự k phần tử lấy từ tập n phần tử đã cho, mỗi phần

tử không được lấy lặp lại.

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

Từ công thức trên có thể suy ra rằng:

TỔ HỢP

Ví dụ 7:

 Với tập A = {1, 2, 3, 4, 5} thì các bộ (1, 2, 3 ), (1, 2, 4) là các tổ

hợp chập 3 từ 5 phần tử, còn các bộ (1, 1, 2 ), (2, 3, 2 ) không

hai bộ (2, 3, 5 ), (3, 5, 2) chỉ được tính là một tổ hợp chập 3.

phải là tổ hợp chập 3 từ 5 phần tử đã cho. Theo định nghĩa

Ví dụ 8:

 Có 12 đội bóng tham dự giải chuyên nghiệp quốc gia, các đội

thi đấu vòng tròn một lượt. Hỏi có bao nhiêu trận đấu được tổ

 Giải : Mỗi trận đấu là một cặp 2 đội được chọn từ 12 đội đã

chức ?

cho, không kể đến thứ tự và phải khác nhau, vậy số trận đấu

là tổ hợp chập 2 từ 12 : 12!/(10!.2!) = 66 trận

TỔ HỢP LẶP

KN: Tổ hợp lặp chập k từ n phần tử là một bộ gồm k phần tử

không phân biệt thứ tự, mỗi phần tử có thể được lấy lặp lại

từ n phần tử đã cho.

KH: Số tổ hợp lặp chập k từ n phần tử là

TỔ HỢP LẶP

 Phương trình sau có bao nhiêu nghiệm nguyên không âm:

Ví dụ 9:

 Giải:

 Chúng ta nhận thấy mỗi nghiệm của phương trình ứng với một cách chọn 11 phần tử từ một tập có 3 loại, sao cho có x1 phần tử loại 1, x2 phần tử loại 2, x3 phần tử loại 3 được chọn. Vì vậy số nghiệm bằng số tổ hợp chập 11 từ tập gồm 3 phần tử. Theo công thức trên ta có

x1 + x2 + x3 = 11

HOÁN VỊ CỦA TẬP HỢP CÓ CÁC PHẦN TỬ GIỐNG NHAU

KN: Giả sử có n phần tử trong đó có n1 phần tử giống nhau thuộc loại 1, n2 phần tử giống nhau thuộc loại 2, …, và nk phần tử giống nhau thuộc loại k. Khi đó số cách sắp xếp n phần tử được tính

 Số cách chọn n1 chỗ loại 1 là  Số cách chọn n2 chỗ loại 2 là  ....

như sau:

KH: Số hoán vị từ n phần tử trong đó có n1 phần tử như nhau thuộc loại 1, n2 phần tử như nhau thuộc loại 2, …, và nk phần tử như nhau thuộc loại k là:

HOÁN VỊ CỦA TẬP HỢP CÓ CÁC PHẦN TỬ GIỐNG NHAU

 Có thể nhận được bao nhiêu xâu khác nhau bằng cách sắp xếp

Ví dụ 10 :

 Giải: Từ SUCCESS có 7 chữ cái (3 chữ S, 1 chữ U, 2 chữ C và

lại các chữ cái của từ SUCCESS?

1 chữ E). Do vậy câu trả lời không phải là số hoán vị của 7 chữ

cái được!!! Theo công thức hoán vị của tập hợp có các

phần tử giống nhau ta có:

MỘT SỐ CÔNG THỨC TỔ HỢP

1.

2.

3.

(hằng đẳng thức Pascal)

(nhị thức Newton)

4.

(hằng đẳng thức Vandermonde)

5.

MỘT SỐ CÔNG THỨC TỔ HỢP

 Chứng minh:

 Giải :

 VT của đẳng thức là số tập con có k phần tử của tập có (n + m) phần tử.

 Giả sử có tập  = a1, a2, …, an, an+1, …, an+m}= 1  2 , trong đó 1 =

a1, a2, …, an và 2 = an+1, an+2, …, an+m, như vậy để chọn tập con có k

phần tử của  ta có thể chọn như sau:

 Chọn i phần tử từ tập 1 → có C(n,i) cách chọn

 Sau đó chọn k – i phần tử từ tập 2 → có C(m,k-i) cách chọn

→ có C(n,i) .C(m,k-i) cách chọn ứng với mỗi i từ 0 đến k.

 Như vậy, số cách chọn là:

Cho n là số nguyên dương, chứng minh

BÀI TẬP 1.

c.

a.

b.

2. Có tất cả bao nhiêu hoán vị của tập hợp {a,b,c,d,e,f} với

phần tử cuối cùng bằng a?

3. Một tập hợp có 100 phần tử, có bao nhiêu tập con có

nhiều hơn 2 phần tử?

4. Tìm hệ số của x101y99 trong khai triên của (2x – 3y)200 ?

5. Có bao nhiêu xâu nhị phân chứa đúng tám số 0 và

mười số 1, và ngay sau mỗi số 0 nhất thiết là một số 1?

BÀI TẬP

6. Có bao nhiêu cách chọn 8 đồng tiền xu từ hộp chứa 100

đồng một xu giống nhau và 80 đồng năm xu giống nhau?

7. Phương trình :

x1 + x2 + x3 + x4 + x5 =21

có bao nhiêu nghiệm nguyên không âm sao cho:

a. x1 ≥ 1?

b. xi ≥ 2 với i = 1, 2, 3, 4, 5

c. 0 ≤x1≤ 10?

d. *0 ≤x1 ≤ 3 và 1≤ x2 ≤4 và x3≥ 15?

8. Bất đẳng thức x1 + x2 + x3≤ 21 có bao nhiêu nghiệm

nguyên không âm?

BÀI TẬP

9. Có bao nhiêu xâu nhị phân khác nhau nếu chúng được bắt

12 bít 0 và sau mỗi bít 1 có ít nhất hai bít 0?

đầu bằng bít 1 và chứa thêm 3 bít 1 nữa, nó còn chứa tất cả

10. Có bao nhiêu xâu khác nhau có thể lập được từ chữa cái

trong từ MISSISSIPPI, yêu cầu phải dùng tất cả các chữ?