Bài toán đếm Toán rời rạc PDF

Preview

Summary

Chương 2ương 2. BÀI TOÁN ĐBÀI TOÁN ĐẾẾMM2. PHÁT BIỂU BÀI TOÁNDạng tổng quát nhất của bài toán đếm có thể phát biểu ngắn gọn như sau: Cho một tập rời rạc A; tìm bản số |A| của tập A, tức là hãy đếm xem A có bao nhiêu phần tử. Khi đếm các phần tử của A phải đảm bảo nghiêm ngặt 2 nguyên tắc: Một là: Kh...

Description

TOÁN RỜI RẠC – Lý thuyết

Chương 2. BÀI TOÁN Đ ẾM 2.1. PHÁT BIỂU BÀI TOÁN Dạng tổng quát nhất của bài toán đếm có thể phát biểu ngắn gọn như sau: Cho một tập rời rạc A; tìm bản số |A| của tập A, tức là hãy đếm xem A có bao nhiêu phần tử. Khi đếm các phần tử của A phải đảm bảo nghiêm ngặt 2 nguyên tắc: Một là: Không bỏ sót, nghĩa là phần tử nào cũng được đếm. Hai là: Không trùng lặp, nghĩa là không có phần tử nào được đếm quá một lần. Phương pháp tổng quát để giải bài toán đếm có thể diễn giải như sau: Giả sử A là tập cần đếm, N = {1, 2, 3, ..., n} là tập n số nguyên dương đầu tiên. Nếu lập được sự tương ứng đơn trị hai chiều giữa các phần tử của A và các phần tử của N; nghĩa là tìm được một song ánh f f : A « Nthì | A | = n Tuy nhiên có rất nhiều cách cho tập A khác nhau nên phương pháp nêu trên chỉ có ý nghĩa như một định hướng tổng quát, còn trên thực tế thì người ta phải căn cứ vào hình thái cụ thể của tập A mà tìm ra một giải pháp thích hợp. Hãy xét một vài ví dụ dưới đây để thấy rõ điều đó Thí dụ 1. Cho A = {x}: x là các số nguyên, dương, £ 100 và x 2 - 1 chia hết cho 24. Tìm |A|. Thí dụ 2. Cho A = {x}: x là các con số hàng nghìn mà các chữ số của nó tạo thành một dãy tăng (thí dụ 1348, 2569, …). Về mặt hình thức thì trong hai thí dụ trên đều là tìm các con số thỏa mãn những điều kiện nhất định; nhưng trong thí dụ 2 thì mỗi con số lại là một cấu hình tổ hợp gồm 4 chữ số chọn trong 9 chữ số và xếp theo một thứ tự nhất định. Việc đếm các cấu hình tổ hợp như vậy nói chung là phức tạp hơn. Thí dụ 3. Một người vượt cầu thang có 13 bậc, lúc thì bước 1 bậc, lúc thì bước 2 bậc, lúc thì bước 3 bậc một bước. Hỏi có bao nhiêu cách vượt cầu thang như thế, tập A ở đây là tập các cách vượt cầu thang, có ý nghĩa như là tập

28

TOÁN RỜI RẠC – Lý thuyết

các “giải pháp” cho một vấn đề đặt ra, phức tạp hơn nhiều so với các thí dụ trước. Thí dụ 4. Có bao nhiêu lần lặp trong đoạn chương trình C++ dưới đây: int n1 = 5, n2 = 10, S = 0;

for (int i = 1; i < = n1 ; i + + ) S + +; for (int i = 1; i < = n2 ; i + + ) S + +; Số lần lặp ở đây tương ứng với số phép toán để thực hiện đoạn chương trình nói trên. Mở rộng thí dụ này, vấn đề đặt ra có thể là: Tìm số phép toán của chương trình thực hiện một thuật toán nào đó; con số này đặc trưng cho độ phức tạp của thuật toán. Thí dụ 5. Một loài khuẩn sinh trưởng theo nguyên tắc sau đây: khi đủ a ngày tuổi (a nguyên dương) thì nó bắt đầu sinh sản, mỗi ngày một lứa, mỗi lứa sinh được b khuẩn con (b nguyên dương). Tại thời điểm t = 0 , số khuẩn là n 0 con đều là mới sinh ra. Tìm số khuẩn n T tại thời điểm T > a (T nguyên dương) với giả thiết trong khoảng thời gian t Î [0, T] không có con khuẩn nào bị chết. A ở đây là tập các con khuẩn trong quá trình sinh trưởng của nó. Qua các thí dụ trên ta thấy tập A có rất nhiều hình thái khác nhau, do đó phương pháp đếm các phần tử của A cũng có một đa dạng tương ứng. Mỗi phương pháp đếm là một thuật toán, nên trước tiên ta tìm hiểu những khái niệm cơ bản về thuật toán.

2.2. KHÁI NIỆM THUẬT TOÁN 2.2.1. Định nghĩa Thuật toán giải một bài toán nào đó, có thể hiểu một cách trực quan là một dãy hữu hạn các bước chỉ rõ những thao tác toán học phải thực hiện trên các đối tượng để thu được lời giải của bài toán. Thuật toán có các đặc trưng sau: a)Tính hữu hạn, còn gọi là tính dừng của thuật toán. b)Tính chính xác. Tại mỗi bước các thao tác toán học phải được chỉ ra 1 cách chính xác, không cần tư duy, chỉ cần thực hiện một cách máy móc. Đó cũng là cách đưa tư duy toán học vào máy tính. 29

TOÁN RỜI RẠC – Lý thuyết

c) Tính đơn trị. Các kết quả trung gian của các bước của thuật toán phải xác định một cách đơn trị, chỉ phụ thuộc vào input (đầu vào) và kết quả của bước trước. d) Tính phổ dụng. Thuật toán có thể giải được bất kỳ bài toán nào trong lớp bài toán bài toán đã cho. e) Tính tối ưu. Khi xây dựng thuật toán cần chú ý đến việc bảo đảm điều kiện tốt nhất cho quá trình thực hiện, bao gồm việc sắp xếp các input, output, bố trí chặt chẽ các thao tác để giảm thiểu phép toán và do đó giảm đến mức thấp nhất thời gian thực hiện thuật toán. 2.2.2. Biểu diễn thuật toán Có 3 cách biểu diễn thuật toán, mỗi cách đều có ưu nhược điểm nhất định nên tùy theo từng trường hợp ta lựa chọn sao cho thích hợp. a)Biểu diễn bằng ngôn ngữ tự nhiên, liệt kê các bước của thuật toán. Thí dụ. Giải phương trình bậc 2: ax2 + bx + c = 0 với a, b, c là các số thực và a¹0 Bước 1: Đưa vào input a, b, c Bước 2: Tính biệt số D = b 2 - 4ac Bước 3: Xét dấu D Nếu D ³ 0 chuyển sang bước 4. Ngược lại chuyển sang bước 5. Bước 4: Tính nghiệm

-b + D -b - D ; x2 = 2a 2a (Output) đưa ra thông báo nghiệm của phương trình là x1 và x 2 , x1 =

chuyển sang bước 6. Bước 5: (Output) đưa ra thông báo phương trình vô nghiệm. Bước 6: Kết thúc. b)Biểu diễn bằng sơ đồ khối. Phương pháp này sử dụng các biểu trưng hình học quy ước để diễn đạt các bước và thao tác cần thực hiện trong thuật toán. Ta quy ước có các khối sau:

30

TOÁN RỜI RẠC – Lý thuyết

Nút khởi đầu hoặc kết thúc Nút thao tác, ghi câu lệnh cần thực hiện Nút điều kiện, ghi rõ điều kiện cần kiểm tra trong quá trình tính toán Cung, dùng để chỉ đường đi của thuật toán Thí dụ.

Sơ đồ khối mô tả thuật toán giải phương trình bậc hai:

ax2 + bx + c = 0 như sau Bắt đầu

Input a, b, c

D = b2 - 4ac

D³0

sai

Thông báo PT vô nghiệm

đúng

x1, 2 =

-b ± D 2a

Thông báo pt có 2 nghiệm là x1 và x2

Kết thúc Ưu điểm của phương pháp này là có tính phổ dụng cao, khắc phục được tính đa nghĩa và hàng rào ngôn ngữ, rất tiện lợi trong chuyên ngành toán và tin học. 31

TOÁN RỜI RẠC – Lý thuyết

2.2.3. Phương pháp quy nạp Quy nạp toán học là một phương pháp hữu hiệu để chứng minh một mệnh đề toán học đúng với mọi số tự nhiên n. Để thực hiện điều đó ta phải tiến hành các bước sau: Bước 1: Chứng minh mệnh đề đúng với n = 1. Bước 2: Giả sử mệnh đề đã đúng với n, ta chứng minh mệnh đề đúng với (n + 1) Thí dụ 1. Chứng minh rằng " n Î N*

n(n + 1)(2n + 1) 6 1(1 + 1)(2 + 1) Bước 1: Với n = 1 ta có 12 = . Vậy công thức đúng với n = 1 6 Bước 2: Giả sử công thức trên đúng với n, tức là ta có n(n + 1)(2n + 1) 12 + 2 2 + ... + n 2 = 6 Ta phải chứng minh công thức đúng với (n + 1) , nghĩa là: 12 + 2 2 + ... + n 2 =

(n + 1)(n + 2)(2n + 3) 6 n(n +1)(2n +1) Ta có vế trái = 12 + 22 + ... + n 2 + (n + 1) 2 = + (n + 1) 2 6 (n + 1)(n + 2)(2n + 3) = =vế phải. 6 Vậy công thức được chứng minh. Thí dụ 2.Tìm tổng S = 1.2 + 2.3 + ... + n(n + 1) 12 + 22 + ... + n 2 + (n + 1) 2 =

2.3.4 3 3.4.5 1.2 + 2.3 + 3.4 = 20 = 3 Ta thấy 1.2 + 2.3 = 8 =

n(n + 1)(n + 2) 3 Vấn đề đặt ra là dự đoán này có đúng không. Ta kiểm tra sự đúng đắn này bằng phương pháp quy nạp: 1.2.3 Bước 1: Với n = 1 ta có 1.2 = . Vậy công thức đúng với n = 1 3

Vậy có thể dự đoán 1.2 + 2.3 + ... + n(n + 1) =

32

TOÁN RỜI RẠC – Lý thuyết

Bước 2: Giả sử công thức trên đúng với n, ta phải chứng minh công thức đúng với (n + 1), nghĩa là:

1.2 + 2.3 + ... + n(n + 1) + (n + 1)(n + 2) =

(n + 1)(n + 2)(n + 3) 3

Ta có vế trái = 1.2 + 2.3 + ... + n(n + 1) + (n + 1)(n + 2)

n(n + 1)(n + 2) + (n + 1)(n + 2) 3 (n + 1)(n + 2)(n + 3) = = vế phải. 3 Vậy dự đoán trên là đúng. Tuy nhiên cần thấy rằng quy nạp toán học không phải là phương pháp duy nhất để giải quyết lớp các bài toán như vậy (xem lời giải bài tập 2.1, ý d) chương 2) 2.2.4. Phương pháp đệ quy Đệ quy là khái niệm rất hay gặp trong toán học cũng như trong lập trình, nó cho phép ta mô tả một cách ngắn gọn và sáng sủa các đối tượng cũng như các quá trình liên quan đến dãy số tự nhiên. Như vậy đệ quy là một phương pháp xác định các đối tượng thỏa mãn một tính chất nào đó; nó bao gồm các quy tắc, trong đó một số quy tắc để xác định các đối tượng ban đầu và quy tắc còn lại dùng để xác định các đối tượng tiếp theo nhờ các đối tượng ban đầu đã được xác định. Thí dụ. Cho dãy số a 0, a 1, a 2, ..., a n, ... có tính chất sau: =

a 0 = 0, a 1 = 1 và a n = a n -1 + a n -2; " n ³ 2 . Đó chính là dãy Fibonacci mà " n ³ 2 ta có thể tìm được số Fibonacci thứ n nếu biết số Fibonacci thứ (n - 1) và thứ (n - 2) . Bằng quy nạp toán học hoặc bằng cách giải phương trình truy hồi tuyến tính cấp 2 hệ số hằng ta có thể chứng minh rằng " n ³ 0 ta có: n

n

1 æ1 + 5 ö 1 æ1 - 5 ö an = ç ÷ ç ÷ 5è 2 ø 5è 2 ø Tuy nhiên ta có thể tính a n trực tiếp như sau: Trước hết hãy tìm cặp số a, b sao cho

a n - aa n -1 = b(a n -1 - aa n -2) Suy ra a n = (a + b)a n -1 - a .b a n -2 Từ điều kiện a n = a n -1 + a n -2 ta suy ra a + b = 1 và a.b = - 1 33

TOÁN RỜI RẠC – Lý thuyết

Khi đó a và b là nghiệm của phương trình x 2 - x - 1 = 0 ; do đó có thể chọn

1+ 5 1- 5 và b = 2 2 Đặt q n = a n - a.a n -1 thì sẽ có q n = b.q n -1 với n ³ 2 và q 1 = 1 a=

Từ đó suy ra q n = bn- 1 Vậy ta có a n - a.a n -1 = b n -1 hay a n = a.a n -1 + b n- 1 Từ đây suy ra

a 2 = a.a 1 + b

(1)

a 3 = a.a 2 + b 2

(2)

a 4 = a.a 3 + b 3

(3)

………………

a n - 1 = a.a n -2 + bn- 2

(n - 2)

a n = a.a n -1 + bn -1

(n - 1)

Nhân 2 vế của đẳng thức thứ k với an - 1- k ; (k = 1, 2, 3, ..., n - 1) rồi cộng vế với vế ta có: a n = a n -1 .a 1 + a n -2b + a n -3b 2 + ... + a .b n -2 + b n -1 =

Ta thấy a =

an - bn a-b

(vì a 1 = 1)

1+ 5 1- 5 ; b= nên a - b = 5 và ta có: 2 2 n

n

1 æ1 + 5 ö 1 æ1 - 5 ö an = ç ÷ ç ÷ 5è 2 ø 5è 2 ø Điều phải chứng minh.

2.3. CÁC TỔ HỢP KHÔNG LẶP 2.3.1. Chỉnh hợp Định nghĩa. Chỉnh hợp chập k của n phần tử là một nhóm gồm k phần tử lấy trong n phần tử đã cho và sắp xếp theo một thứ tự nhất định. Ở đây mỗi phần tử chỉ được lấy một lần (không lặp). Thí dụ. Cho X = {0, 1, 2, 3, 4, 5} gồm 6 phần tử. 34

TOÁN RỜI RẠC – Lý thuyết

Các nhóm dưới đây 123, 213, 402, 305, … đều là các chỉnh hợp chập 3 của 6 phần tử. Hai chỉnh hợp 123 và 213 có các phần tử như nhau nhưng khác nhau về thứ tự. Như vậy hai chỉnh hợp là khác nhau nếu chúng có ít nhất một phần tử khác nhau hoặc thứ tự các phần tử khác nhau. Để xây dựng một chỉnh hợp ta xây dựng dần từ thành phần đầu tiên. Thành phần đầu tiên có n cách chọn, thành phần thứ hai chỉ có (n - 1) khả năng chọn, …, thành phần thứ k chỉ có (n - k + 1) khả năng chọn. Nếu ký hiệu số chỉnh hợp chập k của n phần tử là A kn thì ta có:

A kn = n.(n - 1). ... .(n - k + 1)

(1)

Thí dụ. Từ các phần tử của X đã cho ở trên, có thể lập được bao nhiêu con số hàng trăm mà các chữ số là khác nhau? Ta thấy ngay S = A36 - A52 = 6.5.4 - 5.4 = 120 - 20 = 100 số. Ở đây, A 25 chính là số các chỉnh hợp chập 3 có số 0 đứng ở phía trước; con số này không phải con số hàng trăm. 2.3.2. Hoán vị Định nghĩa. Hoán vị của n phần tử là một cách sắp xếp thứ tự n phần tử đó. Ký hiệu số hoán vị là Pn thì

Pn = Ann = n.(n - 1). ... .2.1 = n!

(2)

Thí dụ. Có 5 người dàn hàng ngang chụp ảnh, hỏi có bao nhiêu kiểu ảnh khác nhau? Mỗi kiểu ảnh là một hoán vị, vậy số kiểu ảnh là: P5 = 5! = 120 2.3.3. Tổ hợp Định nghĩa. Tổ hợp chập k của n phần tử là một nhóm gồm k phần tử lấy trong n phần tử đã cho (không kể thứ tự). Nếu ký hiệu Ckn là số tổ hợp chập k của n phần tử thì dễ dàng thấy rằng: A kn n.(n - 1). ... .(n - k + 1) = C .Pk = A Þ C = Pk k! k n

k n

k n

(3)

Nếu chú ý rằng Ckn là số nguyên thì ta có nhận xét thú vị sau đây: Tích của k số tự nhiên liên tiếp nhau luôn chia hết cho tích của k số tự nhiên đầu tiên (k!). 35

TOÁN RỜI RẠC – Lý thuyết

Thí dụ 1. Có 10 người thi đấu bóng bàn vòng tròn, hỏi có bao nhiêu trận đấu? Cứ 2 người tạo nên 1 trận đấu, mỗi trận đấu là một tổ hợp chập 2 của 10. Vậy số trận đấu là: 10.9 C210 = = 45trận 1.2 Thí dụ 2. Có bao nhiêu dãy nhị phân độ dài 10 có đúng 3 số 1 (và 7 số 0). Mỗi dãy nhị phân như thế tương ứng với việc chọn 3 vị trí trong 10 vị trí để gán số 1 tức là tương ứng với một tổ hợp chập 3 của 10 phần tử. Vậy số dãy nhị phân cần tìm là:

10.9.8 = 120 1.2.3 Các số tổ hợp C kn rất hay gặp trong toán rời rạc, ta thường gọi là hệ số tổ C310 =

hợp. Dưới đây là một số công thức đáng nhớ: n! C kn = k!.(n - k)!

(4) (5)

C kn = C nn- k Ckn = Ckn --11 + C kn -1 ;

(n > k > 0)

(6)

Chứng minh các công thức (4), (5), (6) rất đơn giản, xin dành cho độc giả. Để có thể áp dụng công thức (4) và (5) cho mọi k £ n ta quy ước:

C 0n = C nn = 1và 0! = 1 Chú ý: - Công thức (5) giúp ta tính toán nhanh hơn. Thay cho tính Ckn ta sẽ tính

Cnn -k nếu n - k < k Thí dụ.Tính C810 ; ta thấy 10 - 8 = 2 < 8 nên ta tính

10.9 = 45 1.2 - Công thức (6) với quy ước C0n = 1 cho phép ta tính tất cả các hệ số tổ hợp 2 C810 = C10 =

chỉ bằng phép cộng. Các hệ số này được tính và viết theo quy tắc sau: Các dòng tương ứng với n = 0, 1, 2, ... ; các cột tương ứng với k = 0, 1, 2, ... và ta có bảng tam giác dưới đây gọi là tam giác Pascal

36

TOÁN RỜI RẠC – Lý thuyết

C 00 C10

C11

C02

C12

C 22

C 03

C13

C 23

C 33

….

....

....

….

2 n

3 n

0 n

C

1 n

C

C

…. ….

C

C nn- 1

Cnn

Dòng hệ số tổ hợp cuối cùng: C0n , C1n , C2n , …, Cnn -1 , Cnn là các hệ số trong khai triển nhị thức Newton: n

(x + y) n =

åC .x k n

k

y n- k

k= 0

Cho y = 1 ta có công thức: n n

(x + 1) =

å C .x k n

(7)

k

k= 0

Từ hệ thức này ta suy ra một số công thức sau đây: - Cho x = 1 thì sẽ có: (8)

C0n + C1n + Cn2 + ... + Cnn = 2n - Cho x = - 1 thì sẽ có:

C0n - C1n + Cn2 - C3n ... + (-1)n Cnn = 0 Từ đó suy ra

C0n + Cn2 + ... = C1n + C3n + ... = 2n - Đạo hàm theo x hai vế của (7) rồi thay x = 1 sẽ có: C1n + 2C n2 + ... + nC nn = n2 n -1

-1

(9) (10)

2.4. CÁC TỔ HỢP CÓ LẶP 2.4.1. Chỉnh hợp lặp Định nghĩa. Chỉnh hợp lặp chập k của n phần tử là một nhóm gồm k phần tử lấy trong n phần tử đã cho và sắp xếp theo một thứ tự nhất định; các phần tử có thể lấy lặp. Thí dụ 1. Với X = {0, 1, 2, 3, 4, 5} các chỉnh hợp lặp chập 3 có thể là 123, 213, 211, 111, …

37

TOÁN RỜI RẠC – Lý thuyết

Nếu ký hiệu Lkn là số chỉnh hợp lặp chập k của n phần tử thì dễ dàng thấy rằng mỗi thành phần của nó đều có n cách lựa chọn nên ta có công thức:

Lkn = n k

(11)

Chú ý rằng trong chỉnh hợp lặp số k không bị giới hạn bởi điều kiện k £ n mà trái lại k có thể lấy giá trị lớn hơn n. Chẳng hạn như với 3 chữ số 1, 2, 3 ta vẫn có thể lập được các con số hàng triệu gồm 7 chữ số: 1 222 333; 2 221 111; … Thí dụ 2. Từ các chữ số thuộc X = {0, 1, 2, 3, 4, 5} có thể lập được bao nhiêu con số hàng trăm? Mỗi con số hàng trăm là một chỉnh hợp lặp chập 3 của 6 chữ số đã cho, loại trừ các chỉnh hợp lặp có số 0 đứng trước. Do đó ta có số các con số hàng trăm là:

s = L36 - L26 = 6 3 - 6 2 = 180số 2.4.2. Hoán vị lặp. Ta hãy xét 2 nhóm gồm 5 chữ cái: THANG và NHANH Nếu ta hoán vị 5 chữ cái trong nhóm THANG thì sẽ được P5 = 5! = 120 hoán vị khác nhau. Nhưng khi hoán vị các chữ cái trong nhóm NHANH thì sẽ không được 120 hoán vị khác nhau; vì khi ta đổi vị trí 2 chữ N với nhau hoặc 2 chữ H với nhau thì sẽ không tạo ra một hoán vị mới. Trong các hoán vị này, chữ N lặp 2 lần, chữ H lặp 2 lần, ta gọi đó là các hoán vị lặp. Số hoán vị lặp trong trường hợp này dễ dàng tính được là: 120 = 30 2.2 Bây giờ ta xét trường hợp tổng quát: Cho k phần tử khác nhau; ta ký hiệu P(n1 , n 2 , ..., n k ) là số hoán vị của k phần tử trên, trong đó phần tử thứ nhất lặp n1 lần, phần tử thứ hai lặp n 2 lần, …, phần tử thứ k lặp n k lần. Ta dễ dàng chứng minh được công thức sau đây: (n + n2 + ... + nk )! P(n1 , n 2 , ..., n k ) = 1 n 1! n 2 !... n k !

38

(12)

TOÁN RỜI RẠC – Lý thuyết

Thí dụ. Hoán vị các chữ cái trong tên của dòng sông MISSISIPI, ta thấy ở đây chỉ có 4 chữ cái M, P, S, I trong đó M và P không lặp, S lặp 3 lần, I lặp 4 lần. Vậy số hoán vị là: (1 + 1 + 3 + 4)! 9! = = 2520 P(1, 1, 3, 4) = 1!1! 3!4! 3!4! Nếu ta đặt n = n1 + n 2 + ... + n k thì sẽ có định lý sau đây: Định lý 1. Ký hiệu C n (n1, n 2 , ..., n k ) là số cách chia n phần tử khác nhau thành k nhóm với số các phần tử tương ứng là n1 , n 2 , ..., n k . Nếu ni ¹ n j " i ¹ j thì

Cn (n1 , n2 , ..., n k ) = P(n1 , n2 , ..., n k ) . Chứng minh. Không mất tính tổng quát ta chỉ cần chứng minh cho trường hợp k = 3 . Thật vậy, ta có Cnn1 là số cách chọn n1 phần tử trong n phần tử. Tương ứng với mỗi cách chọn n1 phần tử cho nhóm thứ nhất, ta còn lại

n - n1 = n 2 + n3 phần tử; do đó có Cnn 22 + n 3 cách chọn n 2 phần tử cho nhóm thứ hai. Đương nhiên sau khi chọn n 2 phần tử cho nhóm thứ hai thì sẽ còn lại

n 3 phần tử của nhóm thứ ba. Vậy số cách chia ấy là: Cn (n1 , n2 , n3 ) = Cnn 1 .Cnn 22 + n 3 =

n! (n + n3 )! (n1 + n2 + n3 )! . 2 = n1 !(n - n1 )! n 2 !n 3 ! n1 !n2 !n3 !

Với chú ý rằng n = n1 + n 2 + n3 thì ta có:

C n (n1, n 2 , n 3 ) = P(n1 , n 2 , n 3 ) Điều phải chứng minh. Thí dụ 1. Có bao nhiêu cách chia bộ bài tú lơ khơ 52 quân thành 4 phần tương ứng với số quân là 10, 12, 14, 16. Vì số quân của các phần khác nhau nên 52! C52 (10, 12, 14, 16) = 10!12!14!16! Giả thiết n i ¹ n j " i ¹ j là để cho các nhóm được tạo thành không có sự trùng lặp. Nếu n1 = n 2 = ... = n i (i < k) tức là có i nhóm có số phần tử bằng nhau thì công thức tính sẽ là: 39

TOÁN RỜI RẠC – Lý thuyết

Cn (n1 , n2 , ..., ni , ni +1 , ..., n k ) =

P(n1 , n 2 , ..., n k ) i!

Nghĩa là số cách chia nhóm sẽ giảm đi i! lần. Thí dụ 2. Chia 4 đối tượng a, b, c, d thành 2 nhóm, mỗi nhóm gồm 2 đối tượng thì chỉ có 3 cách (a, b) và (c, d) (a, c) và (b, d) (a, d) và (b, c) Chú ý rằng nếu lấy ra 2 đối tượng từ 4 đối tượng thì có C 24 = 6 cách, nhưng chia thành 2 nhóm, mỗi nhóm 2 đối tượng thì lại chỉ có: P(2, 2) 4! 24 C4 (2, 2) = = = = 3 cách như trên. 2! 2!. 2!2! 8 Thí dụ 3. Có bao nhiêu cách chia bộ bài tú lơ khơ 52 quân thành 4 phần bằng nhau? Khi đó mỗi phần có 13 quân nên: P(13, 13, 13, 13) 52! C52 (13, 13, 13, 13) = = 4! 4!. (13!)4 2.4.3. Tổ hợp lặp Định nghĩa.Tổ hợp lặp chập k của n phần tử là một nhóm gồm k phần tử lấy (có thể lặp) trong n phần tử đã cho. Giống như trong chỉnh hợp lặp, số k có thể lớn hơn n. Thí dụ 1. Hai quả cam, ba quả quýt, bốn quả chanh có thể coi như tổ hợp lặp chập 9 của 3 phần tử ; trong đó cam lặp 2 lần, quýt lặp 3 lần, chanh lặp 4 lần. Ta ký hiệu số tổ hợp lặp chập k của n phần tử là R kn và tìm công thức cho R kn . Ta gán cho mỗi phần tử trong n phần tử đã cho một số nguyên dương khác nhau từ 1 đến n. Khi đó mỗi tổ hợp chập k không lặp của n phần tử tương ứng với 1 dãy số tăng a 1a 2...a k trong đó:

1 £ a 1 < a 2 < ... < a k £ n, (k £ n) Và mỗi tổ hợp lặp chập k của n phần tử tương ứng với 1 dãy số không giảm a 1a 2...a k trong đó 1 £ a1 £ a 2 £ ... £ a k £ n và không nhất thiết k £ n . Ta thiết lập sự tương ứng giữa dãy a 1a 2...a k với dãy b1b 2...b k như sau: 40

TOÁN RỜI RẠC – Lý thuyết

b1 = a1 b2 = a 2 + 1 b3 = a 3 + 2 ………….. b k = a k + (k - 1) Khi đó ta có 1 £ b1 < b 2 < ... < b k £ n + k - 1 Mỗi dãy b1b 2...b k như vậy tương ứng với một tổ hợp (không lặp) chập k của ( n + k - 1 ) phần tử. Vậy R kn £ C nk + k - 1 Ngược lại với mỗi tổ hợp không lặp chập k của (n + k - 1 ) phần tử (tương ứng với 1 dãy tăng b1b 2...b k ...