Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 2: Phương pháp đếm

Chia sẻ: You You | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

77
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 2 trình bày về phương pháp đếm. Các nội dung chính được trình bày trong chương này gồm có: Khái niệm tập hợp, cách xác định một tập hợp, quan hệ "bao hàm trong" và tập hợp con, các phép toán tập hợp, ánh xạ, các nguyên lý đếm,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 2: Phương pháp đếm

Chương 2. Phương pháp đếm I. TẬP HỢP 1. KHÁI NIỆM TẬP HỢP Để chỉ một tập hợp ta dùng chữ in hoa, chẳng hạn như A, B, C,…., X,Y,Z. Để chỉ một phần tử ta dùng chữ thường, chẳng hạn như a, b, c,…., x,y,z. Để chỉ x là một phần tử của tập hợp A. Ký hiệu x  A Để chỉ x không là một phần tử của tập hợp A. Ký hiệu x  A Tập vũ trụ: Tập A nằm trong tập U thì U gọi là một vũ trụ của A. Tập hợp rỗng: Tập hợp không có phần tử nào được gọi là tập hợp rỗng, và được ký hiệu là  . Tập hợp bằng nhau: A = B  x  A thì x  B và  x  B thì x  A
2.CÁCH XÁC ĐỊNH MỘT TẬP HỢP. Cách liệt kê: Ta liệt kê tất cả các phần tử của tập hợp giữa 2 ký hiệu ngoặc  và  . Ví dụ: a A =  a, b, c  b c Cách nêu đặc trưng của phần tử: A =  x  U / p(x) với U là tập vũ trụ của tập A. hay vắn tắt (khi hiểu ngầm tập vũ trụ U): A =  x / p(x)  Ví dụ: A =  n  N / n là số nguyên tố   B =  n  N / có một số tự nhiên m sao cho n = m2 
3. QUAN HỆ "bao hàm trong" VÀ TẬP HỢP CON Định nghĩa: A  B (hay B  A)  x  A thì x  B Ví dụ:  0, 1, 2   n  N : n < 10 Các tập hợp số. N  Z  Q  R  C, trong đó  N là tập hợp các số tự nhiên,  Z là tập hợp các số nguyên,  Q là tập hợp các số hữu tỉ,  R là tập hợp các số thực,  C là tập hợp các số phức. Cho X là một tập hợp. Sưu tập tất cả các tập hợp con của X được ký hiệu là P(X). Nói một cách khác, P(X) là một tập hợp mà mỗi phần tử của nó là một tập hợp con của X. Ví dụ: X= 0, 1, 2 Thì P(X)= 0, 1, 2 Tính chất:   A và A  A, với mọi tập hợp A. (A  B)  (B  A)  (A = B) (A  B)  (B  C)  (A  C) X  Y  P(X)  P(Y) Nếu tập hợp X có n phần tử (n  N) thì tập hợp P(X) có 2n phần tử.
4.CÁC PHÉP TÓAN TẬP HỢP. Giao. A  B =  x : (x  A)  (x  B)  Hợp. A  B =  x : (x  A)  (x  B)  Hiệu. A - B =  x : (x  A)  (x  B)  Phần bù. Ac = U – A Tích Descartes của 2 tập hợp. A x B =  (a,b) : a  A  b  B  Trong trường hợp B = A, ta kỳ hiệu A x A = A2.
Các tính chất của các phép toán: Tính giao hoán: AB=BA AB=BA Tính kết hợp: A  (B  C) = (A  B)  C A  (B  C) = (A  B)  C Tính phân bố: A  (B  C) = (A  B)  (A  C) A  (B  C) = (A  B)  (A  C) Luật De Morgan: (A  B)c = Ac  Bc (A  B)c = Ac  Bc Phần tử trung hòa: A=A AU=A Phần bù: A  Ac = U A  Ac =  Tính thống trị: AU=U A=
II. ÁNH XẠ 2.1 Định nghĩa ánh xạ Cho X và Y là các tập hợp khác rỗng. Một ánh xạ f từ tập hợp X vào tập hợp Y là phép tương ứng sao cho bởi phép tương ứng nầy mỗi phần tử x của X sẽ có một phần tử duy nhất y của Y tương ứng mà ta ký hiệu là f(x) và gọi là ảnh của x. Ta viết f:XY x f(x) Ta thường minh họa ánh xạ f bởi sơ đồ sau đây: Hai ánh xạ f và g từ X vào Y được gọi là bằng nhau khi ta có:  x  X : f(x) = g(x) Cách xác định một ánh xạ. Ta có thể xác định ánh xạ f từ X vào Y bằng nhiều cách, chẳng hạn như cách liệt kê tất cả các ảnh của từng phần tử của X, cách cho một công thức để xác định ảnh f(x) của mỗi phần tử x, hoặc ta có thể đưa ra một thủ tục xác định để tính ra (hay tìm ra) được phần tử f(x) ứng với mỗi phần tử x  X. Ví dụ: f : N  N xác định bởi f(n) = 2(n+1). Thì f(1)=4 f(2)=6 ….
2.2 Ảnh và ảnh ngược Ảnh của tập hợp. Cho f là một ánh xạ từ X vào Y. Giả sử A là một tập hợp con của X. Ảnh của tập A qua ánh xạ f, ký hiểu bởi f(A), là tập hợp con của Y gồm tất cả những phần tử y sao cho y là ảnh của ít nhất một phần tử x thuộc A. f(A) =  f(a) : a  A  Ảnh ngược (hay tạo ảnh) của một tập hợp. Cho f là một ánh xạ từ X vào Y. Giả sử B là một tập hợp con của Y. Aûnh ngược của tập B bởi ánh xạ f, ký hiểu là f-1(B), là tập hợp con của X gồm tất cả những phần tử x sao cho f(x) thuộc B. f-1(B) =  x  X : f(x)  B  Trong trường hợp tập B chỉ có một phần tử y thì ảnh ngược của B sẽ được viết vắn tắt là f-1(y). Ví dụ: Cho ánh xạ f : Z  N xác định bởi f(n) = n2+1. Đặt A =  -2, -1, 0, 1, 2, 3 và B =  0, 1, 2, 3, 4, 5 . Ta có : f(A) =  1, 2, 5, 10 f-1(B) =  -2,-1, 0, 1,2 2.3 Các ánh xạ đặc biệt Đơn ánh: Ánh xạ f : X  Y được gọi là một đơn ánh khi các ảnh của 2 phần tử khác nhau tùy ý thì khác nhau, nghĩa là với mọi x và x' thuộc X ta có: x  x'  f(x)  f(x') hay f(x) = f(x')  x = x' Toàn ánh: Ánh xạ f : X  Y được gọi là một toàn ánh khi mọi phần tử của Y đều là ảnh của ít nhất một phần tử x thuộc X, nghĩa là f(X) = Y.
Song ánh: Aùnh xạ f : X  Y được gọi là một song ánh khi nó vừa là đơn ánh vừa là toàn ánh. Khi ấy với mỗi y  Y, có duy nhất phần tử x  X sao cho f(x) = y. Như thế phép tương ứng liên kết y với x sẽ cho ta một ánh xạ từ Y vào X. Ta gọi ánh xạ nầy là ánh xạ ngược của f và ký hiệu là f-1. Vậy ta có f-1 : Y  X, xác định bởi f-1(y) = x, với f(x) = y. Ví dụ: Ánh xạ f : Z  N xác định bởi f(n) = n2+1 không phải là một đơn ánh vì f(-1) = f(1) = 2 mà -1  1. Ánh xạ f : N  N xác định bởi f(n) = n2+1 là một đơn ánh vì ta có thể thấy rằng với mọi n và n' thuộc N ta có: nếu f(n) = f(n') thì n = n'. Cho a và b là 2 số thực tùy ý và a  0. Ánh xạ f : R  R xác định bởi f(x) = a.x+b là một song ánh vì với mọi số thực y thì phương trình ax + b = y có nghiệm thực x duy nhất là x = (y-b) / a. Từ đó ta cũng có ánh xạ ngược được xác định bởi f-1(y) = (y-b) / a.
III. CÁC NGUYÊN LÝ ĐẾM. 3.1 Phép Đếm Định nghĩa: Cho A là một tập hợp khác rỗng. Nếu tồn tại một số nguyên dương n và một song ánh f từ A vào  1, 2, . . ., n thì ta nói A là một tập hợp hữu hạn và A có n phần tử. Khi đó song ánh f : A   1, 2, . . ., n được xem là một phép đếm tập hợp A. Tập hợp rỗng có số phần tử là 0, và cũng được xem là tập hữu hạn. Số phần tử của một tập hợp hữu hạn A được ký hiệu là |A| (còn gọi là lực lượng của tập hợp A). Nếu tập hợp A không hữu hạn, ta nói A là vô hạn và viết |A| = 
3.2 Nguyên lý cộng Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau, nghĩa là A  B =  . Khi ấy ta có: | A  B | = | A | + | B | Một cách tổng quát: Nếu A1, A2, ..., An là các tập hợp hữu hạn rời nhau thì: | A1  A2  . . .  An | = | A1 | + | A2 | + . . . + | An | Nguyên lý bù trừ: Trong trường hợp đối với hai tập hợp hữu hạn A và B tùy ý thì ta có: |AB|=|A|+|B|-|AB| Nguyên lý cộng : để thực hiện một công việc ta có thể chọn một trong hai phương án khác nhau, cách thực hiện phương án thứ nhất luôn luôn khác cách thực hiện phương án thứ hai. Phương án thứ nhất có m cách thực hiện, và phương án thứ hai có n cách thực hiện. Thì tất cả sẽ có (m+n) cách thực hiện công việc.
3.3 Nguyên lý nhân Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau. Khi ấy ta có: |AxB|=|A|.|B| Một cách tổng quát: Nếu A1, A2, ..., An là các tập hợp hữu hạn thì số phần tử của tích Descartes của các tập hợp trên bằng tích của các số lượng phần tử của các tập hợp trên: | A1 x A2 x . . . x An | = | A1 | . | A2 | . . . . . | An | Nguyên lý nhân : Để thực hiện một công việc phải qua hai giai đọan kế tiếp nhau. Giai đọan thứ nhất ta có m cách làm, và ứng với mỗi cách làm giai đọan thứ nhất có n cách làm giai đọan thứ hai. Thì sẽ có (m*n) cách thực hiện công việc.
Ví dụ: Các ghế ngồi trong một hội trường sẽ được ghi nhãn gồm một mẫu tự và một số nguyên dương không lớn hơn 100. Hỏi số ghế tối đa có thể được ghi nhãn khác nhau là bao nhiêu? Lời giải. Thủ tục ghi nhãn cho một ghế gồm 2 giai đọan : ghi một trong 26 mẫu tự và kế tiếp là ghi một trong 100 số nguyên dương. Qui tắc nhân cho thấy có 26 x 100 = 2600 cách khác nhau để ghi nhãn cho một ghế ngồi. Do đó số ghế lớn nhất có thể được ghi nhãn khác nhau là 2600. Ví dụ: Một mật khẩu bao gồm 6 ký tự, trong đó gồm 3 mẫu tự rồi đến 3 ký số thập phân. Hỏi có bao nhiêu mật khẩu khác nhau? Lời giải. Có 26 cách chọn cho mỗi mẫu tự và có 10 cách chọn cho mỗi ký số thập phân. Do đó, theo qui tắc nhân, có tất cả 26.26.26.10.10.10 = 17 576 000 mã khác nhau. Ví dụ: Mỗi người sử dụng trên một hệ thống máy tính có một mật khẩu, dài từ 6 đến 8 ký tự, trong đó mỗi ký tự là một chữ in hoa hoặc là một ký số thập phân. Mỗi mật khẩu phải có chứa ít nhất một ký số. Hỏi có bao nhiêu mật khẩu khác nhau? Lời giải. Đặt P là số lượng tất cả các mật khẩu, và P6, P7, P8 lần lượt là số các mật khẩu có độ dài 6, 7, 8. Do qui tắc cộng ta có P = P6 + P7 + P8. Chúng ta sẽ tính P6, P7, và P8. Tính trực tiếp P6 tương đối khó. Để tính P6 cho dễ, ta tính số chuỗi có độ dài 6 gồm các chữ in hoa hay ký số thập phân (kể cả các chuỗi không có ký số thập phân), và trừ cho số chuỗi (với độ dài 6) không có ký số thập phân nào. Theo qui tắc nhân, số chuỗi gồm 6 ký tự là 366 và số chuỗi không có ký số nào là 266. Suy ra P6 = 366 - 266 = 2 176 782 336 - 308 915 776 = 1 867 866 560. Tương tự, ta có thể tính ra được : P7 = 367 - 267 = 78 364 164 096 - 8 031 810 176
= 70 332 353 920. và P8 = 368 - 268 = 2 821 109 907 456 - 208 827 064 576 = 2 612 282 842 880. Từ đó ta tính được : P = P6 + P7 + P8 = 2 684 483 063 360.
IV. GIẢI TÍCH TỔ HỢP. LỌAI KÝ HIỆU CÔNG THỨC Không k n! A( n, k ) hay A Ank  n * ( n  1) * ... * ( n  k  1)  Chỉnh Lặp n ( n  k )! Hợp Có Pnk  n k P(n, k) hay P kn Lặp Không n A( n, n ) hay A n Ann  n! Hóan Lặp vị Có n! Lặp n1! * n 2 ! * ..... * n k ! Không k k n! Lặp C C (n, k ) hay Cn n  Tổ k ! ( n  k )! Hợp Có k ( n  k  1)! Lặp C n  k 1  k ! ( n  1)!
Với mọi số thự nhiên n ta có: C(n, 0) = 1 C(n, n) = 1 Cho n và r là 2 số nguyên không âm và k  n. Ta có: C(n,k) = C(n,n-k) Cho n và k là 2 số nguyên sao cho 0 < k < n. Khi đó ta có: C(n, k) = C(n-1, k) + C(n-1, k-1). Ðịnh lý. Cho x và y là 2 biến thực, n là một số nguyên không ấm tùy ý. Ta có: Hệ quả 1. Cho n là một số nguyên không âm tùy ý. Ta có: Hệ quả 2. Cho n là một số nguyên không âm. Ta có:
BÀI TẬP Bài 1: Có bao nhiêu chuỗi nhị phân dài tối đa 6 bit? Bài 2: Có bao nhiêu chuỗi nhị phân dài 10 bit, sao cho bit đầu bằng 0 hay bit cuối bằng 1. Bài 3: Một mật khẩu phải có độ dài 6 ký tự (không phân biệt ký tự hoa, thường), mỗi ký tự được lấy từ bảng 26 chữ cái và 10 chữ số. Tính số mật khẩu có thể tạo ra trong mỗi trường hợp sau: a) Không có điều kiện gì thêm. b)Trong mật khẩu phải có ít nhất một ký tự số. c) Trong mật khẩu phải có ít nhất một ký tự số và không có ký tự A. Bài 4: Có bao nhiêu dãy nhị phân dài 12 bit, chứa ít nhất 3 bit 0 và 3 bit 1. Bài 5: Cần bầu một ủy ban gồm 6 đại biểu, chọn từ 8 Bà và 8 Ông ứng viên. Có bao nhiêu cách chọn trong mỗi trường hợp sau: a) Chọn tùy ý? b)Chọn số Bà bằng số Ông? c) Chọn số Bà ít hơn số Ông? Bài 6: Có bao nhiêu tam giác được tạo ra từ 9 điểm phân biệt trên mặt phẳng sao cho không có 3 điểm nào thẳng hàng. Bài 7: Có 100 vé số, được đánh số từ 1 đến 100, được bán cho 100 người khác nhau. Người ta sẽ trao 4 giải thưởng nhất, nhì, ba, tư. Hỏi a) Có bao nhiêu cách trao giải? b)Có bao nhiêu cách trao giải, nếu người có vé 50 trúng giải nhất? c) Có bao nhiêu cách trao giải, nếu người có vé 50 không trúng giải nào? d)Có bao nhiêu cách trao giải, nếu 3 người có vé 10,15, 20 trúng giải? e) Có bao nhiêu cách trao giải, nếu 2 người có vé 20,30 trúng giải, nhưng người có vé 15 không trúng giải? Bài 8: Có 6 người vào tiệm ăn phở, trong tiệm có 4 lọai phở. Hỏi có bao nhiêu cách gọi cho mỗi người 1 tô phở?
Bài 9: Cô dâu, chú rể, cùng chụp hình với 6 người bạn, có bao nhiêu cách xếp thành 1 hàng ngang để chụp, trong mỗi trường hợp sau: a) Xếp tùy í? b)Xếp sao cho cô dâu, chú rể luôn bên nhau? c) Xếp sao cho cô dâu luôn bên trái chú rể? d)Xếp sao cho cô dâu, chú rể đứng đúng giữa hàng?