Chương 1 Tập hợp và tổ hợp 1. Tập hợp và khả năng 1. Tập hợp Tập hợp (còn gọi là tập) là một khái niệm cơ bản của toán học, không định nghĩa. Giả sử đã cho tập hợp A.
Để chỉ a là một phần tử của tập hợp A, ta viết a ∈ A (đọc là a thuộc A). Để chỉ a không phải là một phần tử của tập hợp A, ta viết a ∈ / A (đọc là a không thuộc A). Tập những học sinh giới tính nam trong một lớp, tập học sinh có nhà cách trường trên 30km,. Các phần tử của một tập hợp có thể chỉ ra được bằng một trong hai cách sau: • Liệt kê các phần tử của chúng.
Ví dụ: A là tập hợp các ước nguyên dương của 30, Ta viết A = {1, 2, 3, 5, 6, 10, 15, 30}. • Chỉ ra tính chất đặc trưng cho các phần tử. 6 Ví dụ: B là tập hợp các nghiệm của phương trình : 2x2 − 5x + 3 = 0, ta viết là : B = x ∈ R/2x2 − 5x + 3 = 0. Một số tập hợp toán học: Tập các số thực, được ký hiệu R ; Tập các số hữu tỷ, được ký hiệu Q ; Tập các số nguyên, được ký hiệu Z ; Tập các số nguyên không âm, được ký hiệu Z+ ; Tập các số tự nhiên ký hiệu N ; Tập rỗng, tập không có phần tử nào, được ký hiệu ∅.
Tập B mà mỗi phần tử của nó đều thuộc tập A, thì B được gọi là tập con của tập A và viết B ⊆ A. Tập B mà mỗi phần tử của nó đều thuộc tập A và B 6= A, thì A được gọi là tập con thực sự của tập A và viết B ⊂ A. Khi A ⊂ B và B ⊂ A ta nói tập hợp A bằng tập hợp B và viết là A = B. Số các phần tử của tập hợp A được gọi là lực lượng của tập A, được ký hiệu bởi |A| hay n(A).
n - tập là ký hiệu tập có n phần tử. Xâu Trong nhiều bài toán tổ hợp, thứ tự các phần tử đóng vai trò rất quan trọng (ví dụ thứ tự các trận đấu, thứ tự sắp xếp học lực của học sinh trong một lớp, thứ tự lắp ráp linh kiện cho một cỗ máy. ), trong khi đó trong tập hợp thứ tự giữa các phần tử không giữ vai trò gì. Do vậy phải đưa một khái niệm “xâu” để giải quyết các bài toán nêu trên.
Cho tập X bất kỳ và tập gồm các số tự nhiên Nn = {1, 2, 3,. Cho ánh xạ từ tập Nn vào tập X tương ứng số 1 với phần tử x1 ∈ X, số 2 với phần tử x2 ∈ X,. , số n với phần tử xn ∈ X. Kết quả ta nhận được bộ x1 , x2 ,.
, xn các phần tử của tập hợp X, trong đó mỗi số phần tử có thể xuất hiện nhiều lần. Khi sắp xếp các phần tử của bộ trên theo thứ tự, ta nhận được xâu (x1 , x2 , ., xn ) độ dài n, lập nên từ những phần tử của tập X. Phần tử xk , 1 ≤ k ≤ n được gọi là thành phần thứ k hoặc là tọa độ thứ k của xâu (x1 ,. 7 Các xâu có độ dài 2 được gọi là các cặp, còn xâu có độ dài 3 là bộ ba.
Đôi khi các xâu độ dài n được gọi là n-bộ. , yn ) được xem là bằng nhau nếu chúng có độ dài như nhau, đồng thời các thành phần của chúng có cùng số thứ thự thì bằng nhau. Ta kí hiệu bằng các xâu bằng chữ cái Hy Lạp. Như vậy, nếu α = (x1 , x2 ,.
, ym ) thì α = β khi và chỉ khi n = m và xk = yk với mọi k, 1 ≤ k ≤ n. √ √ √ √ √ √ Ví dụ: Cho α = 2, 3, 2 và β = 4 4, 4 9, 4 16 , thì α = β vì 4 4 = √ 4 2 1 √ √ √ 4 2 1 √ √ √4 22 = 2 4 = 2 2 = 2, 4 3 = 32 = 3 4 = 3 2 = 3, 4 16 = 24 = 2. Các xâu (a, b, c, d) và (a, b, c) không bằng nhau vì có độ dài khác nhau. Các xâu (a, b, c) và (c, a, b) không bằng nhau vì thứ tự các thành phần khác nhau.
Các thành phần của xâu có thể là những tập hợp, những xâu,. Xâu (a, b, {c, d}) và xâu (a, b, {d, c}) bằng nhau vì các tập hợp {c, d} và {d, c} bằng nhau. Xâu không chứa phần tử nào được gọi là xâu rỗng, ký hiệu bởi ( ). Tập hợp sắp thứ tự Định nghĩa 1.
Một tập hợp được gọi là sắp thứ tự, nếu các phần tử của nó được sắp xếp theo một thứ tự xác định. Sắp thứ tự tập các em học sinh trong lớp theo vần chữ cái của tên, theo điểm trung bình môn. Các phép toán trên tập hợp 1. Giao của hai tập hợp Định nghĩa 1.
Giao của hai tập hợp là tập hợp gồm các phần tử thuộc cả hai tập hợp đó. Giao của A và B ký hiệu là A ∩ B. Theo định nghĩa, ta có A ∩ B = {x|x ∈ B và x ∈ A}. Hợp của hai tập hợp Định nghĩa 1.
Hợp của hai tập hợp là tập hợp gồm các phần tử thuộc ít nhất một trong hai tập hợp đó. Hợp của hai tập hợp A và B được ký hiệu là A ∪ B. Theo định nghĩa, ta có A ∪ B = {x|x ∈ B hoặc x ∈ A}. Hiệu và phần bù của hai tập hợp Định nghĩa 1.
Hiệu của hai tập hợp A và B là các phần tử thuộc A nhưng không thuộc B. Hiệu của hai tập hợp A và B ký hiệu bởi A \ B. Theo định nghĩa, ta có A \ B = {x|x ∈ A và x ∈ / B}. Nếu B ⊂ A thì A \ B là phần bù của B trong tập A.
Tích Đềcác của n tập hợp Định nghĩa 1. Cho các tập hợp X1 , X2 , ., Xn và xét những bộ α = (x1 , x2 , ., xn ), trong đó xi ∈ Xi với i = 1, k. Tập hợp lập nên từ những xâu như vậy được gọi là tích Đềcác của các tập hợp X1 ,. Ta ký hiệu tích Đềcác này là X1 × X2 ×.
Ví dụ nếu X1 = {1, 2, 3} và X2 = {a, b} thì tích X1 × X2 lập nên từ 6 cặp: (1, a), (1, b), (2, a), (2, b), (3, a) và (3, b). Tích X2 × X1 cũng lập nên từ 6 cặp nhưng thành phần của chúng có thứ tự khác: (a, 1), (a, 2), (b, 1), (b, 2), (c, 1) và (c, 2). Ví dụ với A = {0, 1} và B = {a, b, c} thì A × B = {(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)}. Số các tập con Định lý 1.
Một tập có n phần tử có 2n tập con. Trước hết ta chứng minh rằng số các ánh xạ từ k - tập X và m - tập Y bằng mk. Chẳng hạn, nếu k = 3, m = 2 thì ta có 23 = 8 ánh xạ. Còn nếu k = 2, m = 3 thì ta có 32 = 9 ánh xạ.
Nếu xem các phần tử của tập hợp X là các “vật”, còn các phần tử của tập hợp Y là các “thùng”, thì mỗi khi có ánh xạ ϕ tập hợp X vào tập hợp Y , diễn ra việc sắp xếp các đồ vật vào các thùng (đồng thời một số thùng có thể rỗng, vì có thể xảy ra trường hợp phần tử y ∈ Y không được phần tử nào ánh xạ vào). Vì số các ánh xạ từ k - tập X vào m - tập Y bằng mk nên số các cách sắp xếp k vật khác nhau vào m thùng khác nhau (một số thùng có thể rỗng) cũng bằng mk. Áp dụng tính số tập con của một tập có n phần tử. Thật vậy, lấy hai số 0 và 1.
Mỗi tập con A của tập hợp X tương ứng với mỗi ánh xạ ϕ tập hợp X vào tập hợp {0, 1}, trong đó các phần tử của A được ánh xạ vào 1, các phần tử còn lại ánh xạ vào 0. Như vậy tồn tại tương ứng một một giữa các tập con của tập hợp X và các ánh xạ của tập hợp này vào tập gồm hai phần tử {0, 1}. Mà các ánh xạ như vậy bằng 2n , trong đó n là số phần tử của tập hợp X. Điều đó có nghĩa số tập con của tập X có n phần tử là 2n.
Ví dụ tập X = {a, b, c} có 23 = 8 tập con. Đó là các tập ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c} và {a, b, c}. Bây giờ chúng ta quay trở lại việc chứng minh rằng tập có n phần tử có 2n tập con. Sử dụng phương pháp quy nạp toán học, ta có khi n = 1, khẳng định đúng vì 21 = 2, mà tập {a} có hai tập con là {a} và ∅.
Giả sử khẳng định đúng với n = k, tức là số tập con của k - tập X là 2k. Thêm vào X phần tử xk+1 , ta nhận được tập Y = {x1 , x2 ,. Một tập hợp con tùy ý của tập hợp Y hoặc không chứa phần tử mới xk+1 , hoặc chứa nó. Trường hợp thứ nhất, nó là một tập hợp con của k - tập X.
Số các tập con như vậy bằng 2k. Trong trường hợp thứ hai, nếu loại phần tử xk+1 , ta lại nhận được một tập hợp con của X. Như vậy, số các tập hợp con loại thứ hai đúng bằng số tập hợp con loại thứ nhất và bằng 2k. Khi đó, tổng số các tập hợp con của Y là 2k + 2k = 2k+1.
Như vậy ta đã chứng minh khẳng định đúng với n = 1 và nếu khẳng định 10 đúng với n = k thì khẳng định đúng với n = k + 1. Nghĩa là khẳng định đúng với mọi giá trị của n. Quy tắc tổng Ví dụ 1. Trên đĩa có 8 quả đào và 7 quả mận thì sẽ có 8 + 7 cách chọn một quả trên đĩa.
Quy tắc tổng: Nếu một công việc có thể thực hiện theo n phương án khác nhau, trong đó phương án thứ i có mi cách thực hiện, với i = 1, n. Khi đó, ta có m1 + m2 + · · · + mn cách thực hiện công việc đã cho.