Chương III: Phép đếm

Chia sẻ: Lê Tẹt | Ngày: | Loại File: PPT | Số trang:25

Thêm vào BST

Báo xấu

60
lượt xem 10
download

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

Phát biểu: Nếu một công việc có thể thực hiện bằng một trong hai phương án lọai trừ lẫn nhau: 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. Khi đó công việc đó có m+n cách thực hiện Theo thuật ngữ của nguyên lí tập hợp : - Nếu A, B là các tập hợp không giao nhau thì |A  B| = |A| +|B|

Chủ đề:

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

Lưu

Nội dung Text: Chương III: Phép đếm

Chương III: Phép đếm Mục Lục :
Phát biểu: Nếu một công việc có thể thực hiện bằng một trong hai phương án lọai trừ lẫn nhau: 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. Khi đó công việc đó có m+n cách thực hiện
Theo thuật ngữ của nguyên lí tập hợp : - Nếu A, B là các tập hợp không giao nhau thì |A ∪ B| = |A| +|B|
Chứng minh
Ví Dụ Nguyên lý cộng LờVí i gidảụi :1: có thể ta TaChúng thựccầhi nệch nmọnộtm trong 2 việviên ột sinh c chọ n lựa UIT khác nhau: chọn một sinh viên toán năm 3, hoặc chọn toán năm thứ 3 hay năm thứ 4 đi dự một h ội ngh ị. một sinh viên toán năm 4. Để thực hiện công việc thứ Hỏi có bao nhiêu cách chọn lựa một sinh viên nhất ta có 100 cách, và để thực hiện công việc thứ 2 ta cónh85ưcách. thế biVếậtyrđằểngchcó ọn 100 một sinh viêntoán sinh viên họcyêu toántheo nămcầu cóứ100+85 tath 3 và 85= sinh viên toán học năm thứ tư ? 185 cách.
Ví dụ nguyên lý cộng Ví dụ 2: 1 thầy giáo có thể chọn người hẹn hò từ ba Lời gisách, danh ải: Rõ ràng danh việ1: sách gồọ c ch mn10 ườcó ngcô ẹnềhò i hchi từ trên u cao 3 danh tsách 1m65 , danhlàsách ồng5thcô ko đ2:có ời(n ếu đdc trình ộ thì caotôi đẳcũng ng trởđã lên danhrồsách ,làm i).áp3d:3ụng quy«đitắềcu ckiộệng cô có Hỏđi ượ n».ta baoc:có bao Có 10 nhiêu V+ậy5ch cách theo +ọ3=18 n ng ầcách thườyi hnghĩ ẹnchhò. ọn , còn các bạn nghĩ sao sao
II.Nguyên lý nhân Phát biểu: Giả sử công việc nào đó được chia thành k giai đọan thực hiện: Giai đọan 1: có n1 cách thực hiện Giai đọan 2: có n2 cách thực hiện …………. Giai đọan k: có nk cách thực hiện Khi đó, số cách thực hiện cả công việc là: n1.n2…nk
II.Nguyên lý nhân Nguyên lý nhân trên tập hợp: - 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 |
Chứng minh
Ví dụ Nguyên lý nhân Víờidgiụả4:đi L ừ đAếđnếCn có i. TừtA B có 3 con 2 giai đoạđ ường, n,A-> đi từ B và B đếC,n theo B-> C cóquy 2 con tắc đ ường nhân Hỏ ta .có : si ố mu ốnđđi con ừA ườtng đi đếtnừC ếnm A đcó Cấlà :n=2x3=6 y con đường?
Ví dụ Nguyên lý nhân LờiVí giảdi.ụTh 1:ủCác tục gh ghiếnhãn ngồi cho trong mộ t hếộgi ồtrm mt ộgh ườ2ng việscẽ: ghiđmượộtctrong 26 mg ghi nhãn ẫồumtựmvà ộtkm ếẫ ếptựlàvà tiu ghimm ộột tsố trong số nguyên 100nguyên dươdngươkhông ng. Quilớtnắchơ nhân n 100.choHth ỏiấsyốcó gh26ế x 100tố=i đa 2600cócách thể đkhác ược nhau để ghi ghi nhãn khácnhãnnhau cholàmbao ột gh ế ngồnhiêu? i. Do đó số ghế lớn nhất có thể được ghi nhãn khác nhau là 2600.
Ví dụ Nguyên lý nhân Lời giải. Một ánh xạ đi từ tập A gồm m phần tử vào mVí tậụp 5: ột d hợCó p B bao gồm nhiêu n phầnánh xạngđiứtng tử tươ ừm vớội tvitệậcp chhọợnplựgaồ mộm tử ầvào phầ n ph t trong n tử m củộat B tậcho p hợmpỗigphồm ần tửn cph ủaầA. tử ?đó, theo qui tắc nhân, có n.n. ... .n = n Do nm ánh xạ từ A vào B.
III.Nguyên lý bù trừ Phát biểu: Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc.
III.Nguyên lý bù trừ
Ví dụ Nguyên lý bù trừ Lời giải: GọVí i A dụ: là nh Trong ững hm ọcộtsinh lớp hngo ọc ạ ngữPháp. i ng tiế Anh Pháp. Có Gọ24 i B HS là nhhữọng c Tihếọng Pháp, c sinh học26 họcAnh. tiếng sinh học tiếng đó số15họhcọcsinh KhíAnh, sinhhọhcọccủtiaếlng ớp Anh là |Avà tiếng ∪ B|. Pháp. Theo Hỏi lớ nguyên lýpbù cótrbao ừ ta nhiêu có |A ∪ngB|=ười? |A|+|B| - |A ∩ B|= 24 + 26 -15 = 35