Tìm hiểu và ứng dụng toán học tổ hợp qua bài toán Hoán vị - Tổ hợp - Chỉnh hợp

Tìm hiểu và ứng dụng Toán học tổ hợp
Qua bài toán HOÁN VỊ - TỔ HỢP - CHỈNH HỢP
 Giới thiêu : Toán học tổ hợp (hay giải tích tổ hợp, đại số tổ hợp, lý thuyết tổ hợp) là một ngành toán học rời rạc, nghiên cứu về các cấu hình kết hợp các phần tử của một tập hữu hạn phần tử. Các cấu hình đó là các hoán vị, chỉnh hợp, tổ hợp,... các phần tử của một tập hợp.
Môn toán này có liên quan đến nhiều lĩnh vực khác của toán học, như đại số, lý thuyết xác suất, lý thuyết ergod (ergodic theory) và hình học, cũng như đến các ngành ứng dụng như khoa học máy tính và vật lí thống kê....nên có nhều vấn đề rất sâu phải có trình độ cao.
 Tuy nhiên, với trình độ phổ thông cơ sở vẫn có thể tiếp cận và ứng dụng giải nhiều bài toán rất hay gặp trong thực tế cũng như các đề thi ( Thi HSG, thi tuyển sinh..). Dưới đây giới thiệu vài khái niệm và bài toán ứng dụng
1. Hoán Vị:
a. Khái niệm
*Từ ví dụ: Có 3 học sinh An (a), Bình (b)và Chính (c) ngồi cùng bàn học. Nếu mỗi tuần một lần thay đổi vị trí ngồi giữa 3 người thì sau bao nhiêu tuần họ lại vế vị trí ban đầu? .
Giải : Gọi Vị trí ngồi ban đầu là A o = (a,b,c) “ b ngồi giữa ; a bên phải; c bên trái ”. Các tuần tiếp theo các thay đổi có thể là
 A 1 = (a,c,b) ; A 2 = (b,a,c) ; A 3 = (b,c,a), A 4 = (c,a,b), A 5 = (c,b,a).
Vậy sau 5 tuần họ lại vế vị trí ban đầu (ĐS).
*Nhận xét : cách giải trên là cách liệt kê; muốn khẳng định kết quả, ta phải chứng minh rằng không còn cách sắp xếp nào khác. Tuy nhiên nếu với số cho lớn thì các liệt kê không ổn, dễ bỏ sót.
* Cách suy luận: Mỗi người nếu ngồi đầu bàn thì chỉ có 2 cách thay đổi vị tri, vậy có 3 người thì sẽ có 2 x 3 = 6 cách thay đổi vị trị. Đầu bài trên hỏi sau mấy tuần quay về vị trí ban đầu thi kết qurả phải là 6 – 1 = 5 (tuần)
*liên hệ với lý thuyết hoán vị
Nếu mỗi lần “thay đổi vị trí” là một Hoán vị của tập hợp {a;b;c}. A = {a,b,c}
 thì tập hợp này có tất cả 6 Hoán vị 
Tổng quát ta có:
Cho tập hợp có phần tử (). Mỗi thay đổi vị trí sắp xếp phần tử này theo một thứ tự nhất định, ta được một Hoán vị các phần tử của tập .
b. Số các Hoán vị:
Định lí : Số các Hoán vị của một tập hợp có phần tử là:
Bài toán minh họa : 
 Một đoàn khách du lịch dự định đến tham quan điểm du lịch và ở Hà Nội. Họ đi tham quan theo thứ tự nào đó, chẳng hạn 
. Như vậy mỗi cách họ chọn thứ tự tham quan là một Hoán vị của tập . Do vậy đoàn khách có tất cả cách chọn.
( Như bài này rõ ràng cách liệt kê thô sơ khõ lòng giải quyết được )
2. Chỉnh hợp:
a. Khái niệm về chỉnh hợp
*Từ ví dụ :
 Trong trận chung kết bóng đá phải phân định thắng thua bằng đá luân lưu . Huấn luyện viên của mỗi đội cần trình với trọng tài một danh sách sắp thứ tự cầu thủ trong số cầu thủ của đội để tham gia đá. Hỏi mỗi đội bóng có bao nhiêu phương án chọn ?
Giải: Ta có thể chọn trong cầu thủ để đá quả đầu tiên. Tiếp theo có cách chọn cầu thủ đá quả thứ hai, rồi cách chọn cầu thủ đá quả thứ ba, cách chọn cầu thủ đá quả thứ tư và cuối cùng có cách chọn cầu thủ đá quả thứ năm. Theo quy tắc nhân, mỗi đội sẽ có: cách chọn.
Mỗi danh sách có xếp thứ tự cầu thủ được gọi là một chỉnh hợp chập của cầu thủ
*Tổng quát:
Cho tập gồm phần tử và số nguyên , . Mỗi lần lấy ra phần tử của và sắp xếp chúng theo một thứ tự ta được một Chỉnh hợp chập của phần tử thuộc .
*Nhận xét: 
Hai Chỉnh hợp khác nhau khi và chỉ khi hoặc có ít nhất một phần tử của Chỉnh hợp này không là phần tử của Chỉnh hợp kia hoặc các phần tử của Chỉnh hợp giống nhau nhưng được sắp xếp theo thứ tự khác nhau.
b. Số các Chỉnh hợp:
Trong ví dụ trên, tính số phương án huấn luyện viên lập danh sách cầu thủ là 
 (cách chọn.)
Định lí:
Số các Chỉnh hợp chập của một tập hợp có phần tử ( ) là:
với quy ước 
Ta quy ước: , do đó công thức đúng với mọi số nguyên thỏa mãn 
Chú ý: Một Hoán vị của một tập phần tử chính là một Chỉnh hợp chập của phần tử đó . 
Do đó 
: 
3. Tổ hợp:
* Khái niệm:Cho tập A có n phần tử và số nguyên với . Mỗi tập con của có phần tử gọi là một Tổ hợp chập của phần tử của ( gọi tắt là Tổ hợp chập của )
Như vậy, lập một Tổ hợp chập của chính là lấy ra phần tử của mà không quan tâm đến thứ tự. 
* Số các Tổ hợp:
Định lí: Số các Tổ hợp chập của một tập hợp có phần tử ( ) là:
Với quy ước: thì cũng sẽ đúng với mọi số nguyên thỏa mãn 
 *Bài toán mẫu: 
 Trong lớp học có học sinh nam và học sinh nữ. Mỗi tuần Thầy giáo cần học sinh nam và học sinh nữ đi tham gia 1 sinh hoạt ngoại khóa của trường. 
 Hỏi có bao nhiêu cách?
Giải: 
Ta có:
cách chọn học sinh nam trong số học sinh nam 
và có
cách chọn HS nữ trong số HS nữ. 
Theo quy tắc nhân, số cách chọn cần tìm là: 
 (cách chọn)
4. Hai tính chất cơ bản của :
Tính chất 1: Cho các số nguyên thỏa mãn .
Khi đó:
Tính chất 2: Cho các số nguyên thỏa mãn .
Khi đó:
5. Bài toán thực hành
 Bài 1: Có bao nhiêu cách xếp chỗ ngồi cho 10 bạn vào ngồi quanh 2 bàn tròn sao cho bàn thứ nhất có 6 bạn, bàn thứ hai có 4 bạn? Chú ý rằng 2 cách xếp n người cụ thể vào ngồi quanh một bàn tròn được coi là như nhau nếu người ngồi bên trái mỗi người trong 2 cách xếp là giống nhau.
Huớng giải
Chia là ba bước.
Bước 1: chọn nhóm người (hoặc 4 người). Có cách.
Bước 2: Xếp người vào bàn tròn vị trí. cách.
Bước 3: Xếp người vào bàn tròn có vị trí. cách.
Áp dụng quy tắc nhân, tính kết quả.
 Bài 2 : Một người dùng ổ khóa số gồm 3 vòng số, mỗi vòng có 10 chữ số từ 0 đên 9. Hỏi người đó có bao nhiêu cách đặt mật mã ( số để khóa chỉ người đó biết ) cho ổ khóa ?