Bà i giảng tổ hợp 2: Các đối tượng tổ hợp cơ bản.

[namdung]

Nếu một tập hợp không có cấu trúc gì cả thì chẳng có cách nào đếm được số phần tử của nó ngoài cách đếm liệt kê. Vì vậy ta sẽ quan tâm đến những tập hợp có cấu trúc, tức là được tập hợp được xây dựng từ các tập hợp cơ bản (đã biết rõ số phần tử) thông qua các phép toán, các phép xây dựng.
Tôi cho rằng bạn đọc đã nắm rõ những khái niệm và phép toán cơ bản trên tập hợp: tập con, hợp, giao, hiệu, hiệu đối xứng của hai tập hợp, phần bù của một tập hợp trong một tập vũ trụ. Đặc biệt phép toán tích Đề-các sẽ rất quan trọng. Theo định nghĩa tích Đề-các của hai tập hợp A và B là tập hợp tất cả các bộ sắp thứ tự (a, b) với a thuộc A và b thuộc B. AxB=(a,b)|a∈A,b∈B. Chú ý rằng nếu A, B, C thuộc tập vũ trụ X thì các phép toán hợp, giao, hiệu của A, B, C không vượt ra khỏi X. Nhưng tích Đề-các thì khác. Tích Đề-các là một công cụ hữu hiệu để xây dựng các tập hợp mới to hơn, nhiều phần tử hơn.
Chú ý là các quy tắc đếm ở bài trước đều có thể phát biểu gọn gàng trên ngôn ngữ tập hợp.
Quy tắc cộng: Nếu A giao B bằng rỗng thì |A hợp B | = |A| + |B|
Quy tắc nhân: |A x B | = |A|.|B|
Quy tắc phần bù: Nếu A thuộc X thì |A| = |X| - |phần bù của A|.
Tiếp theo, ta sẽ giới thiệu các đối tượng tổ hợp cơ bản phát sinh từ một tập hợp hữu hạn X có n phần tử.
1. Tập tất cả các tập con của X, ký hiệu là P(X). Phần tử của P(X) là các tập con của X, trong đó có rỗng và chính X. Ví dụ với X = {1, 2, 3} thì P(X) gồm 8 phần tử sau: rỗng, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, X. Nói chung, nếu X có n phần tử thì P(X) có 2^n phần tử. Chính vì thế đôi khi người ta còn ký hiệu P(X) là 2^X. Còn ở đây chữ P là viết tắt của chữ power, P(X) trong tiếng Anh gọi là power set. P(X) và các tập con của nó là một đối tượng ta rất quan tâm.
2. Chỉnh hợp chập k từ n phần tử của X là một bộ sắp thứ tự k phần tử phân biệt lấy từ X. Ở đây sắp thứ tự có nghĩa là thứ tự quan trọng, ví dụ là (1, 2) sẽ khác (2, 1). Ví dụ với X = {1, 2, 3, 4, 5} và k = 2 thì các chỉnh hợp chập 2 của 5 phần tử của X gồm (1, 2), (2, 1), (1, 3), (3, 1), (1, 4), (4, 1), (1, 5), (5,1), (2, 3), (3, 2), (2, 4), (4, 2), (2, 5), (5, 2), (3, 4), (4, 3), (3, 5), (5, 3), (4, 5), (5, 4). Có tất cả 20 chỉnh hợp chập 2 của 5 phần tử như vậy. Ở đây ta đưa việc thiết lập 1 chỉnh hợp như thế thành 1 quy trình 2 công đoạn: chọn phần tử thứ nhất sau đó chọn phần tử thứ hai. Phần tử thứ nhất rõ ràng có 5 cách chọn, phần tử thứ hai chỉ có 4 (phải khác phần tử thứ nhất). Tổng quát hơn số chỉnh hợp chập k từ n phần tử, được ký kiệu là A(k,n) với lý luận tương tự, sẽ bằng n.(n-1)...(n-k+1). Nếu đặt n! = 1.2.3...n thì ta có thể rút gọn A(k,n) = n!/(n-k)!.
3. Hoán vị của n phần tử chính là chỉnh hợp chập n từ n phần tử đó. Nói cách khác là một cách xếp n phần tử theo một thứ tự nào đó. Số hoán vị của n phần tử được ký hiệu là P(n) và bằng n!.
4. Tổ hợp chập k từ n phần tử của X là một bộ không sắp thứ tự k phần tử phân biệt lấy từ X. Ở đây không sắp thứ tự có nghĩa là thứ tự không quan trọng, ví dụ là {1, 2} sẽ giống {2, 1}. Ví dụ với X = {1, 2, 3, 4, 5} và k = 2 thì các tổ hợp chập 2 của 5 phần tử của X gồm {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}. Có tất cả 10 tổ hợp chập 2 của 5 phần tử như vậy, ít hơn 1 nửa so với chỉnh hợp tương ứng. Với tổ hợp chập k của n phần tử, ta thấy rằng từ 1 tổ hợp chập k của n phần tử ta có thể phát sinh ra k! các chỉnh hợp chập k của n phần tử đó bằng cách hoán vị các phần tử trong tổ hợp này. Vì thế, số chỉnh hợp chập k của n phần tử sẽ gấp k! lần số tổ hợp chập k của n phần tử. Do đó nếu ký hiệu C(k,n) là số tổ hợp chập k của n phần tử thì ta có A(k,n) = k!C(k,n). Từ đây suy ra C(k,n) = n!/(k!*(n-k)!). Ta có thể coi một tổ hợp chập k từ n phần tử là một tập con k phần tử của tập đó. Như vậy C(k,n) chính là số tập con k phần tử của một tập hợp có n phần tử. Trong một tập hợp thứ tự là không quan trọng nên nếu chúng là các con số thì ta có thể sắp chúng theo thứ tự tăng dần. Không sắp thứ tự lại có thể sắp thứ tự. Đây giống như một nghịch lý và là bắt nguồn của nhiều sai lầm. Ta phải nắm vững chỗ này nhé.
5. Chỉnh hợp lặp chập k từ n phần tử của X là một bộ sắp thứ tự k phần tử không nhất thiết phân biệt lấy từ X. Ví dụ với X = {1, 2, 3} và k = 2 thì ta có 9 chỉnh hợp lặp chập 2 từ 3 phần tử này là (1, 1), (1, 2), (2, 1), (1, 3), (3, 1), (2, 2), (2, 3), (3, 2), (3, 3). Tổng quát hơn, dùng quy tắc nhân ta dễ dàng có được số chỉnh hợp lặp chập k của n phần tử bằng n^k.
Tạm thời hôm nay ta dừng lại ở đây. Còn hai đối tượng tổ hợp quan trọng nữa là hoán vị lặp và tổ hợp lặp ta sẽ đề cập đến trong bài sau. Tiếp theo, ta sẽ dùng các công cụ mới trang bị và các quy tắc đếm để giải một bài tập thú vị liên quan đến một trò chơi mà tôi rất thích: binh xập xám.
Luật chơi binh xập xám:
Mỗi người chơi sẽ được chia 13 lá bài, được chia thành 3 chi. Chi đầu và giữa gồm 5 lá bài. Chi cuối gồm 3 lá bài. Từ đây mới có cái tên xập xám. Xập xám tức là thập tam = 13.
Yêu cầu người chơi phải sắp xếp sao cho chi trước mạnh hơn chi sau.
Sức mạnh của bộ bài (chi) được căn cứ theo danh sách sau (mạnh đến yếu)
Thùng phá sảnh: gồm 1 dãy liên tiếp và đồng chất (chi 3 không có)
Tứ quý: gồm 4 lá bài cùng số (chi 3 không có)
Cù lũ: gồm 1 bộ ba và 1 đôi (chi 3 không có)
Thùng: gồm 1 dãy các lá bài đồng chất (chi 3 không có)
Sảnh: gồm 1 dãy liên tiếp và không đồng chất (chi 3 không có)
Sám cô: gồm 1 bộ ba
Thú: gồm 2 bộ đôi
Dách (hay Độn): gồm 1 bộ đôi
Mậu thầu: các lá bài không có kết hợp gì với nhau.
Bài toán 1. Rút ra ngẫu nhiên 5 lá bài từ bộ bài 52 quân. Tính xác suất để có
a) Thùng phá sảnh b) Tứ quý c) Cù lũ d) Thùng e) Sảnh f) Sám cô g) Thú h) Dách i) Mậu thầu.
Giải: Số cách rút ra 5 quân từ bộ bài 52 quân bằng C(5,52). Đó là không gian xác suất.
a) Một thùng phá sảnh được xác định hoàn toàn bởi chất của 5 quân bài và quân nhỏ nhất. Quân nhỏ nhất có thể là 1 (A), 2, 3, 4, 5, 6, 7, 8, 9, 10. Vì vậy có tất cả 4 (số chất) x 10 (số giá trị quân nhỏ nhất) = 40 TH thùng phá sảnh. Xác suất tương ứng là 40/C(5,52).
b) Tứ quý. Có 13 cách chọn giá trị quân bài sẽ gặp 4 lần. Ta lấy cả 4 quân bài tương ứng. Quân bài còn lại có 48 cách chọn. Xác suất tương ứng là 13x48/C(5,52).
c) Cù lũ: Bài tập.
d) Thùng: Có 4 cách chọn chất. Sau khi chọn chất, có C(5,13) cách chọn 5 quân của chất đó. Xác suất tương ứng là 4*C(5,13)/C(5,52).
e) Sảnh: Bài tập.
f) Sám cô: Có 13 cách chọn giá trị quân sám cô. Sau đó có C(3,4) cách chọn 3 quân bài từ 4 quân bài tương ứng. Hai quân còn lại chọn ra không được là đôi nên phải có 2 giá trị khác (thứ tự không quan trọng), có C(2,12) cách chọn. Với mỗi giá trị có 4 cách chọn quân (vì có 4 chất). Đáp số là 13*C(3,4)*C(2,12)*4*4/C(5,52).
g) Thú: Bài tập. Coi chừng là sai!
h) Dách: Bài tập
i) Mậu thầu: Ta tính xác suất của một bộ bài không có đôi. Chú ý còn phải tính đến các trường hợp không đôi nhưng là thùng, sảnh. Có C(5,13) cách chọn ra 5 giá trị khác nhau. Sau đó với mỗi giá trị có 4 cách chọn chất. Đáp số là C(5,13)*4^5/C(5,52). Xác suất mậu thầu thực tế sẽ nhỏ hơn con số nêu trên 1 chút.
Các bạn làm thử bài tập nêu trên nhé. Nếu bạn làm được mà không mắc sai sót gì thì bạn đã nắm khá vững vàng phép đếm đấy.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[hungchng]

Xin phép biên soạn lại bằng LaTeX
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]