Bài giảng Toán tổ hợp - Chương 1: Tổ hợp cơ bản

Bài giảng Toán tổ hợp

Đại học Khoa học Tự nhiên, Tp HCM

2017

Bài giảng Toán tổ hợp

2017

1/40

Nội dung chương 1

Nội dung

Chương 1. Tổ hợp cơ bản

1. Nguyên lý đếm cơ bản

2. Tổ hợp

3. Tổ hợp lặp

4. Khai triển lũy thừa của đa thức

Bài giảng Toán tổ hợp

2017

2/40

Các nguyên lý đếm cơ bản

Nội dung

Các nguyên lý đếm cơ bản

1

Nguyên lý cộng

2

Nguyên lý nhân

3

Nguyên lý Derichlet

Bài giảng Toán tổ hợp

2017

3/40

Các nguyên lý đếm cơ bản

Nguyên lý cộng

Giả sử ta phải thực hiện một công việc bằng cách chọn một trong k sự

chọn lựa các phương pháp khác nhau T₁, T₂, ..., T_k. Để thực hiện T_i

(1 ≤ i ≤ k) ta có n_icách. Vậy ta số cách thực hiện công việc trên là

n₁+ n₂+ · · · + n_k.

Ví dụ. Một sinh viên có thể chọn một đề tài từ một trong 3 danh sách

các đề tài. Số đề tài trong các danh sách đề tài lần lượt là 23, 15, 19.

Hỏi sinh viên có bao nhiêu cách chọn một đề tài?

Đáp án. 23 + 15 + 19 = 57 cách.

Nhận xét. Quy tắc cộng có thể phát biểu dưới dạng của ngôn ngữ tập

hợp: Nếu A₁, A₂, . . . , A_klà các tập hợp đôi một rời nhau, khi đó

|A₁∪ A₂∪ . . . ∪ A_k| = |A₁| + |A₂| + . . . + |A_k|.

Bài giảng Toán tổ hợp

2017

4/40

Các nguyên lý đếm cơ bản

Nguyên lý nhân

Giả sử một thủ tục bao gồm k công việc kế tiếp nhau T₁, T₂, . . . , T_k.

Nếu công việc T₁có thể được thực hiện theo n₁cách, và sau khi chọn

cách thực hiện cho T₁ta có n₂cách thực hiện T₂, v.v. . . cho đến cuối

cùng, sau khi chọn cách thực hiện các công việc T₁, T₂, ..., T_k−1ta có n_k

cách thực hiện T_k. Vậy ta có cách để thực hiện thủ tục này là:

n₁× n₂× ... × n_k

Ví dụ.

Hỏi có nhiêu cách đi từ A đến C?

Đáp án. 3 × 2 = 6 cách.

Bài giảng Toán tổ hợp

2017

5/40

Các nguyên lý đếm cơ bản

Nguyên lý nhân

Nhận xét. Quy tắc nhân có thể phát biểu dưới dạng của ngôn ngữ

tập hợp: Nếu A₁, A₂, . . . , A_klà các tập hữu hạn, khi đó

|A₁× A₂× . . . × A_k| = |A₁| × |A₂| × . . . × |A_k|.

Ví dụ. Có bao nhiêu chuỗi bit có độ dài 8?

Giải. Mỗi bit có thể chọn 1 trong 2 cách: 0 hoặc 1. Theo nguyên lý

nhân ta có số lượng chuỗi là 2⁸= 256.

Ví dụ. Cho tập A gồm 6 phần tử và tập B gồm 10 phần tử. Hỏi

a) Có bao nhiêu ánh xạ từ A vào B?

b) Có bao nhiêu đơn ánh từ A vào B?

Bài giảng Toán tổ hợp

2017

6/40

Các nguyên lý đếm cơ bản

Nguyên lý nhân

Giải. a) Với mỗi phần tử x của A ta có 10 cách chọn ảnh của x (vì B

có 10 phần tử). Theo nguyên lý nhân, ta có 10⁶ánh xạ.

b) Giải sử A = {x₁, x₂, . . . , x₆}. Ta chia bài toán thành 6 bước:

Bước 1. Chọn ảnh của x₁có 10 cách.

Bước 2. Chọn ảnh của x₂có 10 − 1 = 9 cách.

................

Bước 6. Chọn ảnh của x₆có 10 − 5 = 5 cách.

Vậy số đơn ánh là: 10 × 9 × 8 × 7 × 6 × 5 = 151200.

Bài giảng Toán tổ hợp

2017

7/40

Các nguyên lý đếm cơ bản

Nguyên lý Derichlet

Nguyên lý Derichlet (chuồng bồ câu)

Ví dụ.

Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày.

Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1

chuồng có 3 con bồ câu trở lên.

Định nghĩa. Giá trị trần của x, ký hiệu là dxe, là số nguyên nhỏ

nhất mà lớn hơn hay bằng x.

Ví dụ. d2.1e = 3; d1.9e = 2; d4e = 4;

d−1.1e = −1. d−2.9e = −2; d−4e = −4.

Nguyên lý Derichlet

Nếu có n đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa

l m

n

ít nhất

đồ vật.

k

Bài giảng Toán tổ hợp

2017

8/40

Các nguyên lý đếm cơ bản

Nguyên lý Derichlet

l m

n

k

Chứng minh. Giả sử mọi hộp đều chứa ít hơn

vật. Khi đó tổng

số đồ vật nhỏ hơn hoặc bằng

ꢀ l m

ꢁ

ꢀ ꢁ

n

k

− 1 < k

= n.

k

Điều này mâu thuẩn với giả thiết là có n đồ vật cần xếp.

ꢂ

ꢃ

100

12

Ví dụ. Trong 100 người thì có ít nhất

= 9 cùng tháng sinh.

Ví dụ. Trong một lớp học phải có ít nhất bao nhiêu học sinh để cho có

ít nhất 6 học sinh có cùng thứ bậc học tập, biết rằng có 5 loại thứ bậc

A, B, C, D và E?

Giải. Gọi số học sinh của lớp là N. Theo nguyên lý Derichlet ta có

N

d ₅e = 6. Khi đó

25 < N ≤ 30.

Do đó ta có thể chọn N = 26. Vậy lớp phải có ít nhất 26 học sinh.

Bài giảng Toán tổ hợp

2017

9/40

Các nguyên lý đếm cơ bản

Nguyên lý Derichlet

Ví dụ. Chứng minh rằng trong 10 số tự nhiên bất kỳ có thể chọn hai

số có hiệu chia hết cho 9.

Giải. Khi chia 10 số bất kỳ cho 9 ta sẽ có mỗi số có một số dư trong 9

số dư: 0, 1, 2, . . . , 7, 8. Do đó theo nguyên lý Dirichlet phải tồn tại ít

nhất hai số có cùng số dư. Hiệu của hai số đó sẽ chia hết cho 9.

Ví dụ. Cho tập X = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Lấy A là tập hợp con của

X gồm 6 phần tử. Khi đó trong A sẽ chứa hai phần tử có tổng bằng 10.

Giải. Ta lập các hộp như sau: {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}. Do A

có 6 phần tử nên khi sắp xếp 6 phần tử đó sẽ có hộp có 2 phần tử. Rõ

ràng tổng 2 phần tử này bằng 10.

Bài giảng Toán tổ hợp

2017

10/40

Tổ hợp

Nội dung

Tổ hợp

1

Hoán vị

2

3

Chỉnh hợp

Tổ hợp

Bài giảng Toán tổ hợp

2017

11/40

Tổ hợp

Hoán vị

Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ

tự n phần tử của A được gọi là một hoán vị của n phần tử.

Ví dụ. Cho A = {1, 2, 3}. Khi đó A có các hoán vị sau:

123, 132, 213, 231, 312, 321

Mệnh đề. Số các hoán vị của n phần tử, ký hiệu là P_n

P_n= n! = n × (n − 1) × (n − 2) × . . . × 1

Quy ước 0! = 1.

Ví dụ. Cho X = {1, 2, 3, 4, 5}. Hỏi có bao nhiêu số tự nhiên gồm 5 chữ

số khác nhau được tạo từ tập X?

Bài giảng Toán tổ hợp

2017

12/40

Tổ hợp

Hoán vị

Ví dụ. Cần sắp xếp 5 học sinh A, B, C, D, E thành một dãy hàng dọc

a) Hỏi có bao nhiêu cách sắp xếp.

b) Hỏi có bao nhiêu cách sắp xếp sao cho hai học sinh A và B luôn

đứng ở hai đầu hàng ?

Giải. a) Để xếp 5 học sinh theo một dãy hàng dọc ta chỉ cần xếp 5 học

sinh theo thứ tự. Vậy có P₅= 5! = 120 cách.

b) Do 2 bạn A, B đứng đầu hàng nên có 2! = 2 cách xếp 2 bạn đứng

đầu. Ba vị trí còn lại ta chọn 3 học sinh còn lại và xếp theo thứ tự nên

có 3! = 6 cách. Vậy theo nguyên lý nhân ta có: 2! × 3! = 2 × 6 = 12

cách.

Ví dụ. Từ 6 chữ số 1, 2, 3, 4, 5, 6 có thể lập được bao nhiêu số tự nhiên

gồm 6 chữ số khác nhau, trong đó có bao nhiêu số lẻ? bao nhiêu số

không chia hết cho 5?

Bài giảng Toán tổ hợp

2017

13/40

Tổ hợp

Hoán vị

Giải. Để có số tự nhiên có 6 chữ số khác nhau ta chọn sắp xếp 6 chữ

số đã cho theo thứ tự. Nên có P₆= 6! = 720 số.

Gọi x = abcdef là số có 6 chữ số khác nhau.

Nếu x là số lẻ thì f ∈ {1, 3, 5} nên f có 3 cách chọn. Năm số còn

lại a b c d e là hoán vị của 5 chữ số còn lại (vì đã loại đi số f). Nên

có 5! cách chọn. Vậy theo qui tắc nhân ta có 3 × 5! = 360 số lẻ

Tương tự như lý luận trên, ta có 5! số chia hết cho 5. Như vậy số

không chia hết cho 5 là 6! − 5! = 600.

Ví dụ. Cần sắp xếp 3 sinh viên nữ và 5 sinh viên nam thành một hàng

dọc.

a) Hỏi có bao nhiêu cách sắp xếp nếu 3 sinh viên nữ luôn đứng liền

nhau ?

b) Hỏi có bao nhiêu cách sắp xếp nếu sinh viên đứng đầu hàng là sinh

viên nữ và sinh viên cuối hàng là sinh viên nam ?

Đáp án. a) 5! × 6 × 3! = 4320 cách

b) 3 × 5 × 6! = 10800 cách

2017 14/40

Bài giảng Toán tổ hợp

Tổ hợp

Chỉnh hợp

Định nghĩa. Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử

(1 ≤ k ≤ n) 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ử.

Ví dụ. Cho X = {a, b, c}. Khi đó X có các chỉnh hợp chập 2 của 3 là:

ab, ba, ac, ca, bc, cb

Mệnh đề. Số các chỉnh hợp chập k của n, ký hiệu là A^k_n, và

n!

A^k_n= n × (n − 1) × · · · × (n − k + 1) =

(n − k)!

Ví dụ. Có bao nhiêu số tự nhiên khác nhau ngồm 3 chữ số được tạo

thành từ 1, 2, 3, 4, 5, 6.

Đáp án. A³₆số.

Bài giảng Toán tổ hợp

2017

15/40

Tổ hợp

Chỉnh hợp

Ví dụ. Một lớp có 15 học sinh nam và 20 nữ. Trong buổi tập trung lớp

đầu năm, giáo viên chọn 3 học sinh làm ban cán sự lớp: 1 lớp trưởng, 1

lớp phó và 1 thủ quỹ.

a) Hỏi có bao nhiêu cách chọn ?

b) Hỏi có bao nhiêu cách chọn nếu lớp trưởng là nam.

c) Hỏi có bao nhiêu cách chọn nếu trong 3 bạn được chọn phải có ít

nhất 1 nữ.

Đáp án. a) A³₃₅

b) 15 × A²₃₄

c) A³₃₅− A³₁₅

Bài giảng Toán tổ hợp

2017

16/40

Tổ hợp

Định nghĩa. Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k phần

tử của A được gọi là một tổ hợp chập k của n phần tử.

Ví dụ. Cho X = {1, 2, 3, 4}. Tổ hợp chập 3 của 4 phần tử của X là

{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}

!

n

Định nghĩa. Số tổ hợp chập k của n phần tử được kí hiệu là

k

hay C_n^k,

A_n^k

n!

C_n^k=

=

k!

k!(n − k)!

Ví dụ. Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn?

10

Đáp án. C cách.

30

Bài giảng Toán tổ hợp

2017

17/40

Tổ hợp

Ví dụ. Một lớp có 40 sinh viên gồm 25 nam và 15 nữ. Ta cần chọn ra

6 sinh viên tham gia hội nghị của trường. Hỏi có bao nhiêu cách chọn

nếu:

a) Không phân biệt nam nữ ?

b) Có 4 nam và 2 nữ ?

c) Có ít nhất là 4 sinh viên nam ?

Bài giảng Toán tổ hợp

2017

18/40

Tổ hợp

Ví dụ. Một lớp có 40 sinh viên gồm 25 nam và 15 nữ. Ta cần chọn ra

6 sinh viên tham gia hội nghị của trường. Hỏi có bao nhiêu cách chọn

nếu:

a) Không phân biệt nam nữ ?

b) Có 4 nam và 2 nữ ?

c) Có ít nhất là 4 sinh viên nam ?

Đáp án. a) C₄⁶₀

b) C₂⁴₅× C₁²₅

c) C₂⁴₅× C₁²₅+ C₂⁵₅× C₁¹₅+ C₂⁶₅× C₁⁰₅

Bài giảng Toán tổ hợp

2017

18/40

Tổ hợp

Ví dụ. Có bao nhiêu cách sắp xếp 5 bác sĩ, 4 kỹ sư, 3 luật sư vào một

bàn dài có 12 chỗ ngồi (được đánh số từ 1 đến 12) trong mỗi trường

hợp sau:

a) không có điều kiện gì thêm?

b) các đồng nghiệp ngồi cạnh nhau?

c) các bác sĩ ngồi cạnh nhau ở một đầu bàn, còn các kỹ sư, luật sư

ngồi xen kẻ ở đầu bàn còn lại?

Bài giảng Toán tổ hợp

2017

19/40