Bài giảng Chương II: Các phương pháp đếm và nguyên lý Dirichlet (Phần 1) - GVC ThS. Võ Minh Đức
lượt xem 70
download
Bài giảng Chương II: Các phương pháp đếm và nguyên lý Dirichlet (Phần 1) do GVC ThS. Võ Minh Đức biên soạn trình bày về: các nguyên lý đếm cơ bản và một số bài toán đếm cơ bản. Với các bạn chuyên ngành Toán học thì đây là một tài liệu hữu ích.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Chương II: Các phương pháp đếm và nguyên lý Dirichlet (Phần 1) - GVC ThS. Võ Minh Đức
- Ch¬ng II c ¸c ph¬ng ph¸p ®Õm vµ ng uyªn lý diric hle t 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 1
- NỘI DUNG I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN II. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN III. SINH CÁC HOÁN VỊ VÀ TỔ HỢP 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2
- I. 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ý bù trừ 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 3
- I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN 1.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/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 4
- 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/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 5
- I. CÁC NGUYÊN LÝ ĐẾM CƠ BẢN (3) Ví dụ 2: Cho đoạn chương trình m:=0; {m = n1} For i:=1 to n1 do m:=m+1; For i:=1 to n2 do m:=m+1; {m = n1 + n2} … For i:=1 to nk do m:=m+1; Chương trình trên cho giá trị của m là bao nhiêu? m = n1 + n2 + . . . + nk (theo nguyên lý cộng ) 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 6
- 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. | A1 ∪ A2 ∪ ... ∪ An | = | A1 | + | A2 | + ...+ | An | 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 7
- 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/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 8
- 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/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 9
- CÁC VÍ DỤ 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 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 10
- CÁC VÍ DỤ 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. 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 11
- CÁC VÍ DỤ 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; GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 10/1/14 12
- 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/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 13
- 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à| A1 � A2 | = | A1 | + | A2 | − | A1 � A2 | Vấn đề đặt ra: mở rộng cho k tập hợp? 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 14
- 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/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk
- II. MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 1. Chỉnh hợp lặp 2. Chỉnh hợp không lặp 3. Hoán vị 4. Tổ hợp 5. Tổ hợp lặp 6. Hoán vị của tập hợp có các phần tử giống nhau 7. Phân bổ các đồ vật vào trong hộp 8. So sánh các cấu hình tổ hợp 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 16
- 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 MỘT tập hợp có n phần tử được gọi là SỐ một chỉnh hợp lặp chập k từ tập BÀI n phần tử. TOÁN •) Số chỉnh hợp lặp chặp k từ Đ ẾM CƠ tập n phần tử là nk kí hiệu A k n B ẢN 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 17
- 2.1 Chỉnh hợp lặp VÍ DỤ: Sinh viên đọc và thảo luận các ví MỘT dụ trong sách (tr. 49) SỐ BÀI Thời gian : 10 phút. TOÁN Đ ẾM CƠ B ẢN 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 18
- 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? MỘT Đọc các ví dụ (tr. 50) SỐ BÀI TOÁN Thời gian : 10 phút. Công thức tính chỉnh hợp không lặp chập k của n: Đ ẾM n! CƠ P = n k B ẢN ( n −k )! 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 19
- 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Ố Nhận xét: Hoán vị và chỉnh hợp BÀI không lặp có gì tương đồng không? TOÁN Đ ẾM Hoán vị là chỉnh hợp không lặp có CƠ k=n. B ẢN 10/1/14 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài Giảng Giải tích II: Phần 1 - Bùi Xuân Diệu
63 p | 3312 | 395
-
Bài Giảng Giải tích II: Phần 2 - Bùi Xuân Diệu
52 p | 1464 | 339
-
GIÁO TRÌNH VỀ PHÂN TÍCH MÔI TRƯỜNG - PHẦN 2- CHƯƠNG 2
37 p | 460 | 198
-
Chương II: Mô hình hồi quy hai biến - Trình bày: Nguyễn Duy Tâm
19 p | 731 | 167
-
Bài giảng môn Vi sinh thực phẩm
105 p | 292 | 84
-
bài giảng phương pháp tính cho sinh viên IT - 1
10 p | 334 | 83
-
Bài giảng chế biến khí : Quá trình hydro hóa - đề hydro hóa part 1
5 p | 169 | 53
-
Bài giảng Chương II: Các phương pháp đếm và nguyên lý Dirichlet (Phần 2) - GVC ThS. Võ Minh Đức
12 p | 335 | 53
-
Bài giảng Cơ lưu chất: Chương 4 - TS. Lê Thị Hồng Hiếu
62 p | 327 | 48
-
Toán cao cấp C2 - Chương II: Không gian vector
99 p | 508 | 46
-
Bài giảng Vật lý II (Phần 3: Vật lý lượng tử): Chương 8 - TS. TS. Ngô Văn Thanh
32 p | 104 | 14
-
Bài giảng Vật lý đại cương A2 - Chương II: Dao động - Sóng
102 p | 97 | 8
-
Vận dụng các phương pháp giảng dạy chủ động vào việc tổ chức dạy học chương “cảm ứng điện từ” môn Vật lý II ở các trường đại học kỹ thuật
9 p | 64 | 7
-
Bài giảng Toán C1: Chương 3 - ThS. Huỳnh Văn Kha
51 p | 65 | 7
-
Bài giảng Giải tích 2: Chương 3 - Hoàng Đức Thắng
57 p | 62 | 5
-
Bài giảng Cơ học lý thuyết (Phần 3): Chương 14
13 p | 8 | 3
-
Bài giảng Giải tích II: Chương 1 - Ứng dụng phép tính vi phân trong hình học
106 p | 6 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn