Chỉnh Hợp Và Tổ Hợp - VOER

C H Ỉ N H HỢP VÀ T Ổ HỢP.

C h ỉnh h ợ p

Ð ịnh n g h ĩa

Cho X là một tập hợp gồm n phần tử, và r là một số nguyên dương nhỏ hơn hoặc

bằng n. Mỗi phép chọn r phần tử phân biệt của X theo một thứ tự nào đó sẽ cho ta

một chỉnh hợp n chọn r. Nói cách khác, ta có thể xem một chỉnh hợp như là một dãy hay một bộ gồm r phần tử phân biệt được chọn từ n phần tử cho trước.

Ví dụ 1. Cho tập hợp

Dãy gồm 2 phần tử 3, 2 là một chỉnh hợp 3 chọn 2. Sự sắp xếp các phần tử thành dãy 3, 1, 2 cho ta một chỉnh hợp 3 chọn 3. Chỉnh hợp 3 chọn 3 nầy còn được gọi là một hoán vị của 3 phần tử.

Một chỉnh hợp n chọn n được gọi là một hoán vị của n phần tử. Nói cách khác, một hoán vị n phần tử là một cách sắp xếp n phần tử theo một thứ tự nào đó. Mỗi hoán vị n phần tử của tập X cũng có thể được xem như một song ánh từ X vào X.

C ô n g t h ứ c c h ỉ nh h ợ p

Ðịnh lý I.1. Số các chỉnh hợp n chọn r là

A(n,r) = n(n-1)(n-2)...(n-r+1).

Chứng minh: Mỗi chỉnh hợp của n phần tử chọn r tương ứng với một phép chọn ra r phần tử phân biệt gồm r bước chọn liên tiếp nhau, và ở mỗi bước ta chọn một phần tử. Phần tử thứ nhất của chỉnh hợp có thể được chọn theo n cách vì có n phần tử trong tập hợp. Ðối vớ phần tử thứ 2 ta chỉ có n-1 cách chọn (vì ở lần thứ 2 ta phải loại ra phần tử đã chọn ở lần thứ nhất trong việc chọn). Cứ tiếp tục như thế, đến phần tử thứ r ta có n-r+1 cách chọn. Do đó, theo nguyên lý nhân, ta có số chỉnh hợp

n chọn r là

Ghi chú:

n(n-1)(n-2)...(n-r+1).

Ðặt biệt ta có A(n,n) = n!, tức là số hoán vị của n phần tử bằng n!.

Ví dụ 2. Số trường hợp lấy 4 người của một lớp gồm 10 người vào 4 vị trí (có thứ

tự) đại diện cho lớp là A(10,4) = 10.9.8.7 = 5 040.

Chỉnh hợp có lặp.

Một cách sắp xếp có thứ tự k phần tử có thể lặp lại của một tập n phần tử được gọi là một chỉnh hợp lặp chập k từ tập n phần tử. Nếu A là tập gồm n phần tử đó thì mỗi chỉnh hợp như thế là một phần tử của tập Ak. Ngoài ra, mỗi chỉnh hợp lặp chập k từ tập n phần tử là một hàm từ tập k phần tử vào tập n phần tử. Vì vậy số chỉnh hợp lặp chập k từ tập n phần tử là nk.

T ổ h ợ p

Ð ịnh n g h ĩa

Cho X là một tập hợp gồm n phần tử, và r là một số nguyên không âm nhỏ hơn hoặc bằng n. Mỗi phép chọn r phần tử phân biệt của X mà không phân biệt thứ tự trước sau sẽ cho ta một tổ hợp n chọn r. Nói cách khác, ta có thể xem một tổ hợp n chọn r như là một tập hợp con gồm r phần tử của một tập hợp có n phần tử.

Ví dụ 3. Cho tập hợp

là một tổ hợp 4

chọn 3.

Số các tổ hợp n chọn r được ký hiệu là C(n,r). Ví dụ : C(4,2) = 6 vì ta có thể liệt kê ra tất cả các tập hợp con 2 phần tử của một tập hợp có 4 phần tử và thấy có tất cả là

6 tập con. Ðịnh lý sau đây cho ta một công thức để tính C(n,r).

C ô n g t h ứ c tổ h ợ p

Ðịnh lý II.1. Số các tổ hợp n chọn r , với n và r là các số nguyên thỏa 0 ≤ r ≤ n, là

Chứng minh: Ta sẽ tính số tổ hợp thông qua việc thiết lập công thức li ên hệ giữa C(n,r) và A(n,r). Các chỉnh hợp n chọn r thể đạt được bằng cách lấy một tổ hợp n chọn r (hay tập con r phần tử của tập hợp n phần tử cho trước) rồi sau đó chọn một hoán vị của r phần tử trong tổ hợp. Từ đó, theo qui tắc nhân, ta có:

A(n,r) = C(n,r) . A(r,r) = C(n,r) . r!

Suy ra :

Ví dụ 4. Số danh sách không kể thứ tự trước sau gồm 5 người của một lớp học gồm

10 người là C(10,5) = 10! / (5!5!) = 252.

C ô n g t h ứ c n h ị t h ứ c N e w to n :

Ðịnh lý II.2. Cho x và y là 2 biến thực, n là một số nguyên không ấm tùy ý. Ta có:

Chứng minh: Ta có thể khai triển tích của n thừa số trong biểu thức

(x+y)n = (x+y) (x+y) . . . (x+y)

thành tổng của 2n số hạng có dạng t1t2…tn trong đó ti = x hay ti = y, với mọi i từ 1

t

bằng y, và như thế các số hạng nầy bằng xn-jyj. Số các số hạng nầy chính là số cách

ch

trong số hạng t1t2…tn sẽ được chọn bằng y. Ðó chính là số tổ hợp n chọn j. Từ đó

ta suy ra công thức cần chứng minh.

Một cách khác, ta có thể dựa vào tam giác Pascal:

Hệ quả 1. Cho n là một số nguyên không âm tùy ý. Ta có:

Hệ quả 2. Cho n là một số nguyên không âm. Ta có:

M ột s ố t í n h c h ất k h ác c ủ a tổ h ợ p

Dưới đây ta nêu lên một số tính chất của tổ hợp. Các tính chất nầy có thể được

chứng minh dễ dàng từ công thức tổ hợp.

C(n, n) = 1

C(n, k) = C(n-1, k) + C(n-1, k-1).

hoặc bằng m và n. Ta có:

Tổ hợp lặp.

Một tổ hợp lặp chập k của một tập hợp là một cách chọn không có thứ tự k phần tử có thể lặp lại của tập đã cho. Như vậy một tổ hợp lặp kiểu này là một dãy không kể thứ tự gồm k thành phần lấy từ tập n phần tử. Do đó có thể là k > n.

kMệnh đề 1: Số tổ hợp lặp chập k từ tập n phần tử bằng Cnk－1 .

Chứng minh. Mỗi tổ hợp lặp chập k từ tập n phần tử có thể biểu diễn bằng một dãy n－1 thanh đứng và k ngôi sao. Ta dùng n － 1 thanh đứng để phân cách các ngăn. Ngăn thứ i chứa thêm một ngôi sao mỗi lần khi phần tử thứ i của tập xuất hiện trong tổ hợp. Chẳng hạn, tổ hợp lặp chập 6 của 4 phần tử được biểu thị bởi:

* * | * | | * * *

mô tả tổ hợp chứa đúng 2 phần tử thứ nhất, 1 phần tử thứ hai, không có phần tử thứ

3 và 3 phần tử thứ tư của tập hợp.

Mỗi dãy n － 1 thanh và k ngôi sao ứng với một xâu nhị phân độ dài n + k － 1 với k số 1. Do đó số các dãy n － 1 thanh đứng và k ngôi sao chính là số tổ hợp chập k từ tập n + k － 1 phần tử. Đó là điều cần chứng minh.

Thi dụ 8: 1) Có bao nhiêu cách chọn 5 tờ giấy bạc từ một két đựng tiền gồm những

tờ 1000đ, 2000đ, 5000đ, 10.000đ, 20.000đ, 50.000đ, 100.000đ. Giả sử thứ tự mà các tờ tiền được chọn là không quan trọng, các tờ tiền cùng loại là không phân biệt và mỗi loại có ít nhất 5 tờ.

Vì ta không kể tới thứ tự chọn tờ tiền và vì ta chọn đúng 5 lần, mỗi lần lấy

một từ 1 trong 7 loại tiền nên mỗi cách chọn 5 tờ giấy bạc này chính là một tổ hợp

5lặp chập 5 từ 7 phần tử. Do đó số cần tìm là C75－1 = 462.

2) Phương trình x1 + x2 + x3 = 15 có bao nhiêu nghiệm nguyên không âm?

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 15 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 và x3 phần tử loại 3 được chọn. Vì vậy số nghiệm bằng số tổ hợp lặp chập 15 từ tập có 3 phần tử và =

= 136