Chương 1 Kiến thức chuẩn bị Trong chương này chúng tôi trình bày một số kiến thức cơ bản về tổ hợp trong hình học và số học chuẩn bị cho các chương sau của luận văn. Các khái niệm và kết quả trong chương này có thể tham khảo trong các tài liệu tham khảo [1], [4]. và các tài liệu trong đó.1 Kiến thức tổ hợp 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, đặc biệt là lý thuyết tổ hợp. Trong đời sống hàng ngày, ta thường phải đếm các đối tượng nào đó, vì vậy phép đếm được sử dụng một cách cơ bản và thường xuyê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 phương pháp liệt kệ phần tử của tập hợp đó. Quy tắc cộng Giả sử có hai công việc. Việc thứ nhất có thể làm bằng n1 cách, việc thứ hai có thể làm bằng n2 cách và nếu hai việc này không thể làm đồng thời, khi đó sẽ có n1 + n2 cách làm một trong hai việc đó.
Chúng ta sẽ mở rộng quy tắc cộng cho trường hợp có nhiều hơn hai công việc. Giả sử các việc T1 , T2 ,. , Tm có thể làm tương ứng bằng 1 n1 , n2 ,. , nm cách và giả sử không có hai việc nào có thể làm đồng thời.
Khi đó số cách làm một trong m việc đó là n1 + n2 +. Quy tắc cộng có thể phát biểu dưới dạng ngôn ngữ tập hợp nhau sau: Nếu A1 , A2 , ., Am là các tập rời nhau, khi đó số phần tử của hợp các tập này bằng tổng số các phần tử của các tập thành phần. Giả sử Ti là việc chọn một phần tử từ tập Ai với i = 1, 2,. Có |Ai | cách làm Ti và không có hai việc nào có thể được làm cùng một lúc.
Số cách chọn một phần tử của hợp các tập hợp này, một mặt bằng số phần tử của nó mặt khác theo quy tắc cộng bằng |A1 | + |A2 | +. Cuối cùng chúng ta nhận được đẳng thức |A1 ∪ A2 ∪. Quy tắc nhân Giả sử một nhiệm vụ nào đó được tách ra làm hai công việc. Việc thứ nhất có thể làm bằng n1 cách, việc thứ hai có thể làm bằng n2 cách sau khi việc thứ nhất đã được làm, khi đó sẽ có n1 n2 cách thực hiện nhiệm vụ này.
Người ta thường sử dụng quy tắc nhân mở rộng. Giả sử rằng một nhiệm vụ nào đó được thi hành bằng cách thực hiện các việc T1 , T2 ,. Nếu việc Ti có thể làm bằng ni cách sau khi các việc T1 , T2 ,. , Ti−1 đã được làm, khi đó có n1 n2.
nm cách thi hành nhiệm vụ đã cho. Tương tự như quy tắc cộng, ta sẽ chuyển qua ngôn ngữ tập hợp như sau: Nếu A1 , A2 ,. , Am là các tập hữu hạn, khi đó số phần tử của tích Đề-các của các tập này bằng tích của số các phần tử của mọi tập thành phần. Để liên hệ với quy tắc nhân hãy nhớ là việc chọn một phần tử của tích Đề-các A1 · A2 ·.
· Am được tiến hành bằng cách chọn lần lượt một phần tử của A1 một phần tử của A2 , ., một phần tử của Am. Theo quy tắc nhân ta nhận được đẳng thức |A1 · A2 ·. Quy tắc bù trừ Khi hai công việc có thể được làm đồng thời, chúng ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Cộng 2 số cách làm mỗi việc sẽ dẫn đến sự trùng lặp, vì những cách làm cả hai việc sẽ được tính hai lần.
Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. Đó là “Nguyên lý bù trừ”. Chúng ta có thể phát biểu nguyên lý này bằng ngôn ngữ tập hợp: Cho A1 , A2 là các tập hợp. Gọi T1 là việc chọn một phần tử của A1 còn T2 là việc chọn một phần tử của A2.
Có |A1 | cách làm việc T1 và |A2 | cách làm việc T2. Số cách làm hoặc T1 hoặc T2 bằng tổng số cách làm việc T1 và số cách làm việc T2 trừ đi số cách làm cả hai việc. Vì có |A1 ∪ A2 | cách làm hoặc T1 hoặc T2 và có |A1 ∩ A2 | cách làm cả hai việc T1 và T2 nên ta có |A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 |.1: Hình minh họa nguyên lý bù trừ. Nguyên lý bù trừ được phát biểu một cách tổng quát thông qua định lý sau., An là các tập hợp hữu hạn.
Khi đó ta có công thức tổng quát sau đây: n X X X |A1 ∪ A2 ∪ · · · ∪ An | = |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | i=1 1≤i<j≤n 1≤i<j<k≤n n+1 −. Định lý này có thể chứng minh bằng phương pháp quy nạp toán học, tuy nhiên chúng tôi không trình bày ở đây. Bạn đọc có thể tham khảo thêm ở phần Chương 5 trong tập tài liệu [1]-Toán học rời rạc ứng dụng trong tin học.2 Hoán vị và chỉnh hợp Hoán vị của một tập các đối tượng khác nhau là một cách sắp xếp có thứ tự các đối tượng này. Chúng ta cũng quan tâm tới việc sắp xếp có thứ tự một số phần tử của một tập hợp.
Một cách sắp xếp có thứ tự k phần tử của một tập n phần tử được gọi là một chỉnh hợp chập k của n phần tử. Giả sử A là tập hữu hạn gồm n phần tử. Một cách sắp xếp n phần tử khác nhau của tập A theo một thứ tự nào đó được gọi là một hoán vị không lặp của các phần tử trong tập A, hay đơn giản là sự sắp xếp n phần tử của tập A. Khi đó, số hoán vị không lặp của n phần tử kí hiệu Pn và tính theo công thức Pn = n! = n(n − 1) · · · 2 · 1.
Hoán vị trong đó có 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., nk ) là số hoán vị có lặp của n phần tử gồm k loại, trong đó có n1 phần tử như nhau thuộc loại 1, n2 phần tử như nhau thuộc loại 2, ., nk phần tử như nhau thuộc loại k được tính theo công thức quát sau đây n! P (n1 , n2 , .nk ! Định nghĩa 1. Cho tập hợp A gồm n phần tử. Mỗi bộ gồm k (0 ≤ k ≤ n) phần tử được sắp thứ tự của tập A được gọi là một chỉnh hợp không lặp chập k của n phần tử thuộc A. Kí hiệu số chỉnh hợp không lặp chập k của n là Akn , tính bởi công thức n! Akn = = n(n − 1)(n − 2).
Cho tập hợp A gồm n phần tử. Mỗi dãy có độ dài k phần tử của tập A, mà mỗi phần tử có thể lặp lại nhiều lần và được sắp theo một thứ tự nhất định được gọi là một chỉnh hợp có lặp chập k của n phần tử thuộc tập A. Kí hiệu số chỉnh hợp có lặp chập k của n là Akn , tính bởi công thức Akn = nk. 4 Trong lý thuyết tổ hợp, các khái niệm hoán vị, chỉnh hợp và tổ hợp có vai trò quan trọng trong việc đếm, sắp xếp và lựa chọn các phần tử từ một tập hợp.3 Tổ hợp Một tổ hợp chập k của một tập hợp là một cách chọn không có thứ tự k phần tử của tập đã cho.
Như vậy, một tổ hợp chập k chính là một tập con k phần tử của tập ban đầu. Số tổ hợp chập k của tập có n phần tử được biểu thị bởi Cnk. Đây còn được gọi là tổ hợp không lặp Định nghĩa 1. Cho tập hợp A gồm n phần tử.
Mỗi tập con gồm k (0 ≤ k ≤ n) phần tử của tập A được gọi là một tổ hợp không lặp chập k của n là Cnk , tính bởi công thức n! Cnk =. Cho tập A gồm n phần tử. Một tổ hợp có lặp chập k (k không nhất thiết phải nhỏ hơn n) của n phần tử thuộc A là một bộ gồm k phần tử, mà mỗi phần tử này là một trong những phần tử của A. Kí hiệu số tổ hợp có lặp chập k của n là Cnk , tính bởi công thức k Cnk = Cn+k−1 .4 Nhị thức Newton Nhị thức Newton, do Isaac Newton đề xuất vào khoảng năm 1665-1666, có vai trò quan trọng trong lý thuyết tổ hợp để tính toán các hệ số trong biểu thức đa thức nâng mũ của một biểu thức số học.
Cho x, y là hai biến số và n là một số nguyên dương, ta có n X n (x + y) = Cnk xn−k y k .5 Nguyên lý Dirichlet Nguyên lý lồng chim bồ câu hay còn được gọi là nguyên lý Dirichlet, được đề xuất bởi nhà toán học Dirichlet vào thế kỉ 19. Nó cung cấp một công cụ quan trọng để phân tích và giải quyết các vấn đề liên quan đến sự xuất hiện lặp lại và phân phối các phần tử trong tổ hợp. Nếu có k + 1 hoặc nhiều hơn đồ vật được đặt vào trong k hộp thì có ít nhất một hộp chứa hai hoặc nhiều hơn hai đồ vật. CóN đồ vật được xếp N hay N +k−1 vào k hộp.
Khi đó, tồn tại một hộp chứa ít nhất k k đồ vật. Ở đây, kí hiệu ⌈x⌉ là hàm trần của x, là số nguyên bé nhất lớn hơn hoặc bằng x; còn [x] là phần nguyên của x-là số nguyên lớn nhất không vượt quá x.6 Nguyên lý cực hạn Định lý 1. (a) Một tập hợp hữu hạn các số thực luôn có phần tử lớn nhất và phần tử nhỏ nhất. (b) Một tập con bất kỳ của tập các số tự nhiên luôn có phần tử nhỏ nhất.2 Kiến thức số học Chúng tôi dành mục này để nhắc lại một số tính chất và định lý đặc trưng của số học.1 Số nguyên tố Định lý 1.