Tài liệu Các nguyên lý và kỹ thuật thường dùng trong các bài toán tổ hợp

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG ---------------------------------- DƯƠNG THỊ THANH THỦY CÁC NGUYÊN LÝ VÀ KỸ THUẬT THƯỜNG DÙNG TRONG CÁC BÀI TOÁN TỔ HỢP Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60 46 40 Tóm tắt luận văn Thạc sĩ khoa học Đà Nẵng – năm 2012 2 Công trình ñược hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học : Tiến Sĩ Nguyễn Duy Thái Sơn Phản biện 1:……………………………………… Phản biện 2:……………………………………… Luận văn sẽ ñược bảo vệ trước Hội ñồng chấm Luận văn tốt nghiệp thạc sĩ khoa học họp tại Đại học Đà Nẵng, ngày 01-02 tháng 12 năm 2012. Có thể tìm hiểu luận văn tại: - Trung tâm Thông tin – Học liệu, Đại học Đà Nẵng. - Thư viện trường Đại học sư phạm, Đại học Đà Nẵng. 3 MỞ ĐẦU 1. Lý do chọn ñề tài Trong những năm qua, Tổ hợp ñã trở thành một phần căn bản trong sách giáo khoa cho học sinh các trường phổ thông và cả trong giáo trình dành cho sinh viên các trường ñại học. Các nguyên lý và kỹ thuật trong Tổ hợp ngày càng có nhiều ứng dụng trong nhiều lĩnh vực khác, ñặc biệt là trong khoa học máy tính và lý thuyết toán tử. Các bài toán trong Tổ hợp không chỉ thách thức các nhà nghiên cứu mà còn xuất hiện rất thường xuyên trong các cuộc thi Toán học, nhất là trong các kỳ thi Olympic Toán học quốc tế (IMO). Tuy nhiên, hiện nay tài liệu tiếng Việt về Tổ hợp chưa nhiều. Sinh viên và học sinh Việt Nam thường tỏ ra lúng túng trước các bài toán Tổ hợp. Trong luận văn này, tôi sẽ cố gắng tìm hiểu các nguyên lý và kỹ thuật (từ cơ bản ñến nâng cao) thường dùng trong các bài toán Tổ hợp. Bản thân là một giáo viên phổ thông, tôi hi vọng sẽ khám phá ñược nhiều ñiều thú vị khi rèn luyện các kỹ năng Tổ hợp. Mong rằng luận văn này - sau khi ñược hoàn thành - sẽ cung cấp thêm một tài liệu về Tổ hợp ñáp ứng ñược phần nào lòng yêu thích Toán học của học sinh, phục vụ cho công tác bồi dưỡng học sinh giỏi. Đồng thời ñây cũng là một tài liệu ñể mọi người quan tâm ñến Tổ hợp tham khảo. Với những lý do trên, tôi chọn ñề tài “Các nguyên lý và kỹ thuật thường dùng trong các bài toán Tổ hợp” ñể nghiên cứu. 2. Mục ñích và nhiệm vụ nghiên cứu Tôi mong muốn tìm kiếm ñược nhiều tài liệu từ các nguồn khác nhau, nghiên cứu kỹ càng các tài liệu ñó, cố gắng lĩnh hội ñầy ñủ các kiến thức cũ và mới về Tổ hợp ñể có thể trình bày lại các kiến thức ñó trong 4 luận văn này theo một thể khép kín và hy vọng luận văn có thể ñược sử dụng như một tài liệu tham khảo bổ ích cho học sinh và giáo viên các trường trung học phổ thông và những người quan tâm ñến Tổ hợp. 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu: Nguyên lý và các kỹ thuật cơ bản trong lý thuyết Tổ hợp. 3.2. Phạm vi nghiên cứu: Các bài toán Tổ hợp. 4. Phương pháp nghiên cứu Cơ bản sử dụng phương pháp nghiên cứu tài liệu (sách, báo và các tài liệu trên internet có liên quan ñến ñề tài của luận văn) ñể thu thập thông tin nhằm tìm hiểu các nguyên lý và kỹ thuật cơ bản trong Tổ hợp, nghiên cứu cách giải và tập hợp các bài toán phục vụ cho yêu cầu của ñề tài. 5. Giả thuyết khoa học Xây dựng một giáo trình có tính hệ thống, khép kín và có thể giảng dạy ñược cho các học sinh chuyên toán bậc trung học phổ thông. Xây dựng ñược một hệ thống các bài toán (cũ và mới) với các mức ñộ khó dễ khác nhau ứng dụng các nguyên lý và kỹ thuật trong Tổ hợp. 6. Cấu trúc luận văn:Ngoài phần mở ñầu và kết luận, luận văn có nội dung chính sau - Chương 1: Hoán vị và tổ hợp - Chương 2: Hệ số nhị thức và hệ số ña thức - Chương 3: Nguyên lý bù trừ. 5 Chương 1 HOÁN VỊ VÀ TỔ HỢP 1.1. Hai nguyên lý ñếm cơ bản Trong cuộc sống hằng ngày, chúng ta thường phải liệt kê “các sự kiện” như: Sắp xếp các ñối tượng theo một cách nào ñó, phân chia các vật theo một ñiều kiện nhất ñịnh, phân phối sản phẩm theo một ñặc ñiểm kỹ thuật nhất ñịnh, v.v… Chẳng hạn, ta có thể ñối mặt với các bài toán ñếm có dạng: “Có bao nhiêu cách sắp xếp 5 người nam và 3 người nữ trong một hàng sao cho không có hai người nữ nào ñứng kề nhau?”. “Có bao nhiêu cách chia một nhóm gồm 10 người thành 3 nhóm con bao gồm một nhóm con 4 người, một nhóm con 3 người, một nhóm con 2 người và giữ lại 1 người.” Đó là hai ví dụ ñơn giản của bài toán ñếm liên quan ñến cái gọi là: “hoán vị” và “tổ hợp”. Trước khi giới thiệu trong phần tiếp theo thế nào là hoán vị và tổ hợp, ta hãy phát biểu hai nguyên lý ñếm cơ bản: Nguyên lý cộng (AP-Addition principle). Giả sử có: n1 cách ñể sự kiện n2 E1 xảy ra, cách ñể sự kiện E2 xảy ra, ... nk cách ñể sự kiện Ek xảy ra, trong ñó k > 1. Nếu các cách ñể xảy ra các sự kiện khác nhau nói trên là từng ñôi một rời nhau thì số cách ñể ít nhất một trong các sự kiện E1 ,E2,..., hoặc Ek xảy ra là : n1 + n2 +... + nk = ∑i=1 ni . k 6 Một dạng tương ñương của nguyên lý cộng, sử dụng thuật ngữ của lý thuyết tập hợp ñược phát biểu như sau: Cho A1 , A 2 , ..., A k là k tập hợp hữu hạn, trong ñó k ≥ 1 . Nếu các tập hợp ñã cho là rời nhau từng ñôi một, nghĩa là: Ai I Aj = ∅ khi i, j = 1, 2,..., k ; i ≠ j; thì k UA i k = A1 U A2 U ... U Ak = ∑ Ai . i =1 i =1 Nguyên lý nhân (MP-Multiplication Principle). Giả sử một sự kiện E có thể ñược phân tích thành r sự kiện, theo trình tự là E1 , E2 ,..., Er và giả sử có: n1 cách ñể sự kiện E1 xảy ra, n2 cách ñể sự kiện E2 xảy ra, ... nr cách ñể sự kiện Er xảy ra. Khi ñó, số cách ñể sự kiện E xảy ra là: r n1 × n2 × ... × nr = ∏ ni . i =1 Một dạng tương ñương của (MP), sử dụng thuật ngữ của lý thuyết tổ hợp, ñược phát biểu như sau: 7 Giả sử r ∏ A = A × A × ... × A = {( a , a ,... a ) | a ∈ A , i = 1, 2,...r} i =1 i 1 2 r 1 2 r i i biểu thị tích Đề-các của các tập hợp hữu hạn A1 , A2 ,..., Ar . Khi ñó, r ∏A i =1 i r = A1 × A2 × ... × Ar = ∏ A i . i =1 Với tư cách là các mệnh ñề trong Toán học, cả nguyên lý cộng và nguyên lý nhân ñều coa vẻ “hiển nhiên”. Đây có thể là lý do làm cho sinh viên thường xem nhẹ hai nguyên lý này. Có thể nói nguyên lý cộng và nguyên lý nhân thực sự là hai nguyên lý rất cơ bản trong các bài toán ñếm. Tuy nhiên, trong suốt luận văn này, ta sẽ thấy: Một bài toán ñếm - dù phức tạp ñến ñâu - cũng luôn ñược phân nhỏ thành các bài toán ñơn giản ñể ñộ chỉ cần dùng nguyên lý cộng và nguyên lý nhân ñể giải. 1.2. Hoán vị Cho A = {a1 , a2 ,..., an } là một tập hợp gồm n ñối tượng phân biệt. Với 0 ≤ r ≤ n , thì một r -hoán vị của tập A (Có nơi gọi là một chỉnh hợp chập r của n phần tử của tập A) là một cách sắp xếp r ñối tượng bất kì của A thành một hàng. Khi r = n , một n − hoán vị của A ñược gọi vắn tắt là một hoán vị của A. 1.3. Hoán vị vòng quanh Hoán vị ñược thảo luận trong tiết 1.2 ñã giải ñược những bài toán sắp xếp các ñối tượng trong một hàng. Có những hoán vị mà yêu cầu sắp xếp các ñối tượng trong một vòng tròn khép kín. Đó gọi là hoán vị vòng quanh. Xét bài toán sắp xếp 3 ñối tượng phân biệt a, b, c vào 3 vị trí quanh một vòng tròn. Giả sử 3 vị trí ñược ñánh số thứ tự (1), (2), và (3) như hình 8 1.5. Khi ñó ta có 3 cách sắp xếp của a, b, c như ñược chỉ ra trong hình 1.5 có thể xem tương ứng là các hoán vị: abc, cab, bca b a c (1) (1) X X c (1) Xb X (2) (3) X X b X (3) X a a (2) (3) Xc (2) Hình 1.5 Trong trường hợp này, các “hoán vị vòng quanh” như vậy ñược ñồng nhất với hoán vị thông thường, và vì vậy, không có gì ñáng bàn. Để có ñược những kết quả ñáng quan tâm hơn, bây giờ ta ñừng ñể ý ñến việc ñánh số thứ tự các vị trí (nghĩa là chỉ quan tâm ñến “vị trí tương ñối”). Như ñã thấy trong hình 1.6. Mỗi cách sắp xếp trong 3 cách sắp xếp như trên thu ñược từ 2 cách sắp xếp còn lại qua một phép quay; nghĩa là, vị trí tương ñối của các ñối tượng là không thay ñổi qua phép quay. Trong trường hợp như vậy, chúng ta xem 3 sắp xếp trong hình 1.6 không khác gì nhau. Một cách tổng quát, 2 hoán vị vòng quanh của các ñối tượng giống nhau ñược xem là trùng nhau nếu một trong số chúng thu ñược bởi một phép quay. c a c X Xb X abc b X X X b X a cab Hình 1.6 a Xc X bca 9 Cho A là một tập hợp của n ñối tượng phân biệt. Cho 0 ≤ r ≤ n , một r -hoán vị vòng quanh của A là một hoán vị vòng quanh của r ñối tượng phân biệt bất kì của A. Đặt Qrn biểu diễn số r -hoán vị vòng quanh của A . Chúng ta sẽ suy ra một công thức cho Qrn . 1.4. Tổ hợp Cho A là một tập gồm n ñối tượng phân biệt. Một tổ hợp của A chỉ ñơn giản là một tập con của A . Một cách chính xác hơn, với 0 ≤ r ≤ n, một r -tổ hợp (còn ñược gọi là một tổ hợp chập r) của A là một tập hợp con gồm r phần tử của A . n Đặt Crn hoặc   (ñọc là n chập r ) biểu thị số r -tổ hợp của n phần r tử tập A . Chúng ta sẽ suy ra công thức cho Crn . Điều khác nhau giữa một hoán vị và một tổ hợp của một tập hợp các ñối tượng là gì? Một hoán vị là một cách sắp xếp của những ñối tượng nhất ñịnh và do ñó sự sắp thứ tự các ñối tượng là quan trọng, trong khi một tổ hợp chỉ là một tập hợp của các ñối tượng và do ñó trật tự của các ñối tượng là không cần thiết. 1.5. Nguyên lý ñơn ánh và song ánh Cho A, B là các tập hữu hạn. Một ánh xạ f : A → B từ A ñến B là ñơn (hay 1-1) nếu f ( a1 ) ≠ f ( a2 ) trong B mỗi khi a1 ≠ a2 trong A . f là lên nếu với mọi b ∈ B , tồn tại a ∈ A sao cho f (a ) = b . Mỗi ánh xạ ñơn (tương ứng, lên) cũng ñược gọi là một ñơn ánh (tương ứng, toàn ánh). Một ánh xạ vừa là ñơn ánh, vừa là toàn ánh sẽ ñược gọi là một song ánh. 10 Nguyên lý ñơn ánh (IP-Injection Principle). Cho A và B là hai tập hợp hữu hạn. Nếu có một phép ñơn ánh từ A ñến B, thì A ≤ B . Nguyên lý song ánh (BP- Bijection Principle). Cho A và B là hai tập hợp hữu hạn. Nếu có một song ánh từ A ñến B, thì |A|=|B|. 1.6. Chỉnh hợp Trong các phần trước chúng ta ñã sắp xếp và chọn lựa các phần tử từ một tập hợp mà trong ñó không có sự lặp lại. Trong phần này chúng ta sẽ xét ñến sự sắp xếp và chọn lựa mà trong ñó các phần tử ñược phép lặp lại. Tổng quát, chúng ta có : (I) Số hoán vị r phần tử (r-hoán vị) của một tập hợp A = {a1 , a2 ,..., an } , trong ñó r , n ∈ N * , với sự lặp lại ñược phép, là n r . (II) Xét một tập hợp gồm r ñối tượng, trong ñó r1 ñối tượng loại 1, r2 ñối tượng loại 2, ..., và rn ñối tượng loại n , khi ñó r1 + r2 + L + rn = r . Số hoán vị khác nhau của tập các ñối tượng trên, kí hiệu là P(r ; r1 , r2 ,..., rn ) ñược cho là : P(r , r1 , r2 ,..., rn ) = r! . r1 !r2 !...rn ! Ta có thể phát biểu lại kết quả (I) và (II) như sau: (I) Số r-hoán vị của ña tập {∞ ⋅ a1 , ∞ ⋅ a2 ,..., ∞ ⋅ an } là nr 11 (II) Cho M = {r1 ⋅ a1 , r2 ⋅ a2 ,..., rn ⋅ an } , và r = r1 + r2 +...+ rn. Khi ñó số P(r; r1, r2,..., rn) hoán vị của M ñược ñưa ra là P(r ; r1 , r2 ,..., rn ) = r! . r1 !r2 !...rn ! Chương 2 HỆ SỐ NHỊ THỨC VÀ HỆ SỐ ĐA THỨC 2.1. Định lí nhị thức Ta bắt ñầu với hình thức ñơn giản sau ñây của ñịnh lí nhị thức ñược tìm ra bởi Issac Newton (1646-1727) vào năm 1676. Định lí 2.1. Cho số nguyên bất kì n ≥ 0, ( x + y) n n n  n  n−1  n  n =   x n +   x n−1 y + ... +   xy +  n  y 0 1 1 n −          n  n−r r ∑ rx y . r =0   n = 2.2. Các ñồng nhất thức tổ hợp Định lí nhị thức là một kết quả cơ bản trong toán học có nhiều ứng dụng. Trong tiết này ta sẽ ñưa ra các ví dụ cho thấy ñịnh lí nhị thức 2.1 có thể ñược sử dụng ñể phát hiện ra hàng loạt ñồng nhất thức hay liên quan ñến các hệ số nhị thức : 2.3. Tam giác Pascal n Tập hợp các hệ số nhị thức   có thể ñược sắp xếp trong một hình r tam giác từ ñỉnh xuống dưới và từ trái sang phải theo thứ tự tăng dần của 12 giá trị n và r, như hình 2.1. Biểu ñồ này, là một trong những biểu ñồ ñược nhiều người biết ñến trong lịch sử toán học, ñược gọi là tam giác Pascal, theo tên gọi của nhà Toán học nổi tiếng người Pháp Blaise Pascal (16231662), người ñã khám phá và truyền bá nó vào năm 1653 và ñược nhiều người biết ñến. Ta thu ñược một số kết quả tham khảo từ tam giác Pascal n (1) Hệ số nhị thức   , vị trí mà tính từ thứ n từ ñỉnh xuống và thứ r từ r 0 bên trái sang, là số ñường ñi ngắn nhất từ ñỉnh ñầu biểu diễn   ñến ñỉnh 0 n biểu diễn   . Đây là ñịnh thức ta thu ñược trong ví dụ 1.5.1. r n  n  (2) Vì   =   , nên các vị trí của tam giác là ñối xứng với ñường r n − r     0 thẳng ñi qua ñỉnh   . 0 (3) Định thức (2.1) nói rằng tổng của hệ số nhị thức tại cấp n thì bằng 2n , và theo ñịnh thức (2.6) tổng các hình vuông của hệ số nhị thức tại cấp n là  2n  bằng   . n  n   n − 1  n − 1  (4) Định thức   =   +  r  , cho thấy ñơn giản là mỗi hệ số nhị r r − 1       thức trong tam giác bằng tổng của hai nhị thức trên nó trực tiếp bên “vai” trái và phải. 13 2.4. Đường ñi ngắn nhất trong một lưới hình chữ nhật Một ñiểm ( a, b ) trên mặt phẳng x − y ñược gọi là một ñiểm nút nếu cả a và b là số nguyên. Hình 2.3 cho thấy một lưới hình chữ nhật trong mặt phẳng x − y gồm ( m + 1) × ( n + 1) ñiểm nút, và một ñường ñi ngắn nhất từ ñiểm nút ( 0,0 ) ñến ñiểm nút ( m, n ) , trong ñó m, n ∈ N * . Theo ví dụ 1.5.1 m + n m + n số ñường ñi ngắn nhất từ ( 0,0 ) ñến ( m, n ) là  ho ặ c   n . m     Trong tiết này, ta sẽ thấy kĩ thuật ñếm số ñường ñi ngắn nhất giữa hai ñiểm nút trong lưới hình chữ nhật ñược sử dụng như một cách ñể suy ra các ñồng nhất thức liên quan ñến hệ số nhị thức. Để bắt ñầu, ta phát biểu hai nhận xét sau : 10 Trong hình 2.4, số ñường ñi ngắn nhất từ O(0,0) ñến A ( x, y ) là  x + y  x  , và số ñường ñi ngắn nhất từ A ( x, y ) ñến P(m,n) là    (m − x) + (n − y)   . Do ñó số ñường ñi ngắn nhất từ O(0,0) ñến P(m,n) ñi m − x    x + y  (m − x) + (n − y)  qua A ( x, y ) là :    m−x  x   14 20 Trong hình 2.4, số ñường ñi ngắn nhất từ O(0,0) ñến A ( x, y ) là  x + y  x  và số ñường ñi ngắn nhất từ B ( x + 1, y ) ñến P ( m, n ) là    ( m − x − 1) + ( n − y )    . Do ñó số ñường ñi ngắn nhất từ O(0,0) ñến m − x − 1   P ( m, n ) qua ñoạn thẳng AB là  x + y   ( m − x − 1) + ( n − y )  .  x  m − x −1    Ta thành lập một nguyên lý hữu dụng về ñường ñi ngắn nhất trong một lưới, gọi là nguyên lý phản xạ Cho L : y = x + k (k ∈ Z ) là một ñường dốc 1 trên mặt phẳng x-y. Giả sử P và Q là hai ñiểm lưới ở một bên của L và P’ là phản xạ của P ñối với L như hình 2.9. Khi ñó, ta có : Nguyên lý phản xạ (RP-Reflection Principle). Số ñường ñi ngắn nhất từ P ñến Q mà ñiểm tiếp xúc là ñoạn thẳng L bằng số ñường ñi ngắn nhất từ P’ ñến Q. 15 2.5. Một số thuộc tính của các hệ số nhị thức Trong những phần trước, ta ñã tìm hiểu một số ñồng nhất thức liên quan ñến hệ số nhị thức và giới thiệu những kĩ thuật khác ñể thường sử dụng ñể suy ra chúng. Trong phần này, ta sẽ phát biểu một số tính chất hữu ích và nổi bật về hệ số nhị thức. Đầu tiên, chúng ta có một mốt tính chất sau ñây : 10 với n ∈ N * , n n n  n  >L >  n  > n < < L < 0 1            n − 1  n  2 (2.8) Và cho n lẻ, n ∈ N * ,  n   n  n n  n − 1  =  n + 1  > ... >  n  >  n  < < ... 0 1  n − 1  n               2   2  (2.9) 20 Lấy n ≥ 2 là một số nguyên. Mann và Shanks [7] chứng minh rằng n n là một số nguyên tố nếu và chỉ nếu n |   cho r = 1, 2,..., n-1. r Gần ñây, kết quả này ñã ñược phát triển bởi Z.Hao người ñã chứng minh rằng một số nguyên n > 2 là số nguyên tố.  n  n , 6 k ± 1    n cho tất cả số k với 1 ≤ k ≤   , khi  x  biểu thị số nguyên lớn nhất 6   không vượt quá số thực x . 16 30 Cho a, b, c ∈ Z , ta viết a ≡ b (ñồng dư c) nếu và chỉ nếu c ( a − b ) . Các kết quả trên là do nhà toán học người Pháp thế kỉ 19, E.Lucas (18421891). Lấy p là số nguyên tố thì n n ≡   (mod p), n ∈ N *   p  p (i )   p ii ( )   ≡ 0 (mod p), 1 ≤ r ≤ p − 1 r  p + 1  ≡ 0 (mod p ), 2 ≤ r ≤ p − 1 , r   ( iii )   p − 1 r (iv)  ≡ ( −1) (mod p ),0 ≤ r ≤ p − 1 ,   r   p − 2 r v ≡ ( −1) (r + 1) (mod p ), 0 ≤ r ≤ p − 2 , ( )   r   p − 3 r  r + 2 ≡ − 1 ( )   2  (mod p ), 0 ≤ r ≤ p − 3 . r     ( vi )  40 Cho một số nguyên tố p, ta có thể tìm ñược một số n ∈ N = N * U {0} n Sao cho p χ   cho mỗi r = 0,1,..., n r Chẳng hạn, lấy n = 0,1, 2,..., p − 1 (xem thuộc tính (iv)-(vi) ở trên) Bên cạnh ñó, có số n khác, và vì thế vấn ñề là: Cho một số nguyên tố, xác ñịnh một tập hợp   n * A = n ∈ N p χ   , r = 0,1,..., n  r   17 Theo Honsberger [6], vấn ñề này ñược ñặt ra và cũng ñược giải quyết bởi 2 nhà toán học Ấn Độ M.R. Railkar và M.R. Modak [9] vào năm 1976. Họ chứng minh rằng n∈ A nếu và chỉ nếu trong ñó m là một số nguyên không âm và n = k pm − 1 k = 1,2,..., p − 1. 50 lấy n, r ∈ N * và p là một số nguyên tố. Viết n và r theo p như sau: n = n0 + n1 p + n2 p 2 + ... + nk p k , r = r0 + r1 p + r2 p 2 + ... + rk p k , trong khi k là một số nguyên không âm và ni , ri ∈ {0,1,..., p − 1} , với mỗi i = 0, 1,..., k . Vào năm 1878, Lucas chứng minh một kết quả quan trọng:  n   n0   n1   nk   r  ≡  r   r  ... r  ( mod p ) .    0  1   k  Trong trường hợp riêng, nếu chúng ta lấy p = 2 và viết n và r trong dãy nhị phân: n = ( nk nk −1...n1n0 )2 r = ( rk rk −1...r1r0 )2 trong ñó ni , ri ∈ {0,1} , với mỗi i = 0,1,..., k , thì ta có kết quả thú vị sau: n  r  là lẻ nếu và chỉ nếu ni ≥ ri , với mỗi i = 0, 1,..., k .   (2.10) 60 Theo Honsberger [6], bài toán sau ñây ñã ñược giải quyết bởi n Fine [5] : n ∈ N * , có bao nhiêu hệ số nhị phân lẻ   có tại vị trí thứ n trên r tam giác Pascal? Chúng ta sẽ vận dụng (2.10) ñể trả lời câu hỏi này. n = ( nk nk −1,..., n1n0 )2 Viết 18 trong dãy nhị phân và lấy ω ( n ) = ∑ i=0 ni , bằng số chữ số 1 trong ña tập {n0 , n1 ,..., nk } . Cho r ∈ Z , sao k n cho 0 ≤ r ≤ n, viết r = ( rk rk −1... r1r0 )2 , theo kết quả (2.10) ,   là lẻ nếu và r chỉ nếu ri ≤ ni . Theo thứ tự ñó ri ≤ ni , ta ri = 0 nếu ni = 0 , và ri ∈ {0,1} nếu ni = 1. Do ñó, số sự lựa chọn cho r là 2ω ( n ) . Từ ñó, ta kết luận rằng n n ∈ N * , số hệ số nhị phân lẻ   tại vị trí n là 2ω ( n ) . Chẳng hạn, nếu r n = 11 = (1011)2 thì ω (11) = 3 , và trong số 12 hệ số nhị phân 1111 11 3  0  1  ,..., 11 tại vị trí 11, theo ñó ta có 8(=2 ) là lẻ:      11 11  0  = 11 = 1,     11 11  2  =  9  = 55,     11  11   1  = 10  = 11,     11 11  3  =  8  = 165.     Chương 3 NGUYÊN LÝ BÙ TRỪ 3.1. Nguyên lý bù trừ. Nguyên lý cộng (AP) ñã ñược trình bày ở ñầu của chương 1. Dạng ñơn giản nhất của nó là: Nếu A và B là những tập hữu hạn sao cho A I B = φ , thì |A U B| = |A| + |B|. Vậy ñẳng thức tương ứng nào cho |A U B| nếu A I B ≠ φ , nếu 19 A I B ≠ φ , thì khi ñếm A và B , các phần tử của A I B ñã ñược ñếm ñúng 2 lần. Vì vậy chúng ta có (xem hình 3.1): AU B = A + B − AI B . A (3.1) B Hình 3.1.1 Như chúng ta ñã thấy trong các chương trước, khi giải một số bài toán ñếm tương ñối phức tạp, các tập mà ta cần ñếm số phần tử thì thường ñược chia thành những tập con thích hợp rời nhau ñể có thể trực tiếp áp nguyên lý cộng. Tuy nhiên, việc chia một tập hợp thành các tập con rời nhau thích hợp như thế không phải lúc nào cũng dễ. Công thức (3.1) cung cấp cho chúng ta một phương pháp linh hoạt hơn: Biểu diễn tập hợp ñã cho dưới dạng A U B, mà A và B không cần rời nhau, và ñếm |A|, |B|, cũng như |A I B| một cách ñộc lập. Cộng |A| và |B| rồi trừ ñi |A I B|, kết quả thu ñược sẽ là |A U B|. Giai ñoạn “cộng” (|A| và |B| với nhau) còn ñược gọi là “bù”, vì thế công thức thu ñược có tên gọi là nguyên lý bù trừ. Công thức (3.1) là dạng ñơn giản nhất của nguyên lý bù trừ (PIE- the Principle of Inclusion and Exclusion). Tiếp theo, chúng ta sẽ mở rộng công thức (3.1) cho hai tập thành một công thức cho n tập, n ≥ 2 . Các công thức ñó còn ñược mở rộng hơn nữa trong tiết 3.2. Trong tiết 3.3. ta sẽ khảo sát một số ứng dụng của nguyên lý bù trừ. 20 Định lí 3.1. (PIE) Với mọi q tập hữu hạn A1 , A2 ,..., Aq , q ≥ 2, ta có: A1 U A2 U ... U Aq q = ∑ Ai − ∑ Ai I Aj + ∑ Ai I Aj I Ak i =1 i< j i< j (3.3) −... + (−1) q +1 A1 I A2 I ... I Aq . 3.2. Tổng quát hóa Trong ví dụ 3.1, chúng ta ñã ñếm số số nguyên trong S = {1, 2,..., 500} chia hết cho ít nhất một trong các số nguyên 2, 3, 5. Chúng ta có thể ñặt các câu hỏi kiểu khác. Chẳng hạn, có bao nhiêu số nguyên trong S mà (1) không chia hết cho bất kì số nào trong các số 2, 3, 5? (2) chỉ chia hết cho một trong ba số 2, 3, 5? (3) chia hết cho ñúng hai trong ba số 2, 3, 5? (4) chia hết cho cả ba số 2, 3, 5? Trong hình 3.2. ta biểu diễn các tập hợp thỏa mãn những yêu cầu trong các câu hỏi trên. Hình 3.2 Định lí 3.1. chưa ñủ ñể giải trực tiếp các câu hỏi trên. Trong phần này chúng ta sẽ thiết lập một kết quả tổng quát, cho phép chúng ta ñưa ra lời giải trực tiếp cho những câu hỏi loại này.