Cấu trúc rời rạc Chương II. Phép đếm

Phép đếm Nhóm 7 Cấu trúc rời rạc Chương II Cấu trúc rời rạc Nội dung 1 2 Phép đếm Nhị thức Newton Tập hợp 3 Tập hợp bằng nhau: Tập A được gọi là bằng tập B, nếu mọi phần tử của tập A đều là phần tử của tập B và ngược lại mọi phần tử của B đều là phần tử của A. ( x  A)  ( x  B) Tập con: Tập A được gọi là tập con của tập hợp X, nếu mọi phần tử của A đều là phần tử của X, kí hiệu là A X. (A  X)  ( x  A  x  X) I.Tập hợp Ví dụ : + A= a, b, c,d, X = a, b, c, d, x, y, z Khi đó A  X. + Z2=Tập các số chẵn,Z=Tập các số nguyên Khi đó Z2  Z. Nếu A là tập con của X và A không bằng X, thì A được gọi là tập con thực sự của tập X, kí hiệu là A X. Hình 1.1. Tập con Text + Tập rỗng: Tập hợp không chứa phần tử nào gọi là tập rỗng, kí hiệu là . Tập rỗng là tập con của mọi tập hợp. Ví dụ 3: A= Tập các nghiệm thực của phương trình: x2 +1= 0  Khi đó A= . + Tập các tập con: Tập tất cả các tập con của A bao gồm cả tập rỗng và A là một tập hợp. Kí hiệu là p(A). Ví dụ 1.4 : Cho tập A= 2, 4, 6 p(A)= 2, 4, 6, 2, 4, 2, 6, 4, 6, 2, 4, 6,     Các phép toán trên tập hợp. + Phép hợp: Hợp của hai tập hợp A và B là một tập hợp bao gồm các phần tử thuộc ít nhất một trong hai tập hợp đã cho. Kí hiệu là A  B. xA  B  xA  xB. A=1, 3, 5, 7 B=2, 3, 4, 5 A  B =1,2, 3, 4, 5, 7 + Phép giao: Giao của hai tập A và B là một tập hợp bao gồm các phần tử thuộc cả hai tập đã cho. Kí hiệu là A  B . x A  B  xA  xB. A=1, 3, 5, 7 B=2, 3, 4, 5 A  B =3, 5 + Phép hiệu : Hiệu của hai tập hợp A và B là một tập hợp bao gôm các phần tử thuộc A nhưng không thuộc B. Kí hiệu: A \ B xA \ B  xA  xB. A=1, 3, 5, 7 B=2, 3, 4, 5 A \ B =1,7 + Hiệu đối xứng: Hiệu đối xứng của hai tập hợp A và B là một tập hợp. Kí hiệu là: A  B xA  B  x A  B  x A  B . A=1, 3, 5, 7 B=2, 3, 4, 5 A  B =1,2,4,7 Phần bù :Cho AE thì E=1, 2, 3, 4, 5, 6, 7 A=2, 3, 4, 5 A =1,6,7 Tích Descartes: A B = {(a,b) aA,b B} A1A2…An = {(a1,a2,…,an) aiA i , i = 1,2,…,n} Tổng quát: Tính chất của phép toán trên tập hợp 1) Tính luỹ đẳng: A  A = A và A  A = A 2) Tính giao hoán: A  B = B  A và A  B = B  A. 3) Tính kết hợp: (A  B)  C = A  (B  C) và (A  B)  C = A  (B  C) 4) Tính phân phối: A  (B  C) = (A  B)  (A  C) và A  (B  C) = (A  B)  (A  C) 5) Công thức De Morgan: Suy ra: A \ (B  C) = (A \ B)  (A \ C) và A \ (B  C) = (A \ B)  (A \ C). Lực lượng của tập hợp Cho A là tập hợp hữu hạn.Số phần tử của tập A ký hiệu là A.Ta có: 1) AB = A+ B - AB . 2) AB = A B 3) P (A) = 2 A ,P (A) là tập các tập con của A A=1, 3, 5, 7; B= 3, 5,6; AB = {1,3,5,6,7}; AB={3,5} |A| = 4; |B| = 3; |AB | = 5; |AB| = 2 P (A)=24=16 Các phương pháp chứng minh PP1: Chứng minh trực tiếp Áp dụng phép suy diễn logic: A1 → A2→ ... Ak → B VD: Với mọi n nguyên thì n2 – n + 5 là một số lẻ CM: Với mọi n nguyên: n(n-1) là một số chẵn → n(n-1) +5 = n2 – n + 5 là một số lẻ Các phương pháp chứng minh PP2: Chứng minh lựa chọn VD: CMR với mọi n nguyên, 9n2 + 3n – 2 là một số chẵn. CM: Ta có 9n2 + 3n – 2 = (3n+2) (3n-1). Xảy ra 2 TH - TH1: 3n+2 là số chẵn → (3n+2) (3n-1) là số chẵn TH2: 3n+2 là số lẻ → (3n+2)-3 là số chẵn → (3n+2)(3n-1) là số chẵn Các phương pháp chứng minh PP3: Chứng minh phản chứng: Để chứng minh mệnh đề A đúng ta chỉ cần CMR phủ định của A là sai. Chú ý: Ta thường dựa vào công thức logic sau A → B = B → A VD: CMR nếu n là số nguyên và n2 chẵn thì n chẵn. Ta cần CM nếu n lẻ thì n2 lẻ. Mà n lẻ → n = 2m +1 → n2 = 4m2 + 4m + 1 là số lẻ Các phương pháp chứng minh PP4: Chứng minh quy nạp: CM mệnh đề “với mọi n ≥ n0 ta có P(n) đúng” - B1: Kiểm tra, CM P(n0) đúng B2: Giả thiết rằng với n=k (k > n0), P(k) đúng, ta cần CM P(k+1) đúng Kết luận P(n) đúng với mọi n≥n0 Các phương pháp chứng minh PP4: Chứng minh quy nạp: Áp dụng: Để đưa ra công thức tổng quát liên quan đến số tự nhiên n thường vận dụng theo hai bước B1: Quy nạp không hoàn toàn: Để tìm và đưa ra công thức P(n) tổng quát B2: Quy nạp hoàn toàn hay CM công thức P(n) đã dự đoán trên bằng PP quy nạp II. Phép đếm 1. Nguyên lý cộng và nguyên lý nhân 1.1. Nguyên lý cộng. Nếu có m cách chọn x, n cách chọn đối tượng y và nếu cách chọn đối tượng x không trùng với bất kỳ cách chọn đối tượng y nào ,thì có m+n cách chọn 1 trong các đối tượng đã cho. 1.2. Nguyên lý nhân. Nếu có m cách chọn đối tượng x và cứ mỗi cách chọn x luôn luôn có n cách chọn đối tượng y thì có m.n cách chọn cặp đối tượng (x, y). * Ví dụ. Cho A và B là hai tập hợp.Tập hợp các ánh xạ từ A vào B được ký hiệu bởi BA.Giả sử A=m , B= n thì BA= nm.Thật vậy, mỗi phần tử ai thuộc A có n cách chọn ảnh f(a i) của nó trong tập B. Theo qui tắc nhân ta có n.n. …n = nm cách chọn bộ (f(a1), f(a2), …, f(an)).Tức là ta có nm ánh xạ. * 2. Hoán vị. a) Định nghĩa. Cho tập hợp A gồm n phần tử .Mỗi cách sắp đặt có thứ tự n phầntử của A được gọi là một hoán vị của n phần tử.Số các hoán vị của n phần tử ký hiệu là Pn b) Pn = n! c) Ví dụ :Nếu A là tập hợp n phần tử thì số song ánh từ A vào A là n! * Ví dụ 1: Sắp xếp 6 học sinh vào vào 6 cái ghế. Hỏi có bao nhiêu cách sắp xếp? Đáp án: P6 = 6!=1.2.3…6=720 Ví Dụ 2: Cho tập A gồm 5 chữ số hệ thập phân A={1,2,3,4,5}.Tìm các số tự nhiên có 5 chữ số khác nhau lập thành từ 5 số trên. Giải: Ta có 5!=120 số 3. Chỉnh hợp. a) Định nghĩa . Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử (1 k n) sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử. Số các chỉnh hợp chập k của n ký hiệu là b)Công thức * Ví Dụ : Cho tập A gồm 5 chữ số hệ thập phân A={1,2,3,4,5}. tìm các số tự nhiên gồm 3 chữ số khác nhau lập thành từ 5 chữ số trên. Giải   Số 4.Tổ hợp. a) Định nghĩa. Cho tập hợp A gồm n phần tử.Mỗi tập con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử.Số các tổ hợp chập k của n phần tử đựơc ký hiệu là hay * b) Công thức c) Tính chất với mọi 0  k  n; với mọi 1  k  n * Ví dụ: Trong   lớp học có   học sinh nam và   học sinh nữ. Thầy giáo cần  học sinh nam và  học sinh nữ đi tham gia lao động. Hỏi có bao nhiêu cách? Giải: Ta có:cách chọn  4 học sinh nam trong số 20  học sinh nam và có cách chọn  3 HS nữ trong số  15 HS nữ. Theo quy tắc nhân, số cách chọn cần tìm là:   cách chọn 5. Hoán vị lặp. a) Định nghĩa Cho n đối tượng trong đó có ni đối tượng loại i giống hệt nhau (i =1,2,…,k ; n1+ n2,…+ nk= n). Mỗi cách sắp xếp có thứ tự n đối tượng đã cho gọi là một hoán vị lặp của n. * b) Số hoán vị của n đối tượng, trong đó có n1 đối tượng giống nhau thuộc loại 1, n2 đối tượng giống nhau thuộc loại 2,…, nk đối tượng giống nhau thuộc loại k, là * Ví dụ: Số các “chữ” khác nhau có thể có được bằng cách dùng các con chữ của chữ “Mississippi” là: 11! = 34 650 4!4!2!1! * 6.Tổ hợp lặp. a) Định nghĩa. Mỗi cách chọn ra k vật từ n loại vật khác nhau (trong đó mỗi loại vật có thể được chọn lại nhiều lần) được gọi là tổ hợp lặp chập k của n. Số các tổ hợp lặp chập k của n được ký hiệu là * b) Công thức c)Hệ quả. Số nghiệm nguyên không âm (x1,x2,…,xn) (mỗi xi đều nguyên không âm) của phương trình x1+ x2+…+ xn = k là * Số cách chia k vật đồng chất nhau vào n hộp phân biệt cũng chính bằng số tổ hợp lặp chập k của n * Ví dụ. Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có bao nhiêu cách chọn. Chương 2.phép đếm 38 Ta có mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể AA, AB, AC, BB, BC, CC Ví dụ : Tìm số nghiệm nguyên không âm của phương trình x1+ x2 + x3 + x4 = 20 (1) Thỏa điều kiện x1  3; x2  2; x3 > 4 (). Giải. Ta viết phương trình đã cho thành x1  3; x2  2; x3  5. Xét các điều kiện sau: x2  2; x3  5 () x1  4; x2  2; x3  5 () Gọi p, q, r lần lượt là các số nghiệm nguyên không âm của phương trình (1) thỏa các điều kiện (*), (**), (***). Ta có: p = q – r. * Trước hết ta tìm q. Đặt x1’ = x1; x2’ = x2 – 2; x3’ = x3 - 5; x4’ = x4 Phương trình (1) trở thành x1’+ x2’ + x3’ + x4’ = 13 (2) Số nghiệm nguyên không âm của phương trình (1) thỏa điều kiện (**) bằng số nghiệm nguyên không âm của phương trình (2) * Số nghiệm đó là . Vậy . Lý luận tương tự, ta có . Suy ra Vậy số nghiệm nguyên không âm của phương trình (1) thỏa điều kiện (*) là 340 * Ví dụ: Tìm số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 có ít nhất 5 bi, biết rằng hộp 2 và 3 chứa không quá 6 bi. Giải. Trước hết ta tìm số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 có ít nhất 5 bi. Nhận xét rằng ta cần lấy 5 bi để xếp trước vào hộp 1, do đó số bi còn lại chỉ là 25. Suy ra số cách xếp trong trường hợp này bằng số cách xếp 25 bi vào 5 hộp mà không có điều kiện gì thêm. Số đó là * Tương tự ta có - Số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, hộp 2 chứa ít nhất 7 bi là: * - Số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, hộp 3 chứa ít nhất 7 bi là: Số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, mỗi hộp 2 và 3 chứa ít nhất 7 bi là: * Sử dụng công thức ta suy ra số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, đồng thời hộp 2 hay hộp 3 chứa ít nhất 7 bi là Theo yêu cầu của bài toán, khi xếp 30 viên bi vào 5 hộp thì hộp 1 phải có ít nhất 5 bi còn mỗi hộp 2 và 3 phải có không quá 6 bi. Do đó số cách xếp này sẽ bằng hiệu của hai cách xếp (1) và (2), tức là bằng * 7. NGUYÊN LÝ DIRICHLET (nguyên lý chuồng bồ câu) . *      - Chứng bằng lập luận phản chứng: Giả sử không hộp nào chứa nhiều hơn một đối tượng thì chỉ có nhiều nhất là n đối tượng được xếp trong các hộp, trái với giả thiết là số đối tượng lớn hơn n. * Ví dụ : Cho tập X ={1,2,3,4,5,6,7,8,9}. Lấy A là tập hợp con của X gồm 6 phần tử. Khi đó trong A sẽ có 2 phần tử có tổng bằng 10 III. Khai triển nhị thức Newton Với a, b  R và n là số nguyên dương ta có: 1.Công thức NEWTON 2.Nhận Xét Trong triển khai NewTon có các tính chất sau: *Gồm có n+1 toán hạng *Số mủ của a giảm từ n đến 0 và số mủ của b tăng từ 0 đến n. *Tổng số mủ của a và b trong mổi số hạng bằng n. *Các hệ số có tính đối xứng: *Số hạng tổng quát: * 3.Một số hệ quả Hệ quả: Ta có: Từ triển khai này ta có các kết quả sau: * Vd1:Tìm số hạng chứa trong khai triển: Vậy ta có hệ số của là: thỏa Hệ số trong khai triển của : Dạng : Tính tổng Ví dụ 2: Tính tổng a. b. We are UITer Members Huỳnh Văn An 11520003 Sơ Tuấn Hoàng 11520122 Nguyễn Xuân Biển 11520023 Nguyễn Văn Hùng 11520134 Nguyễn Công Sang 11520622 Nguyễn Quang Hải 11520542 Bùi Tất Khải 11520578 Võ Đại Đồng 11520067 Trương Xuân Đạt 11520050 Vũ Đức Phong 10520546