ĐẠi học quốc gia hà NỘI
tải về 0.86 Mb.
|
- Điều hướng trang này:
- 1.4 Chỉnh hợp, tổ hợp
- 1.5 Chỉnh hợp lặp, hoán vị lặp và tổ hợp lặp
- 1.5.2 Hoán vị lặp
- 1.5.3 Tổ hợp lặp
1.3 Giai thừa và hoán vịGiai thừa Định nghĩa: Giai thừa , kí hiệu là ! là tích của số tự nhiên liên tiếp từ 1 đến . , , >1. Quy ước : 0!= 1. 1!= 1.
Cho tập hợp , gồm phần tử . Một cách sắp thứ tự phần tử của tập hợp được gọi là một hoán vị của phần tử đó. Kí hiệu: là số các hoán vị của n phần tử.
Chỉnh hợp Định nghĩa Cho tập hợp gồm phần tử . Kết quả của việc lấy phần tử khác nhau từ phần tử của tập hợp và sắp xếp chúng theo một thứ tự nào đó được gọi là một chỉnh hợp chập của phần tử đă cho. Kí hiệu: là số các chỉnh hợp chập của phần tử. Công thức: = = (với 1 ). Chú ư Một chỉnh hợp chập được gọi là một hoán vị của phần tử. . Tổ hợp Định nghĩa Giả sử tập có phần tử ( 1). Mỗi tập con gồm phần tử của được gọi là một tổ hợp chập của phần tử đă cho (1 ). Kí hiệu: (1 ) là số các tổ hợp chập của phần tử. Công thức: = Chú ư = 1. (0 n). + = ( ).
Định nghĩa (Phương pháp giải toán tổ hợp) Một cách sắp xếp có thứ tự r 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 r 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 Ar. Ngoài ra, mỗi chỉnh hợp lặp chập r từ tập n phần tử là một hàm từ tập r phần tử vào tập n phần tử. V́ vậy số chỉnh hợp lặp chập r từ tập n phần tử là nk. Định lư 1.5.1 Số các chỉnh hợp lặp chập r từ tập n phần tử bằng Chứng minh Rơ ràng có n cách chọn một phần tử từ tập n phần tử cho mỗi một trong r vị trí của chỉnh hợp khi cho phép lặp. V́ vậy theo quy tắc nhân, có chỉnh hợp lặp chập r từ tập n phần tử. Chú ư. Số các chỉnh hợp lặp chập của phần tử là . Như vậy chỉnh hợp có lặp lại là khi giữa các phần tử yếu tố thứ tự là cốt lơi, c̣n yếu tố khác biệt không quan trọng.
Trong bài toán đếm, một số phần tử có thể giống nhau. Khi đó cần phải cẩn thận, tránh đếm chúng hơn một lần. Định lư 1.5.2 Số hoán vị của n phần tử trong đó có n1 phần tử như nhau thuộc loại 1, có n2 phần tử như nhau thuộc loại 2, … và có nk phần tử như nhau thuộc loại k bằng . Chứng minh Để xác định số hoán vị trước tiên chúng ta nhận thấy có cách giữ n1 số cho n1 phần tử loại 1, c̣n lại n – n1 chỗ trống. Sau đó có cách đặt n2 phần tử loại 2 vào hoán vị, c̣n lại n – n1 – n2 chỗ trống. Tiếp tục đặt các phần tử loại 3, loại 4 , … , loại k – 1 vào chỗ trống trong hoán vị. Cuối cùng có cách đặt nk phần tử loại k vào hoán vị. Theo quy tắc nhân tất cả các hoán vị có thể là:
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. Định lư 1.5.3 Số tổ hợp lặp chập k từ tập n phần tử bằng . 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 n1 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. Mỗi dăy n 1 thanh và k ngôi sao ứng với một tổ hợp lặp chập k của n phần tử . Do đó mỗi dăy ứng với một cách chọn k chỗ cho k ngôi sao từ chỗ chứa n – 1 thanh và k ngôi sao. Đó là điều cần chứng minh.
Số tổ hợp có lặp chập của là = = . Tổ hợp có lặp lại khi một phần tử có thể xuất hiện nhiều lần và thứ tự của các phần tử không cần để ư.
|