Các phương pháp đếm và nguyên lý dirichlet

Click to edit Master title style 10/3/2014 ‹#› GVC, ThS. Võ Minh Đức, CĐSP Đăklăk Click to edit Master text styles Second level Third level Fourth level Fifth level Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level 10/3/2014 Võ Minh Đức, CĐSP Đăklăk ‹#› 10/3/2014 1 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk CÁC PHƯƠNG PHÁP ĐẾM VÀ NGUYÊN LÝ DIRICHLET Ch­ư¬ng II 10/3/2014 2 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢNII. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢNIII. SINH CÁC HOÁN VỊ VÀ TỔ HỢPIV. NGUYÊN LÝ DIRICHLET. V. HỆ THỨC TRUY HỒI   NỘI DUNG 10/3/2014 3 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN Nguyên lý cộng Nguyên lý nhân Nguyên lý bù trừ 10/3/2014 4 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN Nguyên lý cộng Giả sử có k công việc T1, T2, …, Tk . Các công việc này có thể làm bằng n1, n2, …, nk cách tương ứng và giả sử rằng không có hai việc nào có thể làm đồng thời. Khi đó số cách để làm một trong k công việc đó là: n1+ n2+ …+ nk 10/3/2014 5 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (2) Ví dụ 1: Một SV cần chọn một bài tập trong ba danh sách tương ứng có 23, 15 và 39 bài. Số cách chọn sẽ là: (?) 23+15+39 =77 cách. (theo nguyên lý cộng ) 10/3/2014 6 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (3) Ví dụ 2: Cho đoạn chương trình m:=0; For i:=1 to n1 do m:=m+1; For i:=1 to n2 do m:=m+1; … For i:=1 to nk do m:=m+1; {m = n1} {m = n1 + n2} m = n1 + n2 + . . . + nk (theo nguyên lý cộng ) Chương trình trên cho giá trị của m là bao nhiêu? 10/3/2014 7 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (4) Nguyên lý cộng: (phát biểu dưới dạng tập hợp như sau) Nếu A1, A2,…, An là các tập hợp đôi một rời nhau, khi đó số phần tử của hợp các tập hợp này bằng tổng các phần tử của các tập hợp đã cho. 10/3/2014 8 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (5) 2. Nguyên lý nhân Giả sử một công việc T nào đó được tách ra thành k công việc nhỏ hơn T1, T2, …, Tk. Nếu việc Ti có thể làm bằng ni cách sau khi các công việc T1, T2,…,Ti-1 đã làm được, thì để hoàn thành công việc T cần phải có n1.n2…nk c¸ch. 10/3/2014 9 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk CÁC VÍ DỤ Ví dụ 1: Để đánh biển số xe môtô người ta dùng một số có 4 chữ số, hỏi có bao nhiêu biển số xe được đánh? ĐÁP SỐ: 104 cách 10/3/2014 10 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk Ví dụ 2: Để ghi nhãn cho những chiếc ghế trong một giảng đường người ta dùng một chuỗi kí tự, kí tự đầu tiên là một chữ cái và các kí tự còn lại là các chữ số biểu diễn một số nguyên dương không vượt quá 100. Nhiều nhất có thể có bao nhiêu chiếc ghế được ghi nhãn? Giải: Có 26 cách chọn chữ cái, mỗi cách chọn lại có 100 cách chọn số. Vậy theo NLN có: 26.100= 2600 cách CÁC VÍ DỤ 10/3/2014 11 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk Ví dụ 3: Có bao nhiêu xâu nhị phân có độ dài n? Giải: Xâu nhị phân đó có dạng là: x1x2x3…xn,, trong đó xi là 0 hoặc 1. x1 có 2 cách chọn, x2 có 2 cách chọn, …, xn có 2 cách chọn. Theo nguyên lý nhân ta có: 2*2*2…*2 = 2n (n lần số 2). Vậy có 2n xâu nhị phân có độ dài n. CÁC VÍ DỤ 10/3/2014 12 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk Ví dụ 4: Giá trị của m bằng bao nhiêu sau khi đoạn chương trình sau đây được thực hiện? m:=0; For i1:=1 to n1 do For i2:=1 to n2 do . . . For ik-1:=1 to nk-1 do For ik:=1 to nk do m:=m+1; CÁC VÍ DỤ 10/3/2014 13 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (6) Nguyên lý nhân: Nếu A1, A2,…, Ak là các tập hợp hữu hạn, khi đó số phần tử của tập hợp tích Đề-Các (Descarts) của các tập hợp này bằng tích của số các phần tử của mọi tập hợp thành phần. Vậy theo quy tắc nhân ta có: |A1 x A2 x . . . x Ak| = |A1|* |A2|*…*|Ak| 10/3/2014 14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (7) 3. Nguyên lý bù trừ: Nếu A1, A2 là các tập hợp hữu hạn, khi đó số phần tử của hợp của 2 tập hợp A1, A2 sẽ là Vấn đề đặt ra: mở rộng cho k tập hợp? 10/3/2014 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (8) VÍ DỤ Trong một kỳ thi TN THPT, thống kê số học sinh đạt điểm 10 được như sau: tỉnh Đắk Lắk có 310 học sinh đạt điểm 10 môn Toán, 123 học sinh đạt điểm 10 môn Vật lý. Trong đó có 53 em vừa đạt điểm 10 môn Toán vừa đạt điểm 10 môn Vật Lý. Hỏi có bao nhiêu em đạt điểm 10? 10/3/2014 16 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk II. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN Chỉnh hợp lặp Chỉnh hợp không lặp Hoán vị Tổ hợp Tổ hợp lặp Hoán vị của tập hợp có các phần tử giống nhau Phân bổ các đồ vật vào trong hộp So sánh các cấu hình tổ hợp 10/3/2014 17 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2.1 Chỉnh hợp lặp Một cách sắp xếp có thứ tự k phần tử có thể lặp lại của một tập hợp có n phần tử được gọi là một chỉnh hợp lặp chập k từ tập n phần tử. Số chỉnh hợp lặp chặp k từ tập n phần tử là nk kí hiệu MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 10/3/2014 18 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2.1 Chỉnh hợp lặp VÍ DỤ: Sinh viên đọc và thảo luận các ví dụ trong sách (tr. 49) Thời gian : 10 phút. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 10/3/2014 19 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2.2 Chỉnh hợp không lặp CH: Nêu khái niệm chỉnh hợp không lặp? Đọc các ví dụ (tr. 50) Thời gian : 10 phút. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN Công thức tính chỉnh hợp không lặp chập k của n: 10/3/2014 20 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2.3 HOÁN VỊ Hoán vị của n phần tử khác nhau là một cách sắp xếp có thứ tự n phần tử đó. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN Nhận xét: Hoán vị và chỉnh hợp không lặp có gì tương đồng không? Hoán vị là chỉnh hợp không lặp có k=n. 10/3/2014 21 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2.3 HOÁN VỊ VÍ DỤ: Đọc sách (tr.51) Thời gian 5 phút MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 10/3/2014 22 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2.4 Tổ hợp lặp Một tổ hợp lặp chập k của một tập hợp gồm n phần tử là một cách chọn không có thứ tự k phần tử có thể lặp lại của tập đã cho. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 10/3/2014 23 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk THẢO LUẬN 1. Đọc ví dụ 2.5.2 và 2.5.3 trong TL1 (Tr.54-55) Thời gian: 7 phút 2. Kết luận? Số tổ hợp lặp chặp k từ tập n phần tử là: MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN Chú ý: k có thể lớn hơn n. 10/3/2014 24 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk Bài toán 1 Có các loại giấy bạc 5.000đ, 10.000đ, 20.000đ, 50.000đ, 100.000đ, 200.000đ, 500.000đ. Có bao nhiêu cách chọn 5 tờ giấy bạc từ thùng đựng tiền trên? biết rằng: 1. số tờ của mỗi loại không 1, x2>2, x3>3 thì có bao nhiêu nghiệm nguyên thỏa mãn điều kiện trên? Bài tập SV làm ở nhà? MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 10/3/2014 28 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2.5 Tổ hợp không lặp Đọc các ví dụ 2.4.1, 2.4.2 (tr. 52) CH: Nêu khái niệm tổ hợp không lặp? Thời gian : 10 phút. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN Công thức tính tổ hợp không lặp chập k của n: 10/3/2014 29 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2.6 Hoán vị của một tập hợp có các phần tử giống nhau Trong bài toán đếm, một số phần tử có thể giống nhau. Tránh đếm hơn một lần. Bài toán: Có thể nhận bao nhiêu xâu khác nhau bằng cách sắp xếp lại các chữ cái của từ SUCCESS. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 10/3/2014 30 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk Mệnh đề 1 Số hoán vị của n phần tử trong đó có n1 phần tử như nhau thuộc loại 1, n2 phần tử như nhau thuộc loại 2, ..., và nk phần tử như nhau thuộc loại k, bằng MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 10/3/2014 31 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2.7 Sự phân bố các đồ vật vào trong hộp Nhiệm vụ : Đọc sách TL1 trang 57 Ví dụ 2.7.1 Có bao nhiêu cách chia những xấp bài 5 quân cho mỗi một trong 4 người chơi từ một cỗ bài chuẩn 52 quân? MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 10/3/2014 32 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk Giải ví dụ 2.7.1 Số cách Người đầu tiên có thể nhận được 5 quân bài là Số cách Người thứ hai có thể được chia 5 quân bài bằng Số cách Người thứ ba có thể nhận được 5 quân bài bằng Và số cách người thứ tư nhận được 5 quân bài bằng theo NL nhân ta có: MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 10/3/2014 33 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk Mệnh đề 2 Số cách phân chia n đồ vật khác nhau vào trong k hộp khác nhau sao cho có ni vật được đặt vào trong hộp thứ i, với i = 1, 2, ..., k bằng MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 10/3/2014 34 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk Ví dụ Cho tập A gồm 5 chữ số hệ thập phân A={1,2,3,4,5} 3. Số các tập con 3 phần tử của 5 chữ số trên là . 4. Số các hoán vị của 5 chữ số trên là: 5! = 120. 10/3/2014 35 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk Ví dụ 5. Số các hoán vị khác nhau có thể có khi hoán vị các chữ cái trong từ XAXAM là .