Bài Giảng Toán Rời Rạc - Chương 2: Phép đếm - TaiLieu.VN

Trang chủ » Nguyên Lý Cộng Toán Rời Rạc » Bài Giảng Toán Rời Rạc - Chương 2: Phép đếm - TaiLieu.VN

Có thể bạn quan tâm

OPTADS360 intTypePromotion=1 zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn tailieu.vn NÂNG CẤP Đăng Nhập | Đăng Ký Chủ đề »
  • Đề thi toán cao cấp 2
  • Đại số tuyến tính
  • Toán rời rạc
  • Xác suất thống kê
  • Phương trình vi phân
    • Toán cao cấp
    • Toán kinh tế
  • HOT
    • LV.26: Bộ 320 Luận Văn Thạc Sĩ Y...
    • LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên...
    • CEO.29: Bộ Tài Liệu Hệ Thống Quản Trị...
    • CEO.24: Bộ 240+ Tài Liệu Quản Trị Rủi...
    • FORM.08: Bộ 130+ Biểu Mẫu Thống Kê...
    • FORM.07: Bộ 125+ Biểu Mẫu Báo Cáo...
    • CMO.03: Bộ Tài Liệu Hệ Thống Quản Trị...
    • FORM.04: Bộ 240+ Biểu Mẫu Chứng Từ Kế...
    • CEO.27: Bộ Tài Liệu Dành Cho StartUp...
    TL.01: Bộ Tiểu Luận Triết Học
TUYỂN SINH YOMEDIA ADSENSE Trang Chủ » Khoa Học Tự Nhiên » Toán học Bài giảng Toán rời rạc - Chương 2: Phép đếm

Chia sẻ: Cvcxbv Cvcxbv | Ngày: | Loại File: PPT | Số trang:62

Thêm vào BST Báo xấu 914 lượt xem 53 download Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung chính của chương 2 Quan hệ trong bài giảng Toán rời rạc nêu 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. 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.

AMBIENT/ Chủ đề:
  • Giải tích tổ hợp
  • Hoán vị lặp
  • Tổ hợp lặp
  • Hệ thức đệ qui
  • Bài giảng toán rời rạc
  • Toán rời rạc
  • Tài liệu toán rời rạc

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

Đă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 - Chương 2: Phép đếm

  1. LOGO Chương 2 TOÁN RỜI RẠC
  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 a có 4 cách chọn ( a∈X\{c, 0} ) TH2 có 2.4.4 =32 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) 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�ừ k � n/ t bồ câu trở lên, trong� / k � n đó là số nguyên nhỏ nhất lớn hơn hay bằng n/k. 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 tháng.
  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 A∩B B
  9. Cơ sở Logic I. Các nguyên lý C A∩C B∩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à Pn 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ử. k Số các chỉnh hợp chập k của n ký hiệu làAn - Công thức n! A = k n ( n−k)! 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. 3 Kết quả: A6
  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ử. k n Số tổ hợp chập k của n phần tử được kí hiệu là C n hay   k    n! C = k k !( n − k ) ! n Tính chất C n−k n =C k n Cn + Cnk −1 = Cn+1 k k
  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 - Số cách chọn là tổ hợp chập 10 của 30. C30
  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 n k n + k −1
  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 3 = C3+2−1 = C4 = 6 2 2 2
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

  • Bài giảng Toán rời rạc - Chương 1: Quan hệ

    ppt 37 p | 826 | 142

  • Bài giảng Toán rời rạc 1 - Học viện Công nghệ Bưu chính Viễn thông

    pdf 119 p | 884 | 68

  • Bài giảng Toán rời rạc: Phần V & VI - GVC ThS.Võ Minh Đức

    ppt 26 p | 587 | 63

  • Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 3: Đồ thị phẳng và bài toán tô màu đồ thị

    ppt 30 p | 293 | 48

  • Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 2: Các bài toán về đường đi

    ppt 48 p | 223 | 45

  • Bài giảng Toán rời rạc - Chương 3: Đại số Bool

    ppt 68 p | 247 | 37

  • Bài giảng Toán rời rạc - Nguyễn Đức Nghĩa

    pdf 33 p | 326 | 31

  • Bài giảng Toán rời rạc: Bài 10 - TS. Nguyễn Văn Hiệu

    pdf 32 p | 152 | 26

  • Bài giảng Toán rời rạc: Bài 9 - TS. Nguyễn Văn Hiệu

    pdf 21 p | 118 | 24

  • Bài giảng Toán rời rạc: Bài 2 - TS. Nguyễn Văn Hiệu

    pdf 37 p | 163 | 20

  • Bài giảng Toán rời rạc: Bài 1 - TS. Nguyễn Văn Hiệu

    pdf 31 p | 223 | 20

  • Bài giảng Toán rời rạc: Bài 7 - TS. Nguyễn Văn Hiệu

    pdf 24 p | 128 | 16

  • Bài giảng Toán rời rạc: Bài 4 - TS. Nguyễn Văn Hiệu

    pdf 16 p | 138 | 14

  • Bài giảng Toán rời rạc: Bài 6 - TS. Nguyễn Văn Hiệu

    pdf 46 p | 108 | 11

  • Bài giảng Toán rời rạc: Bài 5 - TS. Nguyễn Văn Hiệu

    pdf 61 p | 111 | 11

  • Bài giảng Toán rời rạc: Bài 8 - TS. Nguyễn Văn Hiệu

    pdf 40 p | 103 | 10

  • Bài giảng Toán rời rạc: Bài 11 - TS. Nguyễn Văn Hiệu

    pdf 39 p | 103 | 8

  • Bài giảng Toán rời rạc: Bài 2 - Vũ Thương Huyền

    pdf 42 p | 40 | 3

Thêm tài liệu vào bộ sưu tập có sẵn: Đồng ý Thêm vào bộ sưu tập mới: *Tên bộ sưu tập Mô Tả: *Từ Khóa: Tạo mới Báo xấu
  • Hãy cho chúng tôi biết lý do bạn muốn thông báo. Chúng tôi sẽ khắc phục vấn đề này trong thời gian ngắn nhất.
  • Không hoạt động
  • Có nội dung khiêu dâm
  • Có nội dung chính trị, phản động.
  • Spam
  • Vi phạm bản quyền.
  • Nội dung không đúng tiêu đề.
Hoặc bạn có thể nhập những lý do khác vào ô bên dưới (100 ký tự): Vui lòng nhập mã xác nhận vào ô bên dưới. Nếu bạn không đọc được, hãy Chọn mã xác nhận khác.. Đồng ý LAVA AANETWORK THÔNG TIN
  • Về chúng tôi
  • Quy định bảo mật
  • Thỏa thuận sử dụng
  • Quy chế hoạt động
TRỢ GIÚP
  • Hướng dẫn sử dụng
  • Upload tài liệu
  • Hỏi và đáp
HỖ TRỢ KHÁCH HÀNG
  • Liên hệ
  • Hỗ trợ trực tuyến
  • Liên hệ quảng cáo
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

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

Đang xử lý... Đồng bộ tài khoản Login thành công! AMBIENT

Từ khóa » Nguyên Lý Cộng Toán Rời Rạc