1. Hoán vị
a) Định nghĩa: Cho tập hợp A có n(n⩾1)phần tử. Khi sắp xếp n phần tử này theo một thứ tự, ta được một hoán vị các phần tử của tập A (gọi tắt là một hoán vị của A)
b) Số các hoán vị
Định lí 1: Số các hoán vị của một tập hợp có n phần tử, kí hiệu Pn, là:
Pn=n!=n(n−1)(n−2)...1
Ví dụ: Một đoàn khách du lịch dự định tham quan bảy địa điểm A,B,C,D,E,G và H ở thủ đô Hà Nội. Họ đi thăm quan theo một thứ tự nào đó, chẳng hạn B→A→C→E→D→G→H. Như vậy, mỗi cách chọn thứ tự các địa điểm tham quan trên là một hoán vị của tập {A,B,C,D,E,G,H}. Thành thử, đoàn khách có tất cả 7!=5040 cách chọn.
2, Chỉnh hợp
a) Định nghĩa:
Cho tập hợp A gồm n phần tử và số nguyên k với 1⩽k⩽n. Khi lấy ra kphần tử của A và sắp xếp chúng theo một thứ tự, ta được một chỉnh hợp chập k của n phần tử của A (gọi tắt là một chỉnh hợp chập k của A)
Nhận xét: Hai chỉnh hợp khác nhau khi và chi khi có một phần tử của chỉnh hợp này mà không phải của chỉnh hợp kia, hoặc phần tử của hai 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
Định lí 2:
Số các chỉnh hợp chập k của một tập hợp có n phần tử, kí hiệu Akn (1⩽k⩽n) là: Akn=n(n−1)(n−2)...(n−k+1).
Nhận xét: Ann=Pn=n!
Ví dụ: Trong mặt phẳng cho một tập hợp gồm 6 điểm phân biệt. Có bao nhiêu vecto khác vecto →0 có điểm đầu và điểm cuối thuộc tập hợp điểm này?
Giải: Mỗi cặp sắp xếp thứ tự gồm hai điểm (A,B) cho ta một vecto có điểm đầu A, điểm cuối B và ngược lại. Như vậy, mỗi vecto có thể xem là một chỉnh hợp chập 2 của tập hợp 6 điểm đã cho. Thành thử số vecto cần tìm là
A26=6.5=30
Chú ý: Với 0<k<nthì ta có thể viết công thức (1) dưới dạng
Akn=n!(n−k)! (2)
Ta quy ước 0!=1 và A0n=1
Khi đó công thức (2) đúng cho cả k=0 và k=n. Vậy công thức (2) đúng với mọi số nguyên k thỏa mãn 0⩽k⩽n.
3, Tổ hợp
a) ĐN:
Cho tập A có n phần tử và số nguyên k với 1⩽k⩽n. Mỗi tập con của A có kphần tử được gọi là một tổ hợp chập k của n phần tử của A (gọi tắt là một tổ hợp chập k của A)
Như vậy lập một tổ hợp chập kcủa A chính là lấy ra kphần tử của A (không quan tâm đến thứ tự)
b) Số các tổ hợp:
Kí hiệu Ckn( hoặc (nk)) là số các tổ hợp chập k của một tập hợp có nphần tử.
Định lí 3:
Số các tổ hợp chập k của một tập hợp có n phần tử (1⩽k⩽n) là
Ckn=Aknk!=n(n−1)(n−2)...(n−k+1)k! (3)
Ví dụ 6: Trong mặt phẳng cho một tập hợp P gồm 7 điểm, trong đó không có 3 điểm nào thẳng hàng. Hỏi có bao nhiêu tam giác có 3 đỉnh đều thuộc P?
Giải:
Với mỗi tập con gồm 3 điểm bất kỳ của P, tạo ra được một tam giác với các đỉnh là 3 điểm đó. Ngược lại, mỗi tam giác có 3 đỉnh thuộc P tương ứng với một tập con gồm 3 điểm của P. Vậy số tam giác có 3 đỉnh thuộc P chính bằng số các tổ hợp chập 3 của tập P, tức là bằng
C37=7.6.53!=35
4, Hai tính chất cơ bản của số Ckn
a) Tính chất 1:
Cho số nguyên dương nvà số nguyên k với 0⩽k⩽n. Khi đó
Ckn=Cn−kn
b) Tính chất 2 (hằng đẳng thức Pa-xcan)
Cho các số nguyên n và k với 1⩽k⩽n. Khi đó
Ckn+1=Ckn+Ck−1n
|