Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 1 - Nguyễn Anh Thi

Đăng ngày | Thể loại: | Lần tải: 0 | Lần xem: 0 | Page: 40 | FileSize: M | File type: PDF
of x

Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 1 - Nguyễn Anh Thi. Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 1 Tổ hợp cơ bản do Nguyễn Anh Thi biên soạn với các nội dung chính như: Nguyên lý đếm cơ bản, tổ hợp, tổ hợp lặp, khai triển luỹ thừa của đa thức,.... Cũng như những tài liệu khác được bạn đọc chia sẽ hoặc do tìm kiếm lại và chia sẽ lại cho các bạn với mục đích học tập , chúng tôi không thu phí từ thành viên ,nếu phát hiện tài liệu phi phạm bản quyền hoặc vi phạm pháp luật xin thông báo cho website ,Ngoài tài liệu này, bạn có thể download Tải tài liệu luận văn,bài tập phục vụ tham khảo Có tài liệu download mất font không xem được, nguyên nhân máy tính bạn không hỗ trợ font củ, bạn download các font .vntime củ về cài sẽ xem được.

https://tailieumienphi.vn/doc/bai-giang-toan-hoc-to-hop-va-cau-truc-roi-rac-chuong-1-nguyen-anh-thi-y1obuq.html

Nội dung


Bài giảng Toán học tổ hợp và Cấu trúc rời rạc

Đại học Khoa học Tự nhiên, Tp HCM

2016

Bài giảng Toán học tổ hợp và Cấu trúc rời rạc

2016

1/40

Nội dung chương 1

Nội dung
Chương 1.

Tổ hợp cơ bản

1. Nguyên lý đếm cơ bản
2. Tổ hợp
3. Tổ hợp lặp
4. Khai triển lũy thừa của đa thức

Bài giảng Toán học tổ hợp và Cấu trúc rời rạc

2016

2/40

Các nguyên lý đếm cơ bản

Nội dung

Các nguyên lý đếm cơ bản
1

Nguyên lý cộng

2

Nguyên lý nhân

3

Nguyên lý Derichlet

Bài giảng Toán học tổ hợp và Cấu trúc rời rạc

2016

3/40

Các nguyên lý đếm cơ bản

Nguyên lý cộng

Nguyên lý cộng
Giả sử ta phải thực hiện một công việc bằng cách chọn một trong k sự
chọn lựa các phương pháp khác nhau T1 , T2 , ..., Tk . Để thực hiện Ti
(1 ≤ i ≤ k) ta có ni cách. Vậy ta số cách thực hiện công việc trên là
n1 + n2 + · · · + nk .
Ví dụ. Một sinh viên có thể chọn một đề tài từ một trong 3 danh sách
các đề tài. Số đề tài trong các danh sách đề tài lần lượt là 23, 15, 19.
Hỏi sinh viên có bao nhiêu cách chọn một đề tài?
Đáp án. 23 + 15 + 19 = 57 cách.
Nhận xét. Quy tắc cộng có thể phát biểu dưới dạng của ngôn ngữ tập
hợp: Nếu A1 , A2 , . . . , Ak là các tập hợp đôi một rời nhau, khi đó
|A1 ∪ A2 ∪ . . . ∪ Ak | = |A1 | + |A2 | + . . . + |Ak |.
Bài giảng Toán học tổ hợp và Cấu trúc rời rạc

2016

4/40

Các nguyên lý đếm cơ bản

Nguyên lý nhân

Nguyên lý nhân
Giả sử một thủ tục bao gồm k công việc kế tiếp nhau T1 , T2 , . . . , Tk .
Nếu công việc T1 có thể được thực hiện theo n1 cách, và sau khi chọn
cách thực hiện cho T1 ta có n2 cách thực hiện T2 , v.v. . . cho đến cuối
cùng, sau khi chọn cách thực hiện các công việc T1 , T2 , ..., Tk−1 ta có nk
cách thực hiện Tk . Vậy ta có cách để thực hiện thủ tục này là:
n1 × n2 × ... × nk
Ví dụ.

Hỏi có nhiêu cách đi từ A đến C?
Đáp án. 3 × 2 = 6 cách.
Bài giảng Toán học tổ hợp và Cấu trúc rời rạc

2016

5/40

1116932

Tài liệu liên quan


Xem thêm