Tài liệu MỘT SỐ DẠNG TOÁN TỔ HỢP

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------ PHÙNG THẾ TÚ MỘT SỐ DẠNG TOÁN TỔ HỢP LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – Năm 2015 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------ PHÙNG THẾ TÚ MỘT SỐ DẠNG TOÁN TỔ HỢP Chuyên ngành: Phương pháp toán sơ cấp Mã số: 60.46.01.13 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Nguyễn Vũ Lương Hà Nội – Năm 2015 MỤC LỤC LỜI NÓI ĐẦU ……………………………………………………………… 3 Chương 1. Một số kiến thức cơ bản ……………………………………….. 5 1.1. Một số quy tắc cơ bản của phép đếm ………………………………. 5 1.2. Nguyên lý Dirichlet ………………………………………………… 10 1.3. Hoán vị ……………………………………………………………... 12 1.4. Chỉnh hợp …………………………………………………………... 17 1.5. Tổ hợp ……………………………………………………………… 20 1.6. Nhị thức Newton …………………………………………………… 24 Chương 2. Một số cách tiếp cận tới bài toán tổ hợp ……………………... 29 2.1. Sử dụng phương pháp liệt kê ………………………………………. 29 2.2. Đếm các phần tử của phần bù ……………………………………… 34 2.3. Sử dụng nguyên lý bao gồm và loại trừ ……………………………. 36 2.4. Sử dụng cách xây dựng phần tử đếm ………………………………. 44 2.5. Sử dụng các công thức tổ hợp …………………………………….... 45 2.6. Sử dụng nguyên lý phân phối các đồ vật vào hộp …………………. 48 2.7. Sử dụng công thức truy hồi ………………………………………… 52 2.8. Sử dụng phương pháp đánh số ……………………………………... 54 2.9. Phương pháp xây dựng song ánh …………………………………... 57 2.10. Sử dụng phương pháp đếm bằng hai cách ………………………... 61 Chương 3. Kỹ năng giải toán bằng phương pháp bất biến ……………... 66 3.1. Một số bài toán mở đầu …………………………………………….. 66 3.2. Tìm đại lượng không thay đổi sau mỗi phép biến đổi ……………... 71 3.3. Tìm tính chất của một đại lượng không thay đổi sau các phép biến đổi …………………………………………………………………… 73 3.4. Nguyên lý bất biến ………………………………………………... 74 3.5. Một số bài tập vận dụng ………………………………………....... 80 1 KẾT LUẬN ………………………………………………………………..... 88 Tài liệu tham khảo …………………………………………………………. 89 2 LỜI NÓI ĐẦU Toán tổ hợp – là một ngành toán học nghiên cứu các tổ hợp, hoán vị của các phần tử. Trong một thời gian dài, mảng khoa học này nằm ngoài hướng phát triển cơ bản của toán học và các ứng dụng của nó. Trong thời gian khoảng hai thế kỷ rưỡi, ngành giải tích đã đóng vai trò chủ yếu trong việc nghiên cứu bản chất tự nhiên. Hiện trạng này đã thay đổi sau khi các máy tính và máy tính cá nhân ra đời. Nhờ chúng người ta có thể thực hiện việc sắp xếp, phân loại mà trước đây cần hàng trăm đến hàng ngàn năm. Ở thời buổi sơ khai của toán học rời rạc, vai trò của lĩnh vực cổ xưa nhất của toán học rời rạc là toán học tổ hợp cũng đã được thay đổi. Từ lĩnh vực mà phần lớn chỉ những người biên soạn những bài toán thú vị quan tâm đến và phát hiện ra những ứng dụng cơ bản trong việc mã hóa và giải mã các văn tự cổ, nó đã được chuyển thành lĩnh vực nằm trong trục đường chính của sự phát triển khoa học. Ở nước ta hiện nay, chương trình giảng dạy toán tổ hợp, lý thuyết xác suất và thống kê đã bắt đầu từ chương trình toán học phổ thông. Trước hết cần khẳng định rằng hướng này của Bộ Giáo dục và Đào tạo đòi hỏi phát triển các kiểu tư duy chuyên biệt về tổ hợp và xác suất thống kê, vốn rất cần thiết đối với thế hệ hiện tại. Bởi thế, trong nhiều kì thi tuyển sinh vào đại học, thi học sinh giỏi, các bài toán tổ hợp cũng hay được đề cập và thường thuộc loại rất khó. Bằng cái nhìn tổng quan, luận văn này cũng đã nêu ra một số ví dụ điển hình trong các kì thi tuyển sinh vào đại học, thi học sinh giỏi thời gian qua. Cụ thể, luận văn được chia thành các chương: Chương 1. Một số kiến thức cơ bản. Chương này trình bày các kiến thức cơ bản trong tổ hợp gồm: Các quy tắc đếm cơ bản, hoán vị, chỉnh hợp, tổ hợp và nhị thức Newton. Ngoài ra, nguyên lý Dirichlet được đề cập tới như một công cụ đắc lực trong việc giải quyết các bài toán tổ hợp ở chương sau. 3 Chương 2. Một số cách tiếp cận tới bài toán tổ hợp. Chương này ta sẽ tiếp cận tới bài toán tổ hợp nhờ một số phương pháp cơ bản như: Phương pháp liệt kê, phương pháp đếm các phần tử của phần bù, sử dụng nguyên lý bao gồm và loại trừ, sử dụng các công thức tổ hợp, sử dụng nguyên lý phân phối các đồ vật vào hộp, sử dụng công thức truy hồi, phương pháp đánh số, phương pháp xây dựng song ánh và phương pháp đếm bằng hai cách. Chương 3. Kỹ năng giải toán bằng phương pháp bất biến. Chương này trình bày ba bài toán gồm: Bài toán về tính chất hữu hạn hoặc vô hạn của dãy lặp, bài toán về tính chất tuần hoàn của dãy lặp, bài toán về sự tồn tại của dãy lặp mà trạng thái cuối cùng thỏa mãn một số tính chất cho trước. Ngoài ra, rèn luyện kỹ năng phát hiện ra các đại lượng, tính chất của một đại lượng không đổi sau các phép biến đổi. Cuối cùng, trình bày nguyên lý bất biến và một số bài tập vận dụng. Để hoàn thành được luận văn này, trước nhất tôi xin được gửi lời cảm ơn sâu sắc tới PGS. TS Nguyễn Vũ Lương đã dành thời gian hướng dẫn, đánh giá, chỉ bảo, tận tình giúp đỡ trong quá trình xây dựng đề tài cũng như hoàn thiện khóa luận. Qua đây tôi cũng xin được gửi lời cảm ơn chân thành các thầy cô đã đọc, kiểm tra, đánh giá và cho những ý kiến quý báu để luận văn được đầy đủ hơn, phong phú hơn. Cũng xin được gửi lời cảm ơn tới Ban giám hiệu, phòng sau Đại học, khoa Toán-Cơ-Tin học trường Đại học Khoa học Tự nhiên đã tạo điều kiện thuận lợi trong suốt quá trình học tập tại trường. Tuy đã có nhiều cố gắng nhưng do thời gian và khả năng có hạn nên các vấn đề trong khóa luận vẫn chưa được trình bày sâu sắc và không thể tránh khỏi có những sai sót trong cách trình bày. Mong được sự góp ý xây dựng của thầy cô và các bạn. Tôi xin chân thành cảm ơn! Hà nội, ngày 15 tháng 01 năm 2015 Học viên Phùng Thế Tú 4 Chương 1 Một số kiến thức cơ bản 1.1. Một số quy tắc cơ bản của phép đếm Phép đếm có vai trò rất quan trọng trong đời sống cũng như trong khoa học. Trong đời sống, hàng ngày ta thường xuyên phải đếm các đối tượng nào đó và vì thế phép đếm dường như quá quen thuộc và không có gì phải bàn đến. Tuy nhiên, trong các kì thi đại học và thi học sinh giỏi, bài toán đếm đã gây ra không ít khó khăn cho các thí sinh. Trong mục này, chúng ta sẽ trình bày các quy tắc đếm cơ bản, nhờ đó có thể tính chính xác và nhanh chóng số phần tử của một tập hợp mà không cần đếm trực tiếp bằng cách liệt kệ. 1.1.1. Quy tắc cộng Nếu A1, A2 ,..., A k là các tập hợp hữu hạn đôi một rời nhau, tức là Ai  Aj   nếu i  j . Khi đó A1  A2  ...  Ak  A1  A2  ...  Ak , (1.1) với Ai là số phần tử của tập hợp Ai , i  1, 2, 3, ..., k . 1.1.2. Quy tắc nhân Nếu A1, A2 ,..., A k là các tập hợp hữu hạn và A1  A2  ...  A k là tích Descartes của các tập đó thì A1  A2  ...  Ak  A1 . A2 ... Ak . (1.2) Quy tắc cộng và quy tắc nhân cũng thường được phát biểu dưới dạng tương ứng dưới đây: Quy tắc cộng: Giả sử một công việc nào đó có thể thực hiện theo một trong k phương án A1, A2 ,..., Ak . Phương án Ai có ni cách thực hiện i     1, 2, 3, , k  . Khi đó công việc có thể thực hiện theo n1   n 2   .  n k cách. 5 Quy tắc nhân: Giả sử một công việc nào đó bao gồm k công đoạn A1, A2 ,..., Ak . Nếu công đoạn A1 có thể làm theo n 1 cách. Với mỗi i  2 và với mỗi cách thực hiện các công đoạn A1, A2 ,..., Ai1 thì công đoạn Ai có thể thực hiện theo ni cách. Khi đó công việc có thể thực hiện theo n 1 .n 2  n k cách. 1.1.3. Quy tắc bù trừ Cho X là tập hữu hạn và A  X . Gọi A  X \ A . Khi đó, ta có A  X A. (1.3) 1.1.4. Số phần tử của hợp hai hoặc ba tập hợp hữu hạn bất kì Định lí 1.1.1. (Công thức tính số phần tử của hợp hai tập hợp bất kì) Cho A và B là hai tập hợp hữu hạn bất kì. Khi đó, ta có AB  A  B  AB . (1.4) Chứng minh Ta có B và A \ B là hai tập hợp không giao nhau và A  B  B  A \ B  nên AB  B  A\B . Mặt khác A  B và A \ B  (1.5) là hai tập hợp không giao nhau và A  A  B   A \ B  nên A  A  B  A \ B , do đó: A\B  A  AB . (1.6) Thay (1.6) vào (1.5) ta được (1.4). Định lí 1.1.2. (Công thức tính số phần tử của hợp ba tập hợp bất kì) Cho A, B ,C là ba tập hợp hữu hạn bất kì. Khi đó, ta có A  B  C  A  B  C  A  B  B  C  C  A  A  B  C .(1.7) Chứng minh Theo định lí 1.1.1 ta có A  B  C  A  B C   A  B C  A  B C  . (1.8) 6 Mặt khác cũng theo định lí 1.1.1 B C  B  C  B C (1.9) và A  B  C   A  B   A  C   A  B  A  C  A  B   A  C   A  B  A C  A  B C . (1.10) Thay (1.9) và (1.10) vào (1.8) ta được công thức (1.7). 1.1.5. Ví dụ áp dụng một số quy tắc đếm cơ bản Ví dụ 1.1.1. Từ ba chữ số 2, 3, 4 có thể tạo ra bao nhiêu số tự nhiên gồm năm chữ số, trong đó có đủ cả ba chữ số nói trên? Lời giải Gọi số cần tìm có dạng a1a 2a 3a 4a 5 . Bởi số tạo thành phải có đủ cả ba chữ số 2, 3, 4 nên ta xét các trường hợp sau: Trường hợp 1: Số tạo thành gồm ba chữ số 2, một chữ số 3 và một chữ số 4. Ta xếp chữ số 4 có 5 cách chọn một trong các ví trí a 1, a 2 , a 3 , a 4 hoặc a 5 . Xếp chữ số 3 vào một trong bốn vị trí còn lại có 4 cách. Ba vị trí còn lại xếp ba chữ số 2 có 1 cách. Theo quy tắc nhân, ta có 5.4.1 = 20 số. Trường hợp 2: Số tạo thành gồm ba chữ số 4, một chữ số 2 và một chữ số 3. Tương tự trường hợp 1 có 20 số. Trường hợp 3: Số tạo thành gồm ba chữ số 3, một chữ số 2 và một chữ số 4. Tương tự, ta có 20 số. Trường hợp 4: Số tạo thành gồm hai chữ số 2, hai chữ số 3 và một chữ số 4. Chọn một trong năm vị trí để xếp chữ số 4 có 5 cách. Lấy ra hai vị trí từ bốn vị trí còn lại và xếp hai chữ số 2 có 6 cách. Hai chữ số 3 xếp vào hai vị trí còn lại có 1 cách. Theo quy tắc nhân, ta có 5.6.1 = 30 số. Trường hợp 5: Số tạo thành gồm hai chữ số 2, hai chữ số 4 và một chữ số 3. Tương tự trường hợp 4 có 30 số. Trường hợp 6: Số tạo thành gồm hai chữ số 3, hai chữ số 4 và một chữ số 2. Tương tự, ta có 30 số. 7 Vậy theo quy tắc cộng có tất cả 20 + 20 + 20 +30 + 30 +30 = 150 số. Ví dụ 1.1.2. (Đề thi tuyển sinh ĐHQG TP HCM – 1999) Một bàn dài có 2 dãy ghế đối diện nhau, mỗi dãy 6 ghế. Người ta muốn xếp chỗ ngồi cho 6 học sinh trường A và 6 học sinh trường B vào bàn nói trên. Hỏi có bao nhiêu cách xếp chỗ ngồi trong các trường hợp sau: (i) Bất kì hai học sinh nào ngồi cạnh nhau hoặc đối diện nhau thì khác trường; (ii) Bất kì hai học sinh nào ngồi đối diện nhau thì khác trường. Lời giải Đánh số các ghế theo hình vẽ (i) Theo yêu cầu của bài toán, ta có số cách chọn như sau: Ghế Số cách xếp chỗ ngồi 1 2 3 4 5 6 7 8 9 10 11 12 12 6 5 5 4 4 3 3 2 2 1 1 Theo quy tắc nhân, ta có 12.6.5.5.4.4.3.3.2.2.1.1 = 1036800 cách. (ii) Theo yêu cầu của bài toán, ta có số cách chọn như sau: Ghế Số cách xếp chỗ ngồi 1 12 2 11 3 10 4 9 5 8 6 7 12 6 10 5 8 4 6 3 4 2 2 1 Theo quy tắc nhân, ta có 12.6.10.5.8.4.6.3.4.2.2.1 = 33177600 cách. Ví dụ 1.1.3. Xét tập hợp X  1, 2, 3,..., 2009 . Đặt   A  x  X : x  1mod29 . 8 (i) Tính A . (ii) Tìm số tập con B của X sao cho B  A  . Lời giải (i) Xét x  A, ta có x  1 mod 29 nên x  1  29k , k   . Ta có 1  x  2009 suy ra 0  k  69. Vậy A  70 . (ii) Để tìm số tập con B của X thỏa mãn yêu cầu của bài toán ta sử dụng quy tắc bù trừ. Gọi P(X) là tập bao gồm tất cả các tập con của X , M là tập các tập con B của X sao cho B  A   . Khi đó, P X  \ M là tập các tập con B của   X mà B  A   hay B  X \ A. Suy ra P (X ) \ M  P X \ A . Do đó M  P X   P X \ A  22009  2200970  22009  21939. Ví dụ 1.1.4. Khi điều tra kết quả học tập các môn Toán, Lý, Hóa của một lớp có 45 học sinh, người ta nhận thấy rằng: 19 học sinh không giỏi môn nào, 18 học sinh giỏi Toán, 17 học sinh giỏi Lý, 13 học sinh giỏi Hóa, 10 học sinh giỏi hai môn Toán và Lý, 9 học sinh giỏi cả hai môn Lý và Hóa, 10 học sinh giỏi hai môn Toán và Hóa. Hỏi bao nhiêu học sinh giỏi cả ba môn? Lời giải Kí hiệu T là tập hợp học sinh của lớp. A, B , C lần lượt là tập hợp các học sinh giỏi Toán, Lý, Hóa của lớp đó. Vì A  B  C  T \ T \ A  B C  nên số học sinh giỏi ít nhất một   môn là A  B  C  T  T \ A  B C   45  19  26. Suy ra số học sinh giỏi cả ba môn là A  B C  A  B C  A  B  C  A  B  B C  C  A  26  18  17  13  10  9  10  7. Vậy có tất cả 7 học sinh giỏi cả ba môn. 9 1.2. Nguyên lý Dirichlet Nguyên lý Dirichlet mang tên nhà toán học người Đức, Peter Gustav Dirichlet (1805 – 1859), được phát biểu hết sức đơn giản:   * “Nếu nhốt n  1 con thỏ vào n cái lồng n   thì có một lồng chứa ít nhất hai con thỏ”. Một cách tổng quát, ta có nguyên lý Dirichlet mở rộng:   * “Nếu nhốt m con thỏ vào n cái lồng m, n  N thì luôn tồn tại một lồng  m  1  con thỏ”. chứa ít nhất 1    n    Ở đây, kí hiệu a  được dùng để chỉ phần nguyên của số thực a .   Sử dụng phương pháp phản chứng, ta có thể dễ dàng chứng minh được nguyên lý Dirichlet. Mặc dù được phát biểu hết sức đơn giản như vậy nhưng nguyên lý Dirichlet lại có những ứng dụng hết sức đa dạng, phong phú, trong nhiều lĩnh vực và rất hiệu quả. Trong một bài toán tổ hợp, nguyên lý Dirichlet nhiều lúc thể hiện được rõ nét vai trò của nó. Ví dụ 1.2.1. Xét tập hợp M  1, 2, 3,..., 9 . Với mỗi tập con X của M , ta kí hiệu S(X) là tổng tất cả các phần tử thuộc X . Chứng minh rằng trong số 26 tập con X của M với X  3, luôn tồn tại hai tập A và B sao cho S A  S B  . Lời giải Ta chia các tập con X của M thỏa mãn X  3 vào các lồng, mỗi lồng bao gồm các tập có cùng tổng các phần tử. Do 0  S X   24 nên có 25 lồng. Do có 26 tập X với X  3 nên tồn tại hai tập A, B thuộc cùng một lồng. Điều đó có nghĩa là tồn tại hai tập A, B sao cho S A  S B  . Vậy ta có điều phải chứng minh. 10 Ví dụ 1.2.2. Giả sử trong 6 người mà mỗi cặp hai người hoặc là bạn, hoặc là thù của nhau. Chứng minh rằng tồn tại một bộ ba người từng đôi một là bạn của nhau hoặc từng đôi một là kẻ thù của nhau. Lời giải Gọi A là một trong sáu người. Trong 5 người còn lại chia thành 2 nhóm: Bạn của A , thù của A . Do 5 = 2.2+ 1 nên theo nguyên lý Dirichlet có 3 người hoặc là bạn của A hoặc là thù của A . Không mất tính tổng quát, gọi B,C , D là các bạn của A . + Nếu B,C , D không ai là bạn của nhau thì B,C , D  là bộ ba cần tìm. + Nếu B,C , D có 2 người là bạn của nhau; giả sử B ,C . Khi đó A , B ,C là các bạn của nhau và A, B,C  là bộ ba cần tìm. Nếu B,C , D là thù của A thì lập luận tương tự, chỉ cần thay đổi vị trí “bạn” và “thù”. Như vậy bài toán được chứng minh. Ví dụ 1.2.3. (VMO – 2004) Cho tập A  1, 2, 3,...,16 . Hãy tìm số nguyên dương k nhỏ nhất sao cho trong mỗi tập con gồm k phần tử của A đều tồn tại hai số phân biệt a, b mà a 2  b 2   là một số nguyên tố. Lời giải Ta thấy, nếu a, b cùng chẵn thì a 2  b 2   là hợp số. Do đó, nếu tập con X của A có hai phần tử phân biệt a, b mà a 2  b2   là một số nguyên tố thì X không thể chỉ chứa các số chẵn. Từ đó suy ra k  9 . Ta chứng tỏ k = 9 là giá trị nhỏ nhất cần tìm. Điều đó có nghĩa là với mọi tập con X gồm 9 phần tử bất kì của A luôn tồn tại hai phần tử phân biệt a, b mà a 2  b 2   là một số nguyên tố. Để chứng minh khẳng định trên, ta chia tập A thành các cặp hai phần tử phân biệt a, b mà a 2  b2   là một số nguyên tố. Ta có 8 cặp gồm (1;4), (2;3), (5;8), (6;11), (7;10), (9;16), (12;13), (14;15). 11 Theo nguyên lý Dirichlet thì trong 9 phần tử của X có hai phần tử thuộc cùng một cặp và ta có điều phải chứng minh. Ví dụ 1.2.4. Trên mặt phẳng có 17 điểm, không có 3 điểm nào thẳng hàng. Cứ qua 2 điểm ta kẻ một đoạn thẳng và tô nó bằng một trong ba màu: Xanh, đỏ, vàng. Chứng minh tồn tại tam giác có 3 cạnh cùng màu. Lời giải Gọi A là 1 trong 17 điểm đã cho. Xét các đoạn thẳng nối A với 16 điểm còn lại gồm 16 đoạn thẳng. Theo nguyên lý Dirichlet do 16 = 5.3+1 nên tồn tại ít nhất 6 đoạn thằng cùng màu; giả sử là màu xanh. Gọi đầu mút kia của 6 đoạn là B , C , D, E , F , G . Nếu tồn tại 1 đoạn thẳng nối 2 trong 6 điểm trên là màu xanh thì bài toán được chứng minh. Nếu tất cả các đoạn thẳng nối 2 trong 6 điểm trên không có đoạn nào màu xanh. Xét 5 đoạn thẳng BC , BD, BE , BF , BG . Do 5  2.2 nên tồn tại ít nhất 3 đoạn cùng màu; chẳng hạn BC , BD, BE cùng màu đỏ. Nếu trong CD,CE , DE có một đoạn màu đỏ; chẳng hạn CD thì bài toán được chứng minh do tồn tại tam giác BCD thỏa mãn. Nếu CD,CE , DE đều màu vàng thì bài toán được chứng minh do tồn tại tam giác CDE thỏa mãn. 1.3. Hoán vị 1.3.1. Hoán vị không lặp Định nghĩa 1.3.1. Cho tập hợp A có n n  1 phần tử. 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 Pn . Định lí 1.3.1. Số các hoán vị của n phần tử Pn  n !  n. n  1 ...2.1. (1.11) Chứng minh Việc sắp xếp thứ tự n phần tử của tập hợp A có n phần tử là công việc gồm n công đoạn. Công đoạn 1 là chọn phần tử để xếp vào vị trí thứ nhất: Có n 12 cách thực hiện. Sau khi thực hiện công đoạn 1, công đoạn 2 là chọn phần tử để xếp vào vị trí thứ hai: Có n  1 cách thực hiện. Sau khi thực hiện xong i  1 công đoạn (chọn i  1 phần tử của A vào các vị trí thứ 1, 2,..., i  1 ), công đoạn thứ i tiếp theo là chọn phần tử xếp vào vị trí thứ i : Có n  i  1 cách thực hiện. Công đoạn cuối cùng (công đoạn thứ n ) có 1 cách thực hiện. Theo quy tắc nhân, ta có n(n  1)...2.1  n ! cách xếp thứ tự n phần tử của tập hợp A , tức là có n ! hoán vị. Ví dụ 1.3.1. Có bao nhiêu hoán vị của n phần tử, trong đó hai phần tử đã cho không đứng cạnh nhau? Lời giải Trước hết ta xác định số hoán vị, trong đó hai phần tử a và b đã cho đứng cạnh nhau. Vì a và b đứng cạnh nhau nên có n  1 cách chọn vị trí để đặt hai phần tử a, b . Ngoài ra, a và b còn có thể đổi chỗ cho nhau, do đó có 2(n  1) cách sắp đặt a và b cạnh nhau. Với mọi cách đó tương ứng (n  2)! hoán vị của các phần tử khác. Do đó số hoán vị trong đó a và b đứng cạnh nhau bằng 2.(n  1).(n  2)!  2.(n  1)!. Vì vậy số các hoán vị cần tìm bằng n ! 2.(n  1)!  (n  1)!(n  2). Ví dụ 1.3.2. Có 5 thẻ trắng, 5 thẻ đen, đánh dấu mỗi loại theo các số 1, 2, 3, 4, 5. Có bao nhiêu cách sắp xếp các thẻ này thành một hàng ngang sao cho hai thẻ cùng màu không nằm liền nhau? Lời giải Trường hợp 1: Các thẻ trắng ở vị trí số lẻ, các thẻ đen ở vị trí số chẵn. Mỗi một cách sắp xếp các thẻ trắng ở vị trí số lẻ là một hoán vị của 5 thẻ trắng. Suy ra có P5  5 ! cách sắp xếp các thẻ trắng. Tương tự, ta cũng có P5  5 ! cách sắp xếp các thẻ đen ở vị trí số chẵn. Vậy ta có 5 ! 5 ! cách sắp xếp 10 thẻ theo yêu cầu bài toán. 13 Trường hợp 2: Các thẻ trắng ở vị trí số chẵn, các thẻ đen ở vị trí số lẻ. Tương tự như trường hợp 1 có 5 ! 5 ! cách xếp thỏa mãn yêu cầu bài toán. Vậy ta có tất cả 2.(5 !)2 cách sắp xếp 5 thẻ trắng, 5 thẻ đen thỏa mãn yêu cầu bài toán. 1.3.2. Hoán vị lặp Định nghĩa 1.3.2. Hoán vị trong đó mỗi phần tử xuất hiện ít nhất một lần gọi là hoán vị lặp. Định lí 1.3.2. Số hoán vị lặp của n phần tử thuộc k loại khác nhau, mà các phần tử loại i 1  i  k  giống hệt nhau, xuất hiện ni lần với n 1  n 2  ...  n k  n , được kí hiệu là P n1,  n2, ,  nk  và được tính bằng công thức P n1, n2, , nk   n!  n1 ! n2 !...nk ! (1.12) Chứng minh Nếu coi n phần tử này là khác nhau thì sẽ có n ! cách sắp xếp. Trong mỗi cách sắp xếp như vậy, n1 phần tử loại 1 có thể hoán vị theo n 1 ! cách, n2 phần tử loại 2 có thể hoán vị theo n 2 ! cách, …, n k phần tử loại k có thể hoán vị theo nk ! cách. Do ni phần tử loại i i  1,2,..., k  là giống nhau nên số cách sắp xếp chỉ còn n!  n1 ! n2 !...nk ! Vậy P n1,  n2, ,  nk   n!  n1 ! n2 !...nk ! Ví dụ 1.3.3. 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? 14 Lời giải Để số cần lập x  a1a 2a 3a 4a 5a 6a 7a 8a 9a10a11 chia hết cho 5, thì x phải tận cùng là 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 là 0 thì 5 không có mặt và ngược lại nếu x tận cùng là 5, thì chữ số 0 không xuất hiện. Bởi vậy ai 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 a1a 2a 3a 4a 5a 6a 7a 8a 9a10 của số x bằng số hoán vị lặp của 10 phần tử thuộc bốn 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 a11 lại có thể nhận giá trị 0 hoặc 5 nên số các số cần tìm sẽ là 2P 1, 2, 3, 4  10! .2  25200. 1!2! 3! 4 ! Ví dụ 1.3.4. Với các chữ số 0,1, 2, 3, 4, 5 . Có thể lập được bao nhiêu số có 8 chữ số, trong đó chữ số 1 xuất hiện 3 lần, các chữ số khác xuất hiện đúng 1 lần? Lời giải Số tất cả các số có 8 chữ số (kể cả số 0 đứng đầu) trong đó chữ số 1 lặp lại 3 lần, các chữ số khác có mặt đúng 1 lần là P 3,1,1,1,1,1  8! 8!   3!1!1!1!1!1! 3! Trong các số vừa lập ở trên ta phải loại đi các số bắt đầu bằng chữ số 0, tức là các số chỉ có 7 chữ số, trong đó chữ số 1 có mặt 3 lần các chữ số 2, 3, 4 và 5 mỗi chữ số có mặt đúng 1 lần. Số các số như vậy bằng P 3,1,1,1,1  7! 7!   3!1!1!1!1! 3! 15 Vậy số các số thỏa mãn yêu cầu của bài toán là 8! 7 ! -  5880 . 3! 3! 1.3.3. Hoán vị vòng quanh Ví dụ 1.3.5. (Ví dụ dẫn dắt) Mời sáu người khách ngồi xung quanh một bàn tròn. Hỏi có bao nhiêu cách sắp xếp? Lời giải Nếu ta mời một người nào đó vào một vị trí bất kì, thì số cách sắp xếp năm người còn lại vào 5 vị trí giành cho họ sẽ có 5! = 120 cách. Vậy có tất cả 120 cách xếp sáu người ngồi xung quanh một bàn tròn. Nhận xét 1.3.1: Số hoán vị vòng quanh của n phần tử khác nhau được tính bởi công thức Qn  n  1 !. (1.13) Ví dụ 1.3.6. Có bao nhiêu cách xếp chỗ cho 6 bạn nữ và 6 bạn nam ngồi vào 12 ghế sắp quanh một bàn tròn mà không có hai bạn nữ nào ngồi cạnh nhau? Lời giải Xếp 6 ghế quanh một bàn tròn rồi xếp nam vào ngồi: Có 5! cách. Giữa hai bạn nam có khoảng trống. Xếp 6 bạn nữ vào trong 6 khoảng trống đó có 6! cách. Theo quy tắc nhân, ta có 5!6!  86400 cách xếp. Ví dụ 1.3.7. Một hội nghị bàn tròn có phái đoàn các nước: Việt Nam có 3 người, Lào có 5 người, Campuchia có 2 người, Thái Lan 3 người, Trung Quốc 4 người. Hỏi có bao nhiêu cách sắp xếp chỗ ngồi cho mọi thành viên sao cho người cùng quốc tịch thì ngồi cạnh nhau? Lời giải Đầu tiên, sắp xếp khu vực cho thành viên từng nước. Ta có thể mời một phái đoàn nào đó ngồi vào chỗ trước, rồi sắp xếp các phái đoàn còn lại có 4! cách xếp. Ứng với mỗi vị trí của phái đoàn lại có: 3! cách xếp chỗ ngồi cho 3 thành viên Việt Nam; 5! cách sắp xếp chỗ ngồi cho 5 thành viên Lào; 2! cách xếp chỗ 16 ngồi cho 2 thành viên Campuchia; 3! cách xếp chỗ ngồi cho 3 thành viên Thái Lan; 4 ! cách xếp chỗ ngồi cho 4 thành viên Trung Quốc. Vậy số cách sắp xếp thỏa mãn yêu cầu bài toán bằng 4 ! 3 ! 5 !2 ! 3 ! 4 !  4976640. 1.4. Chỉnh hợp 1.4.1. Chỉnh hợp không lặp Định nghĩa 1.4.1. Cho tập hợp A gồm n phần tử và số nguyên dương k với 1  k  n . Khi lấy ra k phần tử của A và sắp xếp chúng theo một thứ tự nào đó ta được chỉnh hợp chập k của n phần tử của A (gọi tắt là một chỉnh hợp chập k của A ). Số các chỉnh hợp chập k của tập hợp có n phần tử được kí hiệu là Ank . Nhận xét 1.4.1: Từ định nghĩa, ta thấy một hoán vị của tập hợp A có n phần tử là một chỉnh hợp chập n của A . Định lí 1.4.1. Số các chỉnh hợp chập k của tập A có n phần tử được tính bởi công thức Ank  n n  1 ... n  k  1  n!  n  k ! (1.14) Chứng minh Việc thiết lập một chỉnh hợp chập k của tập A có n phần tử là công việc gồm k công đoạn. Công đoạn 1 là chọn phần tử để xếp vào vị trí thứ nhất: Có n cách thực hiện. Sau khi thực hiện công đoạn 1, công đoạn 2 là chọn phần tử xếp vào vị trí thứ hai: Có n  1 cách thực hiện. Sau khi thực hiện xong i  1 công đoạn (chọn i  1 phần tử của A vào các vị trí thứ 1, 2,  i  1 ), công đoạn thứ i tiếp theo là chọn phần tử xếp vào vị trí thứ i : Có n  i  1 cách thực hiện. Công đoạn cuối cùng (công đoạn thứ k ) có n  k  1 cách thực hiện. Theo quy tắc nhân, ta có n n  1 ... n  k  1 cách lập một chỉnh hợp chập k của tập A có n phần tử, tức là có n n  1 n  k  1 chỉnh hợp chập k của tập A có n phần tử. Ví dụ 1.4.1. Cho mười chữ số 0,1, 2, 3, 4, 5, 6, 7, 8, 9 . Có bao nhiêu số lẻ có sáu chữ số khác nhau nhỏ hơn 600000 tạo ra từ mười chữ số đã cho? 17 Lời giải Gọi số lẻ có sáu chữ số khác nhau có dạng a1a 2a 3a 4a 5a 6 được tạo thành từ mười chữ số đã cho. Để số này nhỏ hơn 600000 thì 1  a 1  5. Vì vậy ta phải xét riêng hai trường hợp. Trường hợp 1: a 6  A1  1, 3, 5 . Khi đó ta có 3 cách chọn a6 , có 4 cách chọn a1 và A84 cách chọn ra 4 chữ số từ 8 chữ số còn lại để xếp vào 4 vị trí a 2 , a 3 , a 4 , a 5 . Theo quy tắc nhân, ta có 3.4.A84  20160 số. Trường hợp 2: a 6  A2  7, 9 . Khi đó ta có 2 cách chọn a6 , có 5 cách chọn a1 và A84 cách chọn 4 chữ số từ 8 chữ số còn lại để xếp vào 4 vị trí a 2 , a 3 , a 4 , a 5 . Theo quy tắc nhân, ta có 2.5. A 48  16800 số. Vậy theo quy tắc cộng, ta có 20160 + 16800 = 36960 số. Ví dụ 1.4.2. Từ các chữ số 1, 3, 5, 7 có thể lập được bao nhiêu số tự nhiên mà trong mỗi số này các chữ số không lặp lại? Lời giải Vì có bốn chữ số khác nhau, nên số dài nhất trong các số cần tìm cũng chỉ gồm 4 chữ số. Ta lập các loại số tự nhiên dạng a1a2 ...an . Dùng S1 để kí hiệu tập số dạng a 1, S 2 để kí hiệu tập số dạng a1a2 , S 3 để kí hiệu tập số dạng a1a 2a 3 , S 4 để kí hiệu tập số dạng a1a2a 3a 4 . Mỗi số thuộc S1 là một chỉnh hợp chập 1 của 4 phần tử của tập S  1, 2, 3, 4 ; mỗi số thuộc S 2 là một chỉnh hợp chập 2 của 4 phần tử của tập S ; mỗi số thuộc S 3 là một chỉnh hợp chập 3 của 4 phần tử của tập S ; mỗi số thuộc S 4 là một chỉnh hợp chập 4 của 4 phần tử của tập S . Vậy số các số thỏa mãn yêu cầu của đề bài bằng A41  A42  A43  A44  64. 18