Toán rời rạc-Chương 1: Các khái niệm cơ bản p3
Số trang: 0
Loại file: pdf
Dung lượng: 244.58 KB
Lượt xem: 9
Lượt tải: 0
Xem trước 2 trang đầu tiên của tài liệu này:
Thông tin tài liệu:
Hai nguyên lý cơ bản nghiên cứu các bài toán tổ hợp, một vấn đề rất quan trọng thường xuyên được quan tâm đến là số lượng các phần tử trong hợp tử
Nội dung trích xuất từ tài liệu:
Toán rời rạc-Chương 1: Các khái niệm cơ bản p3 TOÁN RỜI RẠC CHƯƠNG 1: KHÁI NIỆM CƠ BẢN Hai nguyên lý cơ bản Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com 1 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University NỘI DUNG 1. Nguyên lý Nhân. 2. Nguyên lý Cộng. 3. Một số ứng dụng của nguyên lý Nhân, Cộng. 2 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1. Khái niệm Nghiên cứu các bài toán tổ hợp, một vấn đề rất quan trọng thường xuyên được quan tâm đến là số lượng các phần tử trong tập hợp. Hai nguyên lý cơ bản sau sẽ đề cập đến vấn đề đó: Nguyên lý Nhân. Nguyên lý Cộng. 3 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 2. Nguyên lý Nhân (1/3) Khái niệm: Giả sử một công việc nào đó có thể tách thành k phân đoạn. Phân đoạn thứ i có thể thực hiện bằng ni cách sau khi phân đoạn 1,2,…, i-1 đã hoàn thành. Khi đó sẽ có n1n2 …nk cách khác nhau để thực hiện công việc đó. Nguyên lý: Cho A1,A2,…., An là các tập hữu hạn bất kỳ, khi đó n N ( A1 A2 .... An ) N ( Ai ) i 1 4 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 2. Nguyên lý Nhân (2/3) Ví dụ: Ký hiệu giảng đường của một trường đại học bắt đầu bằng một trong các chữ cái A, B, C, D, E, F và một số nguyên dương không vượt quá 50. Hỏi nhiều nhất có bao nhiêu giảng đường được ký hiệu khác nhau? Giải: C1: Thủ tục ghi ký hiệu cho một giảng đường gồm hai việc, gán một trong 6 chữ cái A, B, C, D, E, F và sau đó gán một trong 50 số nguyên dương 1, 2,…50. Nguyên lý nhân chỉ ra rằng có 6 x 50 = 300 cách khác nhau để ký hiệu cho một giảng đường. Như vậy nhiều nhất có thể có 300 giảng đường được ký hiệu khác nhau. C2: Nếu gọi tập chữ cái nêu trên là R và tập các số thứ tự cần đánh số là S, ta có là N(R) = 6, N(S) = 50. Như vậy mỗi ký hiệu giảng đường sẽ gồm 2 phần: phần chữ cái là một phần tử bất kỳ a R và phần số là một phần tử b S, tức là một phần tử (a,b) A x B - tích Đề-các của hai tập R và S. Ta có N(R x S) = N(R) x N(S) = 6 x 50 = 300 5 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 2. Nguyên lý Nhân (3/3) Ví dụ: Một sinh viên có 5 chiếc áo sơ mi khác mầu, 3 cái quần khác mầu, 2 đôi giầy khác kiểu. Nếu mỗi ngày sinh viên đó mặc một kiểu khác nhau, thì sau bao nhiêu ngày thì sinh viên đó sẽ phải lặp lại cách trang phục ngoài? Giải: C1: Các cách trang phục khác nhau khác nhau ở một trong ba thành phần áo sơ mi, quần và giầy. Để chọn áo có 5 cách, chọn quần có 3 cách và chọn giầy có 2 cách, như vậy có tất cả 5 x 3 x 2 = 30 cách. Nghĩa là tối đa sau 30 ngày sinh viên đó sẽ phải lặp lại cách trang phục của mình. C2: Biểu diễn tập A là tập áo sơ mi, tập Q là tập quần, tập G là tập giầy, khi đó một bộ trang phục gồm áo, quần và giầy là một phần tử (a, q, g) của tập tích Đề-các A x Q x G. Vậy tổng só cách để chọn trang phục ngoài của sinh viên là N(A X Q X G)=N(A) X N(Q)X N(G) = 5X 3X 2 = 30 6 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 3. Nguyên lý cộng (1/3) Khái niệm: Giả sử có k công việc không thể làm đồng thời. Công việc thứ i (i=1,2,…k) có thể làm bằng ni cách khác nhau. Khi đó sẽ có n1+n2+…+nk cách làm một trong k công việc đó. Nguyên lý cộng. Cho A1,A2,…., An là các tập hữu hạn, không giao nhau từng đôi một. Khi đó: n n N ( Ai ) N ( Ai ) i 1 i 1 7 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 3. Nguyên lý cộng (2/3) Ví dụ: Giả sử Bộ môn Toán có 17 cán bộ và Bộ môn Khoa học máy tính có 13 cán bộ (mỗi cán bộ chỉ biên chế ở một bộ môn!). Hỏi có bao nhiêu cách chọn một đại biểu đi dự hội nghị khoa học trong số các cán bộ của hai bộ môn trên? Giải: C1: Có 17 cách khác nhau để chọn một cán bộ của Bộ môn Toán (việc thứ nhất) và 13 cách khác nhau để chọn một cán bộ của Bộ môn Khoa học máy tính (việc thứ hai). Rõ ràng là hai công việc đó không thể tiến hành đồng thời. Theo nguyên lý cộng ta có 17 + 13 = 30 cách chọn vị đại biểu này. C2: Xem xét theo cách khác, nếu ta gọi A là tập các cán bộ Bộ môn Toán và B là tập các cán bộ Bộ môn Khoa học máy tính. Hai tập đó là hai tập rời nhau (không có phần tử chung) và N(A) ...
Nội dung trích xuất từ tài liệu:
Toán rời rạc-Chương 1: Các khái niệm cơ bản p3 TOÁN RỜI RẠC CHƯƠNG 1: KHÁI NIỆM CƠ BẢN Hai nguyên lý cơ bản Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com 1 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University NỘI DUNG 1. Nguyên lý Nhân. 2. Nguyên lý Cộng. 3. Một số ứng dụng của nguyên lý Nhân, Cộng. 2 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 1. Khái niệm Nghiên cứu các bài toán tổ hợp, một vấn đề rất quan trọng thường xuyên được quan tâm đến là số lượng các phần tử trong tập hợp. Hai nguyên lý cơ bản sau sẽ đề cập đến vấn đề đó: Nguyên lý Nhân. Nguyên lý Cộng. 3 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 2. Nguyên lý Nhân (1/3) Khái niệm: Giả sử một công việc nào đó có thể tách thành k phân đoạn. Phân đoạn thứ i có thể thực hiện bằng ni cách sau khi phân đoạn 1,2,…, i-1 đã hoàn thành. Khi đó sẽ có n1n2 …nk cách khác nhau để thực hiện công việc đó. Nguyên lý: Cho A1,A2,…., An là các tập hữu hạn bất kỳ, khi đó n N ( A1 A2 .... An ) N ( Ai ) i 1 4 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 2. Nguyên lý Nhân (2/3) Ví dụ: Ký hiệu giảng đường của một trường đại học bắt đầu bằng một trong các chữ cái A, B, C, D, E, F và một số nguyên dương không vượt quá 50. Hỏi nhiều nhất có bao nhiêu giảng đường được ký hiệu khác nhau? Giải: C1: Thủ tục ghi ký hiệu cho một giảng đường gồm hai việc, gán một trong 6 chữ cái A, B, C, D, E, F và sau đó gán một trong 50 số nguyên dương 1, 2,…50. Nguyên lý nhân chỉ ra rằng có 6 x 50 = 300 cách khác nhau để ký hiệu cho một giảng đường. Như vậy nhiều nhất có thể có 300 giảng đường được ký hiệu khác nhau. C2: Nếu gọi tập chữ cái nêu trên là R và tập các số thứ tự cần đánh số là S, ta có là N(R) = 6, N(S) = 50. Như vậy mỗi ký hiệu giảng đường sẽ gồm 2 phần: phần chữ cái là một phần tử bất kỳ a R và phần số là một phần tử b S, tức là một phần tử (a,b) A x B - tích Đề-các của hai tập R và S. Ta có N(R x S) = N(R) x N(S) = 6 x 50 = 300 5 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 2. Nguyên lý Nhân (3/3) Ví dụ: Một sinh viên có 5 chiếc áo sơ mi khác mầu, 3 cái quần khác mầu, 2 đôi giầy khác kiểu. Nếu mỗi ngày sinh viên đó mặc một kiểu khác nhau, thì sau bao nhiêu ngày thì sinh viên đó sẽ phải lặp lại cách trang phục ngoài? Giải: C1: Các cách trang phục khác nhau khác nhau ở một trong ba thành phần áo sơ mi, quần và giầy. Để chọn áo có 5 cách, chọn quần có 3 cách và chọn giầy có 2 cách, như vậy có tất cả 5 x 3 x 2 = 30 cách. Nghĩa là tối đa sau 30 ngày sinh viên đó sẽ phải lặp lại cách trang phục của mình. C2: Biểu diễn tập A là tập áo sơ mi, tập Q là tập quần, tập G là tập giầy, khi đó một bộ trang phục gồm áo, quần và giầy là một phần tử (a, q, g) của tập tích Đề-các A x Q x G. Vậy tổng só cách để chọn trang phục ngoài của sinh viên là N(A X Q X G)=N(A) X N(Q)X N(G) = 5X 3X 2 = 30 6 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 3. Nguyên lý cộng (1/3) Khái niệm: Giả sử có k công việc không thể làm đồng thời. Công việc thứ i (i=1,2,…k) có thể làm bằng ni cách khác nhau. Khi đó sẽ có n1+n2+…+nk cách làm một trong k công việc đó. Nguyên lý cộng. Cho A1,A2,…., An là các tập hữu hạn, không giao nhau từng đôi một. Khi đó: n n N ( Ai ) N ( Ai ) i 1 i 1 7 @Copyrights by Dr. Ngo Huu Phuc, Le Quy Don Technical University 3. Nguyên lý cộng (2/3) Ví dụ: Giả sử Bộ môn Toán có 17 cán bộ và Bộ môn Khoa học máy tính có 13 cán bộ (mỗi cán bộ chỉ biên chế ở một bộ môn!). Hỏi có bao nhiêu cách chọn một đại biểu đi dự hội nghị khoa học trong số các cán bộ của hai bộ môn trên? Giải: C1: Có 17 cách khác nhau để chọn một cán bộ của Bộ môn Toán (việc thứ nhất) và 13 cách khác nhau để chọn một cán bộ của Bộ môn Khoa học máy tính (việc thứ hai). Rõ ràng là hai công việc đó không thể tiến hành đồng thời. Theo nguyên lý cộng ta có 17 + 13 = 30 cách chọn vị đại biểu này. C2: Xem xét theo cách khác, nếu ta gọi A là tập các cán bộ Bộ môn Toán và B là tập các cán bộ Bộ môn Khoa học máy tính. Hai tập đó là hai tập rời nhau (không có phần tử chung) và N(A) ...
Tìm kiếm theo từ khóa liên quan:
hai nguyên lý cơ bản toán rời rạc phương pháp dạy học toán sổ tay toán học tài liệu học môn toánGợi ý tài liệu liên quan:
-
Đề thi kết thúc môn học Nhập môn Toán rời rạc năm 2020-2021 có đáp án - Trường ĐH Đồng Tháp
3 trang 348 14 0 -
Kiến thức tổng hợp về Toán rời rạc: Phần 1
151 trang 234 0 0 -
Giáo trình Toán rời rạc: Phần 1 - Nguyễn Gia Định
67 trang 224 0 0 -
Báo cáo thí nghiệm về thông tin số
12 trang 214 0 0 -
Giáo trình Toán rời rạc: Phần 1 - Đỗ Đức Giáo
238 trang 204 0 0 -
Giáo trình Toán rời rạc (Nghề: Công nghệ thông tin - Cao đẳng) - Trường Cao đẳng Cộng đồng Đồng Tháp
107 trang 135 0 0 -
Luận Văn: Ứng Dụng Phương Pháp Tọa Độ Giải Một Số Bài Toán Hình Học Không Gian Về Góc và Khoảng Cách
37 trang 102 0 0 -
Bài giảng Toán rời rạc: Chương 5 - Nguyễn Quỳnh Diệp
84 trang 77 0 0 -
Bài giảng Toán rời rạc: Chương 2 - ThS. Trần Quang Khải
27 trang 70 0 0 -
Giáo trình Toán rời rạc - TS. Võ Văn Tuấn Dũng
143 trang 68 0 0