Giải bài tập toán rời rạc Chương 2

Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.

Giải bài tập toán rời rạc Chương 2

Tóm tắt nội dung tài liệu

  1. LOGO Chương 2 Lê Văn Luyện email: TOÁN RỜI RẠC www.math.hcmus.edu.vn/~lvluyen/trr
  2. Phép đếm Chương II: PHÉP ĐẾM - Các nguyên lý - Giải tích tổ hợp - Hoán vị lặp, tổ hợp lặp - Hệ thức đệ qui
  3. Phép đếm I. Các nguyên lý 1. Nguyên lý cộng Giả sử để làm công việc A có 2 phương pháp - Phương pháp 1 có n cách làm - Phương pháp 2 có m cách làm Khi đó số cách làm công việc A là n+m Ví dụ. An có 3 áo tay dài, 5 áo tay ngắn. Để chọn 1 cái áo thì An có mấy cách
  4. Phép đếm I. Các nguyên lý 2. Nguyên lý nhân Giả sử để làm công việc A cần thực hiện 2 bước - Bước 1 có n cách làm - Bước 2 có m cách làm Khi đó số cách làm công việc A là n.m Ví dụ: A B C Có 3.2 =6 con đường đi từ A đến C
  5. Phép đếm I. Các nguyên lý Ví dụ: Cho tập X ={1,2,3,4,5,0} Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia hết cho 2 Giải. Gọi số có 3 chữ số là abc TH1 . c=0. Khi đó c có 1 cách chọn a có 5 cách chọn ( aX\{0} ) TH1 có 1.4.5 =20 b có 4 cách chọn ( bX\{a, 0} ) TH2 . c≠0. Khi đó c có 2 cách chọn TH2 có 2.4.4 =32 a có 4 cách chọn ( aX\{c, 0} ) b có 4 cách chọn ( bX\{a, c} ) Vậy có 20+32 =52
  6. Phép đếm I. Các nguyên lý 3. Nguyên lý chuồng bồ câu (Derichlet) Gọi  x  là số nguyên nhỏ nhất lớn hơn hay bằng x.  Giả sử có n chim bồ câu ở trong k chuồng. Khi đó tồn tại ít nhất một chuồng chứa từ  n / k  bồ câu trở lên.   Ví dụ. Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1 chuồng có 3 con bồ câu trở lên - Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày
  7. Phép đếm I. Các nguyên lý 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ó hai phần tử có tổng bằng 10. Giải. Ta lập các chuồng như sau: {1,9} {2,8} {3,7} {4,6} {5} Do A có 6 phần tử nên trong 6 phần tử đó sẽ có 2 phần tử trong 1 chuồng. Suy ra đpcm
  8. Phép đếm I. Các nguyên lý 4. Nguyên lý bù trừ. Cho A và B là hai tập hữu hạn. Khi đó |A  B|= |A|+|B| - |A  B| A B A B
  9. Cơ sở Logic I. Các nguyên lý C BC A C A B  C A B A B |A  B  C|=?
  10. Phép đếm I. Các nguyên lý Ví dụ. Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS học Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh học Tiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu người Giải. Gọi A là những học sinh học Tiếng Pháp B là những học sinh học Tiếng Anh Khi đó. Số học sinh của lớp là |A  B |. Theo nguyên lý bù trừ ta có |A  B|= |A|+|B| - |A  B|=24+26-15=35
  11. Phép đếm II. Giải tích tổ hợp 1. Hoán vị Đị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ần tử 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à P n Pn = n! = n.(n-1).(n-2)…1 Quy ước 0! =1 Ví dụ. Cho A ={a,b,c}. Khi đó A có các hoán vị sau abc,acb, bac,bca, cab,cba
  12. Phép đếm 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! Cho X ={1,2,3,4,5}. Hỏi có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau được tạo từ tập X  5!
  13. Phép đếm II. Giải tích tổ hợp 2. Chỉnh hợp. Đị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ử. Ank Số các chỉnh hợp chập k của n ký hiệu là - Công thức n! A k  n  k ! n Ví dụ. Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2 của 3 là: ab, ba, ac, ca, bc, cb.
  14. Phép đếm II. Giải tích tổ hợp Ví dụ. Có bao nhiêu số tự nhiên gồm 3 chữ số được tạo thành từ 1,2,3,4,5,6. Kết quả: A6 3
  15. Phép đếm II. Giải tích tổ hợp 3.Tổ hợp. Đị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ử. n k  C Số tổ hợp chập k của n phần tử được kí hiệu là hay k  n  n! C k k ! n  k ! n Cn  Cn 1  Cn1 n k C k k k k Tính chất C n n
  16. Phép đếm II. Giải tích tổ hợp Ví dụ. Cho X = {1,2,3,4}. Tổ hợp chập 3 của 4 phần tử của X là {1,2,3}, {1,2,4}, {1,3,4} , {2,3,4} Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn 10 C30 - Số cách chọn là tổ hợp chập 10 của 30.
  17. Phép đếm III. Hoán vị lặp, tổ hợp lặp 1. Hoán vị lặp Đị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. Số hoán vị của n đối tượng, trong đó có n1 đối tượng giống nhau thuộc loại 1, n! n2 đối tượng giống nhau thuộc loại 2,…, n1 !n2 !...nk ! nk đối tượng giống nhau thuộc loại k, là
  18. Phép đếm II. Giải tích tổ hợp Ví dụ. Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các chữ cái của từ SUCCESS? Giải. Trong từ SUCCESS có 3 chữ S, 1 chữ U, 2 chữ C và 1 chữ E. Do đó số chuỗi có được là . 7!  420 3!1!2!1!
  19. Phép đếm III. Hoán vị lặp, tổ hợp lặp 2. Tổ hợp lặp Đị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 k Số các tổ hợp lặp chập k của n được ký hiệu là K n K C k k n k 1 n
  20. Phép đếm III. Hoán vị lặp, tổ hợp lặp 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. 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 K C C 6 2 2 2 321 3 4


Page 2

YOMEDIA

Tài liệu tham khảo dành cho giáo viên, sinh viên chuyên ngành công nghệ thông tin - Giáo trình, bài tập toán rời rạc. Mời các bạn tham khảo để biết thêm nhiều kiến thức về toán rời rạc, các nguyên lý toán thống kê. Chúc các bạn học tốt.

27-09-2011 1408 271

Download

Giải bài tập toán rời rạc Chương 2

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.

Download bài tập Toán rời rạc có đáp án PDF ✓ Bài tập Toán rời rạc có lời giải chương 1, 2, 3, 4, 5, 6, 7 ✓ Các dạng bài tập toán rời rạc có lời giải ✓ File PDF ✓ Tải xuống miễn phí các bài tập toán rời rạc có lời giải PDF link Google Drive

Giải bài tập toán rời rạc Chương 2

File tài liệu tổng hợp các dạng bài tập Toán rời rạc có đáp án, lời giải chi tiết được soạn sẵn file PDF là tài liệu để sinh viên học cao đẳng, đại học học tập, ôn thi, giúp các bạn chuẩn bị tốt cho kỳ thi kết thúc học phần, thi cuối kỳ môn môn Toán rời rạc sắp đến. 

Nội dung bài tập Toán rời rạc có lời giải gồm có:

  • Bài tập chương 1: Cơ sở logic 
  • Bài tập chương 2: Tập hợp và ánh xạ 
  • Bài tập chương 3: Phương pháp đếm
  • Bài tập chương 4: Hệ thức đệ qui
  • Bài tập chương 5: Quan hệ hai ngôi
  • Bài tập chương 6: Hàm Bool
  • Bài tập chương 7: Đại cương về đồ thị
  • Hướng dẫn giải bài tập Toán rời rạc theo từng chương

XEM TRƯỚC 11 TRANG

TẢI FULL TÀI LIỆU

>> Xem thêm tài liệu Toán rời rạc

  • Giáo trình toán rời rạc PDF
  • Toán rời rạc Nguyễn Hữu Anh PDF

Giải bài tập toán rời rạc Chương 2
1
Giải bài tập toán rời rạc Chương 2
88 KB
Giải bài tập toán rời rạc Chương 2
2
Giải bài tập toán rời rạc Chương 2
396

Giải bài tập toán rời rạc Chương 2

Nhấn vào bên dưới để tải tài liệu

Để tải xuống xem đầy đủ hãy nhấn vào bên trên

Bài tập chương 2 Lưu ý: N: Tập hợp số tự nhiên, Z: Tập hợp số nguyên, R: Tập hợp số thực. Bài 2.1. Giả sử A = { 1, {1}, {2} }. Hãy chỉ ra các khẳng định đúng trong số các khẳng định sau: a) 1 ∈ A b) {1} ∈ A c) {1} ⊂ A d) {{1}} ⊂ A e) {{2}} ∈ A f) {2} ⊂ A Bài 2.2. Xét 4 tập hợp con của tập hợp vũ trụ U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}: A = {1, 2, 3, 4, 5}; C = {1, 2, 3, 5, 7}; B = {1, 2, 4, 8} D = {2, 4, 6, 8} Hãy xác định các tập hợp sau: a) (A ∪ B) ∩ C b) A ∪ (B ∩ C) c) C ∪ D d) C ∩ D e) (A ∪ B) ∩ C f) A ∪ (B ∩ C) Bài 2.3. Cho A, B, C là các tập hợp. Chứng minh rằng: a) A ∩ (B\C) = (A ∩ B)\(A ∩ C) b) (A\B) ∪ (B\A) = (A ∪ B)\(A ∩ B) c) A\(A ∩ B) = (A ∪ B)\B Bài 2.4. Cho f, g : R → R được xác định bởi f (x) = 2x + 1 và g(x) = x2 + x − 1. Hãy tìm g◦ f và f◦ g? Bài 2.5. Xét hai ánh xạ f, g : R → R xác định bởi: f (x) = ax + b và g(x) = 1 − x + x2 . Giả sử g◦ f (x) = 9x2 − 9x + 3, hãy xác định a, b. Bài 2.6. Xét ánh xạ f : R → R xác định bởi f (x) = x2 − 3. Hãy tìm f (A) và f −1 (A) đối với mỗi tập hợp A dưới đây: a) A = {2, 3} b) A = {−3, −2, 2, 3} c) A = (−3, 3) d) A = (−3, 2] e) A = [−7, 2] f ) A = (−4, −3] ∪ [5, 6] Bài 2.7. Với mỗi ánh xạ f : Z → Z dưới đây, hãy xác định xem nó có là đơn ánh, toàn ánh hoặc song ánh không? Trong trường hợp nó là song ánh, hãy tìm ánh xạ ngược? a) f (x) = x + 7 b) f (x) = 2x − 3 c) f (x) = −x + 5 e) f (x) = x2 e) f (x) = x2 + x f) f (x) = x3 Bài 2.8. Các câu hỏi tương tự như trong bài tập 2.6 nhưng f bây giờ là một ánh xạ f : R → R Bài 2.9. Với mỗi ánh xạ f : A → B dưới đây, cho biết nó có đơn ánh, toàn ánh hoặc song ánh không? Trong trường hợp nó là song ánh, hãy tìm ánh xạ ngược? a) A = B = R, f (x) = x + 7 b) A = B = R, f (x) = x2 + 2x − 3 c) A = [4, 9], B = [21, 96], f (x) = x + 7 d) A = R, B = (0, +∞), f (x) = 2x+1 e) A = B = N, f (x) = x(x + 1)

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.