Phần I: Tổ hợp

Hai quy tắc đếm cơ bản I. Quy tắc cộng Giả sử công việc A có thể tiến hành theo một trong các phương án A,.A…An. Mỗi phương án có số cách thực hiện theo thứ tự là x,x,…x.Khi dó số cách thực hiện công việc A được cho bởi quy tắc cộng S = x+x+……x= Phương pháp giải toán Muốn đếm số cách lựa chọn để thực hiện một công việc A bằng cách quy tắc cộng ta thực hiện các bước sau: Bước 1: phân tích xem có bao nhiêu phương án riêng biệt để tiến hành thực hiện công việc A Bước 2: đếm số cách lựa chọn x,x,…xtương ứng với từng phương án A,A…A. Bước 3: dùng quy tắc cộng ta tính được số cách lựa chọn để thực hiện công việc A là: S = x+ x+…+ x= Ví dụ 1: Có 10 quyển sách toán khác nhau, 8 quyển sách vât lý khác nhau và 6 quyển sách hóa học khác nhau, một học sinh được chọn một quyển hỏi có bao nhiêu cách chọn Giải Có 3 phương án Phương án 1: Chọn sách toán 10 cách chọn Phương án 2: chọn sách vật lý 8 cách chọn Phương án 3: chọn sách hóa học 6 cách chọn Vậy số cách chọn là S = 10 + 8 + 6 = 24 Ví dụ 2: Từ thành phố A đến thành phố B có 3 đường bộ và 2 đường thủy. Cần chọn một đường để đi từ A đến B. Hỏi có mấy cách chọn ?  Giải Để đi từ thành phố A đến thành phố B ta có 2 phương án : đường bộ hoặc đường thủy : Đường bộ : 3 đường có 3 cách chọn. Đường thủy : 2 đường có 2 cách chọn. Và 2 phương án này độc lập với nhau. Vậy theo qui tắc cộng ta có tất cả:  S= 3 + 2 = 5 cách chọn. Ví dụ 3: Một nhà hàng có 3 loại rượu, 4 loại bia, 5 loại nước ngọt. Một thực khách cần chọn đúng một loại thức uống. Hỏi có bao nhiêu cách chọn ? Giải Thực khách có 3 phương án chọn : Hoặc chọn rượu: 3 cách chọn Hoặc chọn bia: 4 cách chọn Hoặc chọn nước ngọt : 5 cách chọn Theo qui tắc cộng thực khách có tất cả : 3 + 4 + 5 = 9 cách chọn một loại thức uống. II. Quy tắc nhân Giả sử công việc A bao gồm n công đoạn A,A….A.Mổi công đoạn có số cách thực hiện theo thứ tự là x.x….x.khi đó số cách thực hiện công việc A được cho bởi quy tắc nhân S=x.x….x= Phương pháp giải toán Muốn đếm số cách lựa chọn để thực hiện công việc A bằng quy tắc nhân ta thực hiện các bước sau Bước 1 phân tích xem có bao nhiêu công đoạn lien tiếp cần phải tiến hành để thực hiện công việc A Bước 2 đềm số cách chọn x,x…..x tương ứng với từng công đoạn A,A………A Bước 3 dùng quy tắc nhân ta có số cách lựa chọn để thực hiện công việc A là S=x.x….x= Ví dụ 1: Một lớp có 30 học sinh cần cử một cán sự lớp gồm một lớp trưởng một lớp phó một thủ quỹ .Hỏi có bao nhiêu cách chọn biết rằng mỗi học sinh đều có thể làm không quá một nhiệm vụ trong ban cán sự Giải Ta chia việc chon ban cán sự thành 3 công đoạn liên tiếp Bước 1 chọn lớp trưởng 30 cách Bước 2 chọn lớp phó 29 cách Bước 3 chọn thủ quỹ 28 cách Vậy S = 30.29.28 = 24360 cách. Ví dụ 2: Từ Hà Nội đến Huế có 3 cách đi : máy bay, ô tô, tàu hỏa. Từ Huế đến Sài Gòn có 4 cách đi: máy bay, ô tô, tàu hỏa, tàu thủy. Hỏi có bao nhiêu cách đi Hà Nội - Huế - Sài Gòn ? Giải Ta có thể xem việc đi Hà Nội - Huế - Sài Gòn như một công việc tiến hành theo 2 giai đoạn liên tiếp nhau : Giai đoạn 1 : đi từ Hà Nội đến Huế : có 3 cách đi. Giai đoạn 2 : từ Huế đến Sài Gòn : ứng với mỗi cách đi ở giai đoạn 1 ta đều có 4 cách để hoàn thành giai đoạn 2. Vậy theo nguyên lí nhân có tất cả : 3.4 = 12 cách đi Hà Nội - Huế - Sài Gòn. Ví dụ 3: Có bao nhiêu số tự nhiên có 3 chữ số khác nhau có thể được tạo thành từ các chữ số 5, 6, 7, 8, 9 ? Giải Số cần lập có dạng: Số cách chọn: a1: 5 cách chọn a2 : 4 cách chọn a3 : 3 cách chọn Vậy có tất cả 3.4.5 = 60 cách chọn Hoán vị. Chỉnh hợp. Tổ hợp I. Hoán vị 1. Định nghĩa Cho tập hợp X gồm n phần tử khi sắp xếp n phần tử này theo một thứ tự ta được một hoán vị các phần tử của tập hợp X Cho một số nguyên dương n số cac hoán vị của một tập hợp có n phần tử là P= Hoán vị vòng: Cho tập A gồm n phần tử (n 1). Mỗi kết quả của sự sắp xếp thứ tự n phần tử của tập hợp A theo một vòng kép kín được gọi là một hoán vị vòng của n phần tử đó. Số hoán vị vòng của n phần tử là : Pn-1=(n-1) ! 2. Ví dụ Ví dụ 1: Có bao nhiêu cách sắp xếp 3 bạn A, B, C ngồi vào một bàn dài có 3 chỗ ngồi ? Giải Cần sắp xếp 3 bạn vào 3 chỗ vậy mỗi cách sắp là hoán vị của 3 phần tử, có tất cả: P3 = 3! = 1.2.3 = 6 cách sắp xếp Các hoán vị đó là : ABC, ACB, BAC, BCA, CAB, CBA. Ví dụ 2: Có bao nhiêu số có 4 chữ số đôi một khác nhau lập từ các số 2, 6, 7, 9 ? Giải Mỗi số được thành lập là một hoán vị của 4 phần tử. Vậy ta có tất cả là : P4 = 4 ! = 24 số. Vậy có tất cả 24 số được lập. Ví dụ 3: Có bao nhiêu đa giác nhận n điểm A, B, …, L làm đỉnh ?  Giải Ta có thể hoán vị vòng các đỉnh theo cả hai chiều theo 2n cách khác nhau mà đa giác vẫn không thay đổi nên số đa giác là : Ví dụ 4: Có bao nhiêu cách sắp xếp n đại biểu ngồi quanh một bàn tròn ? Giải Vị trí tương đối giữa các đại biểu hoàn toàn không đổi nếu ta hoán vị vòng họ theo một chiều nhất định ( chẳng hạn n hoán vị ABC…KL, BCA…LA, CD…LAB là như nhau ) nghĩa là trong các hoán vị vòng không có phần tử nào là cuối cùng hoặc phần tử thứ nhất. Vậy số cách sắp xếp là : II. Chỉnh hợp 1. Định nghĩa Cho tập hợp X cò n phần tử và cho số nguyên k với 1 khi lấy k phần tử của X và sắp xếp chúng theo thứ tự ta được một chỉnh hợp chập k của n phần tử của X Cho các số nguyên n và k với .Khi đó số các chỉnh hợp chập k của một tập hợp có n phần tử là Chú ý : & Chỉnh hợp lặp: Chỉnh hợp lập chập k của n phần tử là một nhóm có thứ tự gồm k phần tử đã cho, trong đó đó mỗi phần tử có thể có mặt 1, 2, 3, …, k lần trong nhóm tạo thành. Kí hiệu là số chỉnh hợp lặp chập k của n phần tử. 2. Ví dụ Ví dụ 1: Có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau lập từ các chữ số 1, 2, 3, ....,9 Giải Mỗi số tự nhiên có 5 chữ số khác nhau được lập bằng cách lấy 5 chữ số khác nhau từ chín chữ số đã cho và xếp theo một thứ tự nhất định. Mỗi số như vậy được coi là một chỉnh hợp chập 5 của 9. Vậy có tất cả : Ví dụ 2: Trong mặt phẳng cho 10 điểm phân biệt. Có bao nhiêu vectơ khác vectơ 0 có điểm đầu và điểm cuối thuộc tập điểm đã cho. Giải Mỗi vectơ là một chỉnh hợp 10 chập 2 của tập điểm đã cho. Với mỗi bạn người đó có 2 cách lựa chọn : mời hoặc không mời Kết quả người đó có 2n cách lựa chọn ( kể cả không mời người nào ). Ví dụ 3: Một người tổ chức buổi tiệc sinh nhật muốn mời một trong số n bạn đến chung vui. Hỏi có bao nhiêu cách lựa chọn? Vậy số cách chọn là : S = . Giải Với mỗi bạn người đó có 2 cách lựa chọn : mời hoặc không mời Kết quả người đó có 2n cách lựa chọn ( kể cả không mời người nào ). Ví dụ 4: Chúng ta muốn thiết lập ít nhất 18000 từ khóa khác nhau chỉ dùng 26 chữ cái tiếng Anh. Các từ khóa có chiều dài càng ngắn càng tố. Hỏi chúng ta cần dùng từ khóa có chiều dài nhất là bao nhiêu là đủ số lượng theo yêu cầu ? Giải Ta thấy rằng tổng số các từ có chiều dài n là số các chỉnh hợp lặp của 26 chữ cái, nghĩa là có 26n chữ cái khác nhau có chiều dài n. Do 261 + 262 + 263 = 18278. Nên chúng ta chỉ cần từ khoá có chiều dài không quá 3 kí tự là đủ số lượng theo yêu cầu. III. Tổ hợp Định nghĩa Cho tập hợp X có n phần tử vá cho số nguyên k với .Mỗi tập hợp con của X có k phần tử được gọi là một tở hợp chập k của n phần tử của X cho các số nguyên n và k với khi đó số các tổ hợp chập k của một tổ hợp có n phần tử là : Ta quy ước & Tổ hợp lặp: Cho tập hợp A có n phần tử, một tổ hợp chập k có lặp lại gọi là tổ hợp lặp của n phần tử đó là một nhóm không kể thứ tự gồm k vật trong đó mỗi vật có thể lặp lại nhiều lần. Ví dụ: abcd, aabc, aaaa,… là các tổ hợp chập 4 có lặp lại của tập gồm n phần tử a, b, c, d,…,l. Định lí về tổ hợp lặp: Có tất cả tổ hợp lặp chập k của n phần tử & Tổ hợp phức (hoán vị lặp): Tổng số cách để phân phối n đối tượng phân biệt vào k hộp H1, H2,....,Hk sao cho r1 đối tượng phân biệt vào hộp H1, r2 đối tượng phân biệt vào hộp H2, ......., rk đối tượng phân biệt vào hộp Hk. n = r1 + r2 +…. + rk 2.Ví dụ Ví dụ 1: Một tổ có 10 người gồm 6 nam và 4 nữ. Cần lập một đoàn đại biểu gồm 5 người. Hỏi Có bao nhiêu cách lập? Có bao nhiêu cách lập gồm 3 nam và 2 nữ Giải Mỗi đoàn đại biểu được lập là một tổ hợp chập 5 của 10. Do đó, số đoàn đại biểu được lập là : Chọn 3 người từ 6 người nam : cách Chọn 2 người từ 4 người nữ : cách Vậy theo quy tắc nhân có = 120 cách thành lập. Ví dụ 2: Với các mẫu tự của chữ LAP LAI có thể tạo ra bao nhiêu chữ khác nhau ( không cần có nghĩa ) ? Giải Mỗi chữ là một hoán vị của 6 mẫu tự gồm 2 mẫu tự L, 2 mẫu tự A, 1 mẫu tự B và 1 mẫu tự I. Vậy có tất cả : = 180 cách. Ví dụ 3: Để chia 17 người thành 4 nhóm: nhóm 5 người, nhóm 2 người, nhóm 7 người và nhóm 3 người có bao nhiêu cách chia? Giải Có tất cả : = 49008960 cách. Ví dụ 4: Có bao nhiêu nghiệm tự nhiên của phương trình Giải Để đếm số nghiệm tự nhiên của phương trình chúng ta xét sự phân phối của 17 giống vật giống nhau vào 5 hộp dán nhãn . Số vật trong hộp ri thể hiện giá trị của ri. Khi đó chúng ta thấy rằng mỗi sự phân phối tương ứng 1- 1 với nghiệm tự nhiên của phương trình đã cho. Như vậy phương trình có nghiệm tự nhiên Nguyên lý bù trừ 1.Định nghĩa 2.Ví dụ Ví dụ 1: Giải Ví dụ 2: Giải