Một số kỹ năng giải bài toán đếm

- MỘT SỐ KỸ NĂNG GIẢI BÀI TOÁN ĐẾM.
- 1 Một số kỹ năng giải bài toán đếm 3.
- 1.1.1 Quy tắc cộng, quy tắc nhân.
- 1.1.2 Hoán vị.
- 1.1.4 Tổ hợp.
- 1.2.1 Mô tả phần tử đếm.
- 1.3 Một số phương pháp giải nâng cao của bài toán đếm.
- 2 Một số dạng bài toán tổ hợp liên quan đến bài toán đếm 34 2.1 Nguyên lí bất biến.
- 2.1.1 Phát hiện đại lượng bất biến trong bài toán.
- 2.1.4 Một số bài toán nâng cao.
- 2.2.5 Một số bài toán minh họa.
- Trong các dạng bài toán tổ hợp thì bài toán đếm và một số dạng toán tổ hợp liên quan đến bài toán đếm là các dạng bài cơ bản và rất quan trọng.
- Việc giải các bài toán dạng này nhiều khi gặp rất nhiều khó khăn và rất dễ mắc phải những sai lầm vì đây là những dạng toán khó và chúng ta không nắm được các phương pháp, các kỹ năng giải.
- Liên quan đến bài toán đếm có hai vấn đề được quan tâm nghiên cứu..
- Một số kỹ năng giải các bài toán đếm;.
- Một số dạng bài toán tổ hợp liên quan đến bài toán đếm..
- Để giải được nhanh chóng và chính xác các bài toán đếm chúng ta cần phải nắm được các kỹ năng giải và việc giải thành thạo các bài toán đếm giúp ta rất nhiều trong việc giải các bài toán tổ hợp liên quan đến bài toán đếm..
- Hiện nay có nhiều sách tham khảo, tài liệu viết về các dạng toán tổ hợp nhưng một số kỹ năng giải bài toán đếm và đặc biệt là một số dạng bài toán tổ hợp liên quan đến bài toán đếm như nguyên lí bất biến, phân hoạch thì chưa được đề cập nhiều.
- Chính vì vậy, chúng tôi xin chọn đề tài cho luận văn của mình là: “Một số kỹ năng giải bài toán đếm”.
- Trong luận văn này ngoài việc trình bày một số kỹ năng giải bài toán đếm, chúng tôi còn đưa ra một số dạng toán tổ hợp liên quan đến bài toán đếm.
- Chương 1: Trình bày một số kỹ năng giải bài toán đếm như sử dụng các khái niện cơ bản, phép tương ứng 1- 1 và một số phương pháp giải nâng cao..
- Chương 2: Đưa ra một số dạng bài toán tổ hợp liên quan đến bài toán đếm như nguyên lí bất biến, phân hoạch và nguyên lí Dirichlet kèm theo các bài tập và lời giải chi tiết..
- Một số kỹ năng giải bài toán đếm.
- Bài toán đếm là một nội dung cơ bản không chỉ dành cho các bài toán thi đại học mà còn rất cần thiết khi giải các bài toán tổ hợp khó trong các kỳ thi học sinh giỏi.
- 1.1 Sử dụng các khái niệm cơ bản 1.1.1 Quy tắc cộng, quy tắc nhân.
- Quy tắc cộng..
- Nội dung quy tắc: Nếu có m 1 cách chọn đối tượng a 1 , m 2 cách chọn đối tượng a 2.
- m n cách chọn đối tượng a n , trong đó cách chọn đối tượng a i ( 1 ≤ i ≤ n ) không phụ thuộc vào bất kì cách chọn đối tượng a j ( 1 ≤ i ≤ n , i 6= j ) thì sẽ có.
- m k cách chọn đối tượng a 1 , hoặc a 2.
- Quy tắc nhân..
- Nội dung quy tắc: Cho n đối tượng a 1 , a 2.
- Nếu có m 1 cách chọn đối tượng a 1 và với mỗi cách chọn a 1 có m 2 cách chọn đối tượng a 2 , sau đó với mỗi cách chọn a 1 , a 2 có m 3 cách chọn đối tượng a 3.
- Cuối cùng với mỗi cách chọn a 1 , a 2 , a 3.
- a n−1 có m n cách chọn đối tượng a n .
- Như vậy sẽ có m 1 .m 2 ...m n−1 .m n cách chọn các đối tượng a 1 , rồi a 2 , rồi a 3.
- Sau đây ta xét một số bài toán minh họa:.
- Bài 1.Với sáu chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số gồm bốn chữ số khác nhau và trong mỗi số nhất thiết phải có chữ số 1..
- Trường hợp 1: a = 1 có 1 cách chọn a , có A 3 5 cách chọn các chữ số b, c, d..
- Có 4 cách chọn a ( vì a 6= 0.
- Nếu b = 1 thì có 1 cách chọn b và có A 2 4 cách chọn c, d;.
- Nếu c = 1 thì có 1 cách chọn c và có A 2 4 cách chọn b, d;.
- Nếu d = 1 thì có 1 cách chọn d và có A 2 4 cách chọn b, c;.
- Vậy theo quy tắc cộng có thể lập được 1.A 3 5 + 4.A 2 4 + 4.A 2 4 + 4.A 2 4 = 204 (số)..
- Có 3 cách đi từ A đến B và có 2 cách đi từ B đến D.
- Theo quy tắc nhân thì số cách chọn đường đi từ A đến D qua B là 3.2 = 6.
- Có 2 cách đi từ A đến C và có 4 cách đi từ C đến D.
- Theo quy tắc nhân thì số cách chọn đường đi từ A đến D qua C là 2.4 = 8.
- Vì cách chọn đường từ A sang D qua B và cách chọn đường từ A sang D qua C không phụ thuộc lẫn nhau, nên theo quy tắc cộng, ta có số con đường để đi từ A sang D là 6 + 8 = 14 (cách)..
- Từ các chữ số 1, 2, 3, 4, 5, 6, 7, 8, 9 có thể lập được bao nhiêu số gồm 4 chữ số khác nhau? Tìm tổng của tất cả các số này..
- Có 9 cách chọn a.
- Có 8 cách chọn b (b 6= a).
- Có 7 cách chọn c ( c 6= a , c 6= b.
- Có 6 cách chọn d ( d 6= a , d 6= b , d 6= c.
- Vậy theo quy tắc nhân thì số các số có thể lập được là 9.8.7.6 = 3024 (số)..
- Bởi vậy, nếu abcd có các chữ số không trùng nhau thì a 0 b 0 c 0 d 0 cũng có các chữ số không trùng nhau.
- 2 .9.8.7.6 cặp số abcd , a 0 b 0 c 0 d 0 gồm 4 chữ số không trùng nhau thuộc tập {1, 2, 3, 4, 5, 6, 7, 8, 9}.
- Các ô của bàn cờ có thể đặt theo quy tắc a ij (i= 1..8 ,j= 1..8 ) a 11 có 2 cách di chuyển..
- a 12 có 3 cách di chuyển..
- a 13 , a 14 , a 22 có 4 cách di chuyển..
- a 23 , a 24 có 6 cách di chuyển..
- a 33 , a 34 , a 44 có 8 cách di chuyển..
- Có bao nhiêu cách chọn ra 1 ô trắng và 1 ô đen?.
- Có bao cách chọn 1 ô trắng, 1 ô đen cùng nằm trên 1 hàng hay 1 cột?.
- Có 32 cách chọn ra một ô đen, 32 cách chọn một ô trắng.
- Vậy số cách chọn n 1 =32.32=1024 (cách)..
- Có 32 cách chọn một ô trắng.
- Vậy số cách chọn n 2 =32.8=256 (cách)..
- Có bao nhiêu cách chọn ra 2 quân domino có thể nối với nhau (số chấm ở một đầu của quân này bằng số chấm ở một đầu quân khác)..
- Theo quy tắc cộng thì số cách nối đươc là 252+42=294 (kể cả thứ tự)..
- Hoán vị không lặp.
- Mỗi cách sắp xếp n phần tử này theo một thứ tự nào đó (mỗi phần tử có mặt đúng một lần) được gọi là một hoán vị của n phần tử đã cho.
- Kí hiệu số hoán vị của n phần tử bằng P n.
- Sau đây ta xét một số bài oán minh họa:.
- Bài 7.Với năm chữ số 1, 2, 3, 4, 5 có thể lập được bao nhiêu số gồm năm chữ số khác nhau?.
- Mỗi số cần lập là một hoán vị của năm chữ số đã cho..
- Vậy số các số lập được bằng số hoán vị của năm phần tử bằng P 5 = 5.
- Có bao nhiêu cách xếp thứ tự cho báo cáo viên..
- Số cách xếp thứ tự cho báo cáo viên bằng 5.
- Vậy số cách là n 2 = 4.
- Vậy số cách sắp xếp B không báo cáo trước A là 1.
- Số cách xếp theo vị trí này là 5!5!..
- Hoán vị có lặp.
- Định nghĩa: Hoán vị trong đó mỗi phần tử xuất hiện ít nhất một lần được gọi là hoán vị có lặp..
- Số hoán vị lặp của n phần tử thuộc k loại, mà các phần tử loại i ( 1 ≤ i ≤ k ) xuất hiện n i lần được kí hiệu là P (n 1 , n 2.
- Với các chữ số 1, 2, 3, 4, 5, 6 có thể lập được bao nhiêu số gồm chín chữ số, trong đó mỗi chữ số 1, 2, 3, 4 xuất hiện đúng một lần, chữ số 5 xuất hiện đúng hai lần và chữ số 6 xuất hiện đúng ba lần..
- Xét một số tùy ý x = 154626356 và kí hiệu các vị trí của x một cách hình thức, ta có x = a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 .
- Khi đó, mỗi số x tương ứng với một hoán vị lặp của chín phần tử a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 , a 8 , a 9.
- Số các hoán vị khác nhau của chín phần tử a i ( 1 ≤ i ≤ 9 ) là 9!.
- song do a 2 = a 8 = 5 nên khi đổi chỗ a 2 và a 8 cho nhau thì hoán vị x = a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 vẫn chỉ cho ta số x.
- Như vậy, khi thực hiện 2! hoán vị a 2 , a 8 và 3! hoán vị a 4 , a 6 , a 9 , ta chỉ được một số cần tìm x.
- Vậy số các số có thể lập được là S = 9!.
- Với sáu chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số chia hết cho 5 gồm 11 chữ số, trong đó chữ số 1 có mặt 4 lần, chữ số 2 có mặt 3 lần, chữ số 3 có mặt 2 lần chữ số 4 có mặt 1 lần và tổng số lần xuất hiện của chữ số 0 và chữ số 5 là 1..
- Để số cần lập x = a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 a 11 chia hết cho 5, thì x phải tận cùng bằng chữ số 0 hoặc chữ số 5..
- Vì tổng số lần xuất hiện trong x của 0 và 5 bằng 1 nên nếu x tận cùng bằng 0 thì 5 không có mặt và ngược lại nếu x tận cùng bằng 5 thì chữ số 0 không xuất hiện.
- Bởi vậy a i ( 1 ≤ i ≤ 10 ) chỉ có thể là một trong những chữ số 1, 2, 3, 4.
- Bởi vậy số khả năng lập phần đầu độ dài 10 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 của x bằng số hoán vị lặp của 10 phần tử thuộc 4 loại chữ số: 1, 2, 3, 4 với 1 xuất hiện 4 lần, 2 xuất hiện 3 lần, 3 xuất hiện 2 lần và 4 xuất hiện 1 lần sẽ bằng P (1, 2, 3, 4.
- Ngoài ra a 11 lại có thể nhận 0 hoặc 5 nên có thể lập được.
- 2.P (1, 2, 3, 4.
- Vị trí ban đầu có thể là phụ âm hoặc nguyên âm đối với mỗi hoán vị của phụ âm.
- Suy ra số cách xếp: n = 2.4!.
- [3 ] Phạm Minh Phương, Một số chuyên đề toán tổ hợp, Nhà xuất bản Giáo dục Việt Nam, 2010.