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 tập hợp (Bài toán đếm)
Nội dung trích xuất từ tài liệu:
Hai nguyên lý cơ bản Nguyên lý Nhân.1. Nguyên lý Cộng.2. Một số ứng dụng của nguyên lý Nhân, Cộng.3. 1 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 (Bài toán đếm) Hai nguyên lý cơ bản sau sẽ đề cập đến vấn đề đó: ◦ Nguyên lý Nhân. ◦ Nguyên lý Cộng. 2 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 n kỳ, khi đó N ( A1  A2  ....  An )   N ( Ai ) i 1 3V í 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 4V í 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 5 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 nhauntừng nđôi một. Khi đó: N (  Ai )   N ( Ai ) i 1 i 1 6 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) = 17 và N(B) = 13. Số cách chọn đại biểu dự hội nghị trong số các cán bộ của hai bộ môn chính là việc chọn một phần tử bất kỳ của tập AB. Ta có N(AB) = N(A) + N(B) = 30 7 Ví dụ: Một đề thi trắc nghiệm có thể được chọn từ một trong ba bộ đề thi độc lập tương ứng có 23, 17 và 29 đề. Có bao nhiêu cách chọn khác nhau? Giải: ◦ C1: Có 23 cách chọn đề thi từ danh sách thứ nhất, 17 cách từ danh sách thứ hai và 29 cách từ danh sách thứ 3. Vì vậy có 23 + 17 + 29 = 69 cách đề thi trắc nghiệm. ◦ C2: Ký hiệu ba bộ đề thi là A, B, C. Tương tự như ví dụ 2.1.1, ta có số cách chọn đề thi là N(ABC) = N(A) + N(B) + N(C) = 23 + 17 + 29 = 69 8 Ví dụ: ◦ Có bao nhiêu xâu nhị phân có độ dài bằng 8? ◦ Giải: Mỗi một trong 8 bít của xâu nhị phân có thể chọn bằng hai cách hoặc bằng 0 hoặc bằng 1. Bởi vậy, quy tắc nhân cho thấy có tổng cộng 28 = 256 xâu nhị phân khác nhau có độ dài bằng 8. ◦ Tương tự, ta có tất cả các dãy nhị phân có độ dài n là 2n. 9 Ví dụ: ◦ Có nhiều nhất bao nhiêu biển đăng ký xe máy trên 50 phân khối của thành phố Hà Nội nếu mỗi biển có nội dung ví dụ như 29 H3-3907 số 29 là ký hiệu dành cho Hà Nội, tiếp đó là một trong 26 chữ cái, sau chữ cái gồm số lớn hơn 0 và nhỏ 10, bốn số cuối bất kỳ. ◦ Giải:  Có tất cả 26 cách chọn chữ cái; 9 cách chọn cho chữ số tiếp theo. ...