Luận văn Thạc sĩ Toán học: Một số vấn đề về bài toán đếm trong tổ hợp

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:46

Thêm vào BST

Báo xấu

17
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn được viết dựa chủ yếu trên tài liệu chính để tham khảo. Mục đích chính của luận văn là trình bày, khẳng định lại các kết quả đã có trong toán học tổ hợp bằng lí luận đếm từ cơ bản đến nâng cao, phục vụ cho công việc giảng dạy môn toán tổ hợp ở bậc THPT. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một số vấn đề về bài toán đếm trong tổ hợp

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN THỊ BÍCH PHƯỢNG MỘT SỐ VẤN ĐỀ VỀ BÀI TOÁN ĐẾM TRONG TỔ HỢP LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2018
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN THỊ BÍCH PHƯỢNG MỘT SỐ VẤN ĐỀ VỀ BÀI TOÁN ĐẾM TRONG TỔ HỢP Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8460113 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Hoàng Lê Trường THÁI NGUYÊN - 2018
i Mục lục MỞ ĐẦU ii Chương 1. Bài toán đếm 1 1.1 Định lí nhị thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Lựa chọn với sự lặp lại . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Phân hoạch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Đếm lặp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Nguyên tắc trung bình . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.6 Nguyên tắc bao hàm loại trừ . . . . . . . . . . . . . . . . . . . . . . 15 Chương 2. Đếm nâng cao 19 2.1 Chặn cỡ của các tập giao . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Đồ thị không có chu trình độ dài 4 . . . . . . . . . . . . . . . . . . 23 2.3 Vấn đề của Zarankiewicz . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4 Tính trù mật của ma trận nhị phân . . . . . . . . . . . . . . . . . 36 KẾT LUẬN 39 TÀI LIỆU THAM KHẢO 40
ii MỞ ĐẦU Toán học tổ hợp là một trong những nội dung quan trọng trong giáo dục phổ thông. Học sinh thường gặp khó khăn khi giải quyết các bài toán này. Vì vậy, tìm hiểu sâu thêm về toán tổ hợp là rất cần thiết. Trong toán học tổ hợp, bài toán đếm là một trong những bài toán cơ bản. Phép đếm là một công cụ đắc lực trong toán học và là một điều rất tự nhiên trong cuộc sống con người. Nhiều kết quả đã biết trong toán học tổ hợp đều có thể được giải thích chỉ bằng phép đếm. Luận văn được viết dựa chủ yếu trên tài liệu chính để tham khảo là [4]. Mục đích chính của luận văn là trình bày, khẳng định lại các kết quả đã có trong toán học tổ hợp bằng lí luận đếm từ cơ bản đến nâng cao, phục vụ cho công việc giảng dạy môn toán tổ hợp ở bậc THPT. Cấu trúc luận văn gồm 2 chượng. Chương 1. Bài toán đếm. Chương 1 trình bày lại các kiến thức cơ bản nhất của bài toán đếm trong tổ hợp, cùng với một số ứng dụng điển hình của chúng thông qua lí luận đếm. Đó là định lí khai triển nhị thức NewTon, lựa chọn với sự lặp lại, phân hoạch, đếm lặp, nguyên tắc trung bình, nguyên tắc bao hàm loại trừ. Chương 2. Đếm nâng cao. Trên cơ sở vận dụng các kiến thức cơ bản đã được trình bày trong chương 1, chương 2 trình bày một số kết quả nâng cao đã nghiên cứu được từ bài toán đếm. Mục đích chính của chương 2 tập trung vào khai thác một số kết quả quan trọng trong lí thuyết đồ thị. Đó là chặn cỡ của các tập giao, đồ thị không có chu trình độ dài 4, vấn đề của Zarankiewicz, tính trù mật của ma trận nhị phân. Trong suốt quá trình làm luận văn, tác giả nhận được sự hướng dẫn và giúp
iii đỡ tận tình của tiến sĩ Hoàng Lê Trường. Tác giả xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất tới thầy. Tác giả cũng bày tỏ lòng biết ơn chân thành tới quí thầy cô giảng dạy lớp cao học toán khóa 10, trường Đại Học Khoa Học - Đại Học Thái Nguyên đã giảng dạy và truyền thụ đến cho tác giả nhiều kiến thức và kinh nghiệm nghiên cứu khoa học. Tác giả xin chân thành cảm ơn tới Ban giám hiệu, các đồng nghiệp trường THPT Lí Nhân Tông, gia đình và bạn bè đã luôn động viên giúp đỡ và tạo điều kiện cho tác giả về mọi mặt trong suốt quá trình học tập và thực hiện luận văn này. Thái Nguyên, ngày... tháng... năm 2018 Tác giả Nguyễn Thị Bích Phượng
1 Chương 1. Bài toán đếm 1.1 Định lí nhị thức Cho một tập có n phần tử, bài toán tìm số các tập con của nó có đúng k phần tử là bài toán cổ nhưng quan trọng với học sinh THPT. Con số này (số các tập con gồm k phần tử của tập hợp có n phần tử) thường được kí hiệu là Cnk và được gọi là hệ số nhị thức. Nói cách khác, Cnk là số khả năng chọn ra k phần tử phân biệt từ một bộ n phần tử phân biệt. Đẳng thức sau đây được chứng minh bởi Sir Isaac Newton năm 1666, và được biết đến như định lí khai triển nhị thức Newton. Định lí khai triển nhị thức Newton. Cho n là một số nguyên dương. Khi đó với mọi x, y , ta có n X n (x + y) = Cnk xk y n−k . k=0 Chứng minh. Ta có: (x + y)n = (x + y)(x + y) · · · (x + y), | {z } n số hạng Để chứng minh định lí ta cần chứng minh với mọi k = 0, 1, ..., n ta thu được Cnk số hạng xk y n−k . Thật vậy, ta xét bài toán tìm số các số hạng có chứa xk trong khai triển. Một cách tự nhiên chúng ta sẽ thực hiện phép đếm như sau. Đầu tiên, ta chọn k thừa số (x + y) bất kì trong n thừa số (các thừa số giống nhau đều có dạng là (x + y)) ta có Cnk cách chọn. Tiếp theo, ứng với mỗi cách chọn đó, muốn có số hạng xk ta lấy số x trong từng thừa số được chọn nhân với nhau thì ta sẽ được xk , số xk
2 này lại được tiếp tục nhân với nhóm còn lại, gồm (n − k) thừa số (x + y) hay nói cách khác xk còn được nhân thêm với (x + y)n−k . Vì số mũ của x chỉ được phép bằng k nên tiếp theo ta cần chọn xem trong khai triển (x + y)n−k = (x + y)(x + y) · · · (x + y), | {z } (n−k) số hạng Những số hạng nào nhân với xk mà sẽ không làm thay đổi số mũ của x. Ta thấy ngay rằng, đó phải là các số hạng không chứa x, chỉ chứa y. Muốn tìm các số hạng chỉ chứa y trong khai triển trên, thì chỉ có một cách duy nhất là ta lấy số y trong (n − k) thừa số ấy nhân với nhau, và kết quả ta được số hạng y n−k . Do đó, xk y n−k là số hạng mà chứa xk ứng với mỗi một cách chọn bộ k thừa số (x + y). Vì vậy, với Cnk cách chọn bộ k thừa số (x + y) như trên, ta thu được Cnk số hạng có dạng xk y n−k . Chú ý rằng định lí này chỉ là sự tổng quát hóa của hằng đẳng thức mà chúng ta đã biết: (x + y)2 = x2 + 2xy + y 2 . Mặc dù đơn giản như vậy, nhưng định lí khai triển nhị thức có rất nhiều ứng dụng. Ví dụ 1.1. (Tính chẵn lẻ). Đây là một ví dụ điển hình, hãy chỉ ra tính chất sau đây của các số nguyên: Nếu n,k là các số tự nhiên thì nk là số lẻ khi và chỉ khi n là số lẻ. Lời giải. (⇒) Nếu n = 2m, n là số chẵn thì nk = 2k mk cũng phải là số chẵn. (⇐) Để chứng minh chiều ngược lại ta giả sử rằng n là số lẻ tức là n có dạng n = 2m + 1 (m∈ N). Áp dụng định lí khai triển nhị thức ta có: nk = (2m + 1)k = 1 + (2m)1 Ck1 + (2m)2 Ck2 + · · · + (2m)k Ckk . Từ khai triển trên ta thấy nk phải là số lẻ.
3 n giai thừa kí hiệu n! là tích của n số tự nhiên liên tiếp đầu tiên, n! = n(n − 1) · · · 2.1 Điều này có thể mở rộng cho tất cả các số nguyên không âm với quy ước 0! = 1. Chỉnh hợp chập k của của n là tích của k thừa số đầu tiên. n! Akn = = n(n − 1) · · · (n − k + 1). (n − k)! Chú ý rằng Cn0 = 1 (tập rỗng) và Cnn = 1 (tập chứa toàn bộ n phần tử). Nói chung, hệ số nhị thức có thể được viết dưới dạng thương của các giai thừa. Akn n! Mệnh đề 1.2. Cnk = = . k! k!(n − k)! Chứng minh. Ta thấy Akn là số các dãy có thứ tự (x1 , x2 , · · · , xk ) gồm k phần tử khác nhau của một tập hợp cố định có n phần tử. Có n cách chọn phần tử đầu tiên x1 . Có (n − 1) cách chọn phần tử tiếp theo x2 ,· · · Bằng một cách khác ta có thể chứng minh được. Ta chọn một tập hợp k phần tử khác nhau từ tập hợp có n phần tử, ta có Cnk cách chọn. Ứng với mỗi cách chọn trên ta có Akk = k! cách sắp xếp thứ tự các phần tử của dãy (x1 , x2 , · · · , xk ). Từ đó ta kết luận: Akn = Cnk k!. Có nhiều đẳng thức hữu ích về mối quan hệ giữa các hệ số nhị thức. Trong nhiều tình huống, sử dụng những điều rất tự nhiên thuộc về tổ hợp để chứng minh các đẳng thức đại số giống như mệnh đề trên, chúng ta có thể thu được kết quả mong muốn một cách dễ dàng. Ví dụ khi chúng ta thấy rằng mỗi tập con được xác định một cách duy nhất theo phần bù của nó thì ngay lập tức ta thu được các đẳng thức. Cnn−k = Cnk . Với đẳng thức này, và với n cố định, giá trị của hệ số nhị thức Cnk tăng đến giữa rồi lại giảm. Dùng định lí khai triển nhị thức thì tổng của tất cả (n + 1) hệ số bằng 2n , 2n chính là số tất cả các tập con của tập có n phần tử: n X n X Cnk = Cnk (1)k (1)n−k = (1 + 1)n = 2n . k=0 k=0
4 Bằng một cách tương tự dùng tổ hợp ta có thể thiết lập được các đồng nhất thức hữu ích. Mệnh đề 1.3. (Tam giác Pascal). Với mọi số nguyên n≥ k ≥ 1, ta có k−1 Cnk = Cn−1 k + Cn−1 . k−1 Chứng minh. Số hạng đầu Cn−1 là số các tập hợp có k phần tử trong đó luôn k có một phần tử cố định. Số hạng thứ hai Cn−1 là số các tập hợp có k phần tử khác phần tử cố định trên. Do đó, tổng của chúng chính là Cnk . Thay đổi n,k, tính một cách chính xác hệ số nhị thức Cnk là rất phức tạp. Tuy nhiên, trong những ứng dụng, chúng ta thường chỉ quan tâm đến tỉ lệ tăng của chúng sao cho đủ để ước lượng. Ví dụ như ước lượng có thể thu được bằng cách sử dụng khai triển Taylor của hàm số mũ và hàm số lôgarit. t2 t3 (2) et = 1 + t + + + ··· , ∀t ∈ R 2! 3! và t2 t3 t4 (3) ln (1 + t) = t − + − + ··· , ∀ − 1 < t ≤ 1. 2 3 4 Điều này đặc biệt kéo theo một số ước lượng hữu ích khác (4) 1 + t < et , ∀t 6= 0, 2 −t− t2 (5) 1−t>e , ∀0 < t < 1. k Mệnh đề 1.4. (6) : ( nk )k ≤ Cnk và Cni ≤ ( en k P k ) . i=0 Chứng minh. Bị chặn dưới: n nn n nn−1 n−k+1 ( )k = ··· ≤ ··· = Cnk . k kk k kk−1 1 Bị chặn trên: Cho 0 < t ≤ 1, từ định lí nhị thức ta có bất đẳng thức sau: k k X X ti (1 + t)n Cni ≤ Cni = . tk tk i=0 i=0
5 k Tiếp theo ta thay t = . n Những ước lượng chặt chẽ hơn sau đây có thể thu được từ công thức nổi tiếng Stirling cho giai thừa: n √ (7) n! = ( )n 2πneαn , e ở đây 1/(12n + 1) < αn < 1/12n. Ước lượng này là cơ bản và có nhiều ứng dụng ví dụ như để tính xấp xỉ cho chỉnh hợp chập k của n phần tử −k2 k3 − 6n 2 +o(1) (8) Akn = nk e 2n với k = o(n3/4 ), và vì thế, áp dụng đối với hệ số tổ hợp ta có: −k2 k3 − 6n nk e 2n 2 (9) Cnk = (1 + o(1)). k! 1.2 Lựa chọn với sự lặp lại Trong phần trước chúng ta xét số cách chọn r phần tử phân biệt từ một tập hợp có n phần tử. Một điều tự nhiên đặt ra là điều gì sẽ xảy ra nếu chúng ta chọn những phần tử giống nhau lặp lại. Nói cách khác, chúng ta có thể trả lời câu hỏi có bao nhiêu nghiệm nguyên không âm của phương trình: x1 +· · ·+xn = r (xi ≥ 0, ∀i = 1, · · · , n) (xem xi như là số lần mà phần tử thứ i được chọn). Công thức sau đây của vấn đề này được đưa ra bởi Lov a´sz , P elika´n và Vesztergombi. Lov a´sz đã giải bài toán chia kẹo bằng phương pháp lựa chọn với sự lặp lại. Giả sử chúng ta có r cái kẹo cùng loại (giống nhau) chúng ta muốn chia cho n đứa trẻ. Chúng ta có bao nhiêu cách chia ?. Ta kí hiệu xi là số kẹo mà chúng ta phát cho đứa trẻ thứ i. Câu hỏi này tương đương với phát biểu ở trên. Câu trả lời phụ thuộc vào chúng ta có bao nhiêu cái kẹo và chúng ta phải công bằng như thế nào. Nếu chúng ta công bằng nhưng chúng ta chỉ có r < n cái kẹo thì một điều tự nhiên là không có sự lặp lại và ta chỉ phát được cho mỗi đứa trẻ không nhiều hơn một cái kẹo (đứa trẻ xi sẽ nhận được 0 hoặc 1 cái kẹo). Trong trường hợp này câu trả lời thật dễ dàng. Chúng ta chỉ cần chọn r đứa
6 trẻ trong n đứa trẻ để mỗi đứa trẻ này nhận được 1 chiếc kẹo. Chúng ta sẽ thấy rằng có Cnr cách làm như vậy. Bây giờ giả sử rằng, chúng ta có đủ kẹo, r ≥ n. Chúng ta phải công bằng, đó là chúng ta muốn mỗi đứa trẻ đều nhận được ít nhất một cái kẹo. Chúng ta bố trí những chiếc kẹo thành một hàng có chiều dài r (từ trái qua phải) và để cho đứa trẻ đầu tiên lấy kẹo từ trái sang phải. Sau một lúc, chúng ta dừng lại và để cho đứa trẻ thứ hai chọn kẹo cứ làm như vậy mãi. Việc chia kẹo được xác định bằng cách ghi rõ địa điểm, vị trí (giữa các kẹo liên tiếp nhau) của chỗ mà bắt đầu với một đứa trẻ mới. Có r − 1 vị trí như vậy và chúng ta phải chon n − 1 vị trí của chúng (đứa trẻ đầu tiên thường bắt đầu ở vị trí đầu tiên, vì vậy chúng ta không chọn vị trí này). Ví dụ nếu chúng ta có n = 6 đứa trẻ và có r = 9 cái kẹo, thì một tình huống điển hình như thế này: λ2 λ3 λ4 λ5 λ6 Do đó, chúng ta phải chọn một tập (n − 1) phần tử từ một tập có (r − 1) n−1 phần tử. Số cách chọn là Cr−1 . Nếu chúng ta không công bằng thì chúng ta sẽ có nhiều cách chia hơn. Mệnh đề 1.5. Số nghiệm nguyên của phương trình x1 + x2 + ... + xn = r với điều r kiện xi ≥ 0, với mọi i = 1, ..., n là Cn+r−1 . Chứng minh. Trong tình huống này, chúng ta không công bằng và cho phép rằng một vài đứa trẻ có thể không nhận được chiếc kẹo nào. Với những cách sau đây, chúng ta có thể làm giảm được vấn đề đếm số các cách chia như vậy, chúng ta chỉ cần làm như sau. Chúng ta mượn mỗi đứa trẻ một chiếc kẹo và sau đó chúng ta chia toàn bộ số kẹo (n + r) chiếc cho những đứa trẻ sao cho mỗi đứa trẻ nhận được ít nhất một cái kẹo. Bằng cách này, mọi đứa trẻ đều nhận lại được chiếc kẹo mà chúng ta đã mượn chúng và một số đứa trẻ may mắn hơn sẽ được nhận nhiều kẹo hơn. Phần hơn này chính là do từ r chiếc kẹo được chia cho n đứa trẻ. Chúng ta đã biết số cách chia (n + r) chiếc kẹo cho n đứa trẻ một cách công n−1 r bằng như trên là Cn+r−1 hay chính là Cn+r−1 .
7 1.3 Phân hoạch Một sự phân hoạch của n phần tử là một bộ những tập con rời nhau, gọi là các khối sao cho hợp của chúng chính là toàn bộ tập có n phần tử ban đầu. Ta kí hiệu S(n; k1 , k2 , · · · , kn ) là số tất cả các phân hoạch của n phần tử thành ki khối, (i = 1, 2, · · · , n; k1 + 2k2 + · · · + nkn = n). ki = số các khối sao cho mỗi khối có i phần tử trong một phân hoạch. Mệnh đề 1.6. n! S(n; k1 , k2 , ..., kn ) = . k1 !...kn !(1!)k1 ...(n!)kn Chứng minh. Chúng ta thấy rằng bất kì một sự sắp xếp nào tức là một hoán vị của n phần tử thì chúng ta sẽ thu được một phân hoạch như vậy. Bằng cách làm như sau: Đầu tiên ta coi các k1 khối 1 phần tử như là các hộp được đánh số từ 1 đến k1 , tiếp theo ta coi các k2 khối 2 phần tử như là các hộp được đánh số từ k1 + 1 đến k2 ,. . . . Chúng ta có n! cách sắp xếp. Ta sẽ chỉ ra rằng với mỗi phân hoạch như vậy sẽ được đếm k1 ! · · · kn !(1!)k1 · · · (n!)kn lần. Thật vậy, chúng ta có thể xây dựng một sự sắp xếp của các phần tử như sau: Đầu tiên ta xếp các khối có 1 phần tử, sau đó xếp các khối có 2 phần tử,...Chúng ta có ki ! cách để sắp xếp các khối có i phần tử và có (i!)ki cách để xếp các phần tử trong khối có i phần tử. 1.4 Đếm lặp Nguyên tắc cơ bản của phép đếm lặp bắt nguồn từ các quan sát thực tế cơ bản sau: Nếu các phần tử của một tập hơp được đếm bằng hai cách khác nhau, thì kết quả thu được là giống nhau. Trong hệ thống các ma trận 0 − 1 đều theo nguyên tắc cơ bản sau. M là một ma trận 0 − 1 cỡ n × m, ri là số các số 1 trong dòng i, cj là số các số 1 trong cột n P Pm j. Thế thì ri = cj = tổng số các số 1 trong ma trận M . i=1 j=1 Ví dụ sau đây là một minh họa cho nguyên tắc cơ bản của phép đếm lặp.
8 Giả sử rằng có một số lượng hữu hạn người gặp nhau trong một bữa tiệc và họ bắt tay nhau. Giả sử rằng không có một ai tự bắt tay mình và hơn nữa là không có hai người nào bắt tay nhau hơn một lần. Bổ đề bắt tay: Tại một bữa tiệc, số khách mà mỗi người khách có số lần bắt tay là số lẻ, là số chẵn. Chứng minh. Gọi P1 , · · · , Pn là những người đến dự tiệc. Chúng ta ứng dụng phép đếm lặp cho tập các cặp có thứ tự (Pi , Pj ) mà Pi và Pj bắt tay nhau ở bữa tiệc. Gọi xi là số lần mà Pi bắt tay và y là số cái bắt tay đã xảy ra. Một mặt, số Pn các cặp bắt tay nhau là xi , và với mỗi Pi số lựa chọn của Pj cũng là xi . Mặt i=1 khác, mỗi một cái bắt tay được tính cho cả hai cặp (Pi , Pj ) và (Pj , Pi ), vì vậy n P tổng số cái bắt tay là 2y. Do đó, xi = 2y . Không mất tính tổng quát, giả sử i=1 xi là số lẻ với mọi i = 1, . . . , n mà 2y lại là số chẵn suy ra n phải là số chẵn. Bổ đề này cũng chính là một hệ quả trực tiếp của trường hợp tổng quát sau đây mà nó chính là một phiên bản đặc biệt cho đồ thị, và đã được chứng minh bởi Euler. Cho một điểm x, bậc của nó là số d(x) trong một họ F , nó chính là số các phần tử của F chứa x. Mệnh đề 1.7. Cho F là một họ các tập con của X. Khi đó P P (10) d(x) = |A|. x∈X A∈F Chứng minh. Xét ma trận liên thuộc M =(mx,A ) của F . M là ma trận 0 − 1 cùng với |X| dòng, mỗi dòng được gán nhãn bởi x ∈ X và |F| cột được gán nhãn bởi các tập A ∈ F sao cho (mx,A ) = 1 nếu và chỉ nếu x ∈ A. Quan sát ta thấy d(x) chính là số của số 1 trong dòng x và |A| chính là số của số 1 trong cột A. Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó, nó được mô tả hình thức: G = (V, E) V gọi là tập các đỉnh và E gọi là tập các cạnh. Có thể coi E là tập các cặp (u,v) với 2 đỉnh u,v thuộc V. Và tùy theo đặc tính và số lượng của tập các cạnh E mà người ta có thể phân loại đồ thị thành đơn đồ thị, đa đồ thị, đồ thị có hướng và
9 đồ thị vô hướng. Như vậy, các đồ thị là họ các tập hợp gồm 2 phần tử, và bậc của đỉnh x là số các cạnh liên thuộc với x, là số đỉnh trong lân cận của nó. Do đó, kéo theo ta có định lí sau. Định lý 1.8. (Euler1736). Trong mọi đồ thị, tổng số bậc của các đỉnh bằng 2 lần tổng số cạnh của nó và do đó nó là số chẵn. Những đồng nhất thức sau đây có thể được chứng minh bằng cách tương tự X X (11) d(x) = |Y ∩ A|, ∀Y ⊂ X. x∈Y A∈F X XX XX 2 (12) d(x) = d(x) = |A ∩ B|. x∈X A∈F x∈A A∈F B∈F Chứng minh (11). Tương tự, xét ma trận liên thuộc M =(mx,A ) của F . M là ma trận 0 − 1 cùng với |Y | dòng, mỗi dòng được gán nhãn bởi x ∈ Y và |F| cột được gán nhãn bởi các tập A ∈ F sao cho (mx,A ) = 1 nếu và chỉ nếu x ∈ A. Quan sát ta thấy, d(x) chính là số của số 1 trong dòng x và |A ∩ Y | chính là số của số 1 trong cột A. d(x)2 . P P P Chứng minh (12). Trước tiên ta chứng minh: |A ∩ B| = A∈F B∈F x∈X Thật vậy, ta có thể viết vế trái của công thức dưới dạng khác XX X X S= |A ∩ B| = 1 A∈F B∈F x∈X x∈Ai ∩Aj Ai ,Aj ∈F Như vậy, để tính tổng S ở vế trái chúng ta đi đếm xem với mỗi x ∈ X có bao nhiêu cặp (Ai , Aj ) của họ F mà x ∈ Ai ∩ Aj . Ta cần chú ý bộ chỉ số (i, j) ở đây không nhất thiết phân biệt, và có thứ tự. Đặt J = {i : x ∈ Ai , Ai ∈ F}. Ta thấy, theo định nghĩa về bậc của x trong họ F thì d(x) = |J|. Bây giờ, ta sẽ xem với mỗi x ∈ X nếu ta thực hiện phép đếm như trên, thì sự đóng góp của nó vào tổng S là bao nhiêu. Nếu J = ∅ tức là d(x) = 0 thì sẽ không có cặp tập hợp nào của F , mà có giao của chúng có chứa x. Do đó, khi thực hiện việc đếm như trên, phần tử x sẽ cho
10 đóng góp vào tổng S ở trên là 0 = d(x)2 . Nếu J 6= ∅ tức là d(x) 6= 0. Khi đó, số các cặp tập hợp (Ai , Aj ) của họ F với i, j không nhất thiết phân biệt và có thứ tự, sao cho x ∈ Ai ∩ Aj chính là d(x)2 . Điều này có nghĩa là khi thực hiện việc đếm như trên, phần tử x trong trường hợp này cho đóng góp vào tổng S ở trên là d(x)2 . Vì vậy, X 1 = d(x)2 x∈Ai ∩Aj Ai ,Aj ∈F Do đó, lấy tổng trên tất cả các x ∈ X ta thu được XX X X X S= |A ∩ B| = 1= d(x)2 . A∈F B∈F x∈X x∈Ai ∩Aj x∈X Ai ,Aj ∈F Tiếp theo, ta chứng minh công thức XX XX |A ∩ B| = d(x). A∈F B∈F A∈F x∈A Thật vậy, theo công thức (11) với mỗi A cố định A ∈ F , ta có X X |A ∩ B| = d(x) B∈F x∈A Vì vậy, XX XX |A ∩ B| = d(x) A∈F B∈F A∈F x∈A Số Turan T(n,k,l) là số các tập con nhỏ nhất có l phần tử của tập X có n phần tử mà mọi tập con của X có k phần tử đều chứa ít nhất một tập trong chúng. Mệnh đề 1.9. Với mọi số nguyên dương l ≤ k ≤ n, Cnl T (n, k, l) ≥ . Ckl Chứng minh. Gọi F là một họ nhỏ nhất gồm các tập hợp có l phần tử trên X mà mọi tập con của X có k phần tử đều chứa ít nhất một phần tử của F . Đặt
11 ma trận 0 − 1 là ma trận M =(mA,B ) mà các dòng của nó được gán nhãn bởi các tập A trong F , các cột được gán nhãn bởi các tập con B của X có k phần tử, và mA,B = 1 nếu và chỉ nếu A ⊆ B. Gọi rA là số của số 1 trong dòng A và cB là số của số 1 trong cột B . Thế thì cB ≥ 1 với mọi B vì B phải chứa ít nhất một tập hợp trong F . Mặt khác, rA là số các tập con B có k phần tử trong đó B luôn chứa một tập có l phần tử cố k−l định. Vì vậy, rA = Cn−l với mọi A ∈ F . Bằng nguyên tắc đếm lặp, X X k−l |F|Cn−l = rA = cB ≥ Cnk , A∈F B mà Cnk Cnl T (n, k, l) = |F| ≥ k−l = , Cn−l Ckl Bất đẳng thức cuối này chính là một tính chất khác của hệ số nhị thức. Các ứng dụng của phép đếm lặp sau đây là tới từ lý thuyết số: Có bao nhiêu số là ước của số tự nhiên n. Nếu t(n) là số các ước của n thì dáng điệu của hàm này không ổn định: t(p) = 2 với mọi số nguyên tố p, trong khi đó t(2m ) = m + 1. Do đó, một điều thú vị là ta xét số trung bình của số các ước số: t(1) + t(2) + · · · + t(n) τ (n) = thì con số này hoàn toàn ổn định. Nó xấp xỉ ln n. n Mệnh đề 1.10. |τ (n) − ln n| ≤ 1. Chứng minh. Ứng dụng nguyên tắc đếm cơ bản, xét ma trận 0-1 cỡ n × n, M = (mij ) với mi,j = 1 khi và chỉ khi j chia hết cho i: Số lần xuất hiện của số 1 trong cột thứ j chính là t(j), là số các ước số của j . Vì vậy, lấy tổng trên các cột chúng ta thấy tổng của số lần xuất hiện số 1 trong ma trận là T (n) = t(1) + t(2) + · · · + t(n). Mặt khác, số các số 1 trong dòng i là số bội số của i: i, 2i, 3i, ..., ri mà ri ≤ n. n Do đó, chúng ta có [ ] chữ số 1 trong dòng i. Lấy tổng trên các dòng ta thu i được n X n Tn = [ ]. Vì x − 1 < [x] ≤ x, ∀x ∈ R nên chúng ta thu được : i i=1
12 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 3 1 1 1 4 1 1 5 1 1 6 1 7 1 8 1 1 Hn − 1 ≤ τ (n) =Tn ≤ Hn , n 1 1 1 ở đây (13) Hn = 1 + + + · · · + = ln n + γn , 0 ≤ γn ≤ 1 2 3 n là số điều hòa thứ n. 1.5 Nguyên tắc trung bình Giả sử rằng chúng ta có một tập hợp gồm m đối tượng (phần tử). Đối tượng thứ i có cỡ là li , và chúng ta muốn chứng minh có ít nhất một đối tượng trong tập hợp có cỡ lớn hơn t, với t cho trước nào đó, tức là tồn tại đối tượng i có lực lượng li ≥ t với t cho trước. Trong tình huống này, chúng ta xét lực lượng trung P li bình l = m và cố gắng chứng minh l ≥ t. Điều này ngay lập tức mang lại kết quả sau. Nguyên tắc trung bình. Mọi tập của các số phải chứa ít nhất một số lớn hơn hoặc bằng số trung bình và ít nhất một số nhỏ hơn hoặc bằng số trung bình. Nguyên tắc này rất đơn giản nhưng ứng dụng của nó thật đáng ngạc nhiên. Chúng ta sẽ thường xuyên sử dụng nguyên tắc này. Sử dụng nguyên tắc này, chúng ta cùng chứng minh điều kiện đủ sau đây về một đồ thị không liên thông. Nhắc lại rằng một thành phần liên thông trong một đồ thị là một tập hợp các đỉnh sao cho luôn có một đường đi giữa 2 đỉnh bất kì của chúng. Một đồ thị là liên thông nếu nó chỉ chứa một thành phần liên thông, nếu không thì nó là đồ
13 thị không liên thông. Mệnh đề 1.11. Mọi đồ thị với n đỉnh cùng với số cạnh nhỏ hơn n − 1 thì không liên thông. Chứng minh. Chúng ta chứng minh bằng quy nạp theo n. Khi n = 1, mệnh đề là hiển nhiên vì không có đồ thị nào có số cạnh âm. Khi n = 2, một đồ thị cùng với ít hơn 1 cạnh hiển nhiên là không liên thông. Giả sử rằng mệnh đề đúng với đồ thị có n đỉnh. Cho đồ thị G = (V, E) có |V | = n + 1 đỉnh sao cho |E| ≤ n − 1. Theo định lý Euler (Định lí 1.8) bậc trung 1 P 2|E| 2(n − 1) bình của tất cả các đỉnh là d(x) = ≤ < 2. |V | x∈V |V | n+1 Theo nguyên tắc trung bình, tồn tại một số đỉnh sẽ có bậc 0 hoặc 1. Nếu d(x) = 0 thì x chính là một thành phần liên thông và phần còn lại có một thành phần liên thông khác của G, vì vậy G không liên thông. Nếu d(x) = 1, giả sử rằng đỉnh duy nhất kề với x là y . Thế thì đồ thị H thu được từ G bằng cách xóa đỉnh x và các cạnh xy sẽ là đồ thị có |V | − 1 = n đỉnh và |E| − 1 ≤ (n − 1) − 1 = n − 2 cạnh. Theo giả thiết quy nạp, H không liên thông. Vì y thuộc vào duy nhất một thành phần liên thông của H , gọi là P và thành phần liên thông khác không chứa y là P 0 trong H nên x cũng thuộc cùng thành phần P và không thuộc thành phần liên thông P 0 trong G. Do đó G cũng không liên thông. Chúng ta đề cập đến một bất đẳng thức quan trọng mà chúng đặc biệt hữu ích khi làm việc với những đại lượng trung bình. Một hàm số f(x) nhận giá trị thực là hàm lồi nếu f (λa + (1 − λ)b) ≤ λf (a) + (1 − λ)f (b), ∀0 ≤ λ ≤ 1. Theo quan điểm hình học, tính lồi của hàm f có nghĩa là nếu chúng ta vẽ một đường l nối điểm (a, f (a)) và điểm (b, f (b)) thì đồ thị f(z) phải nằm phía dưới của l(z) với z ∈ [a; b]. Do đó, để hàm f là hàm lồi thì điều kiện đủ là đạo hàm cấp 2 của hàm f phải không âm. n P Mệnh đề 1.12. (Bất đẳng thức Jensen). Nếu 0 ≤ λi ≤ 1, λi = 1 và f là hàm i=1 lồi, thì n X n X (14) f( λi xi ) ≤ λi f (xi ). i=1 i=1
14 a λa + (1 − λ)b b Hình 1.1: Một hàm lồi Chứng minh. Ta dễ dàng chứng minh bằng quy nạp trên n. Khi n = 2, mệnh đề đúng. Giả sử bất đẳng thức đúng với số các số hạng tăng lên đến n, ta sẽ chứng minh nó đúng với n + 1. Để chứng minh điều này ta chỉ việc thay thế 2 số hạng đầu tiên trong biểu thức λ1 x1 + λ2 x2 + · · · + λn+1 xn+1 bằng biểu thức λ1 λ2 (λ1 + λ2 )( x1 + x2 ), và sử dụng giả thiết quy nạp. λ1 + λ2 λ1 + λ2 1 Nếu a1 , · · · , an là các số không âm xét f (x) = x2 , và λi = ta thu được một bất n đẳng thức hữu ích (nó cũng là một hệ quả của bất đẳng thức Cauchy − Schwarz ) n n X 1 X 2 (15) a2i ≥ ( ai ) . n i=1 i=1 Bất đẳng thức Jensen(15) mang lại bất đẳng thức hữu ích sau giữa số học và hình học, cụ thể: Với bất kì các số không âm a1 , · · · , an , ta có: n n 1X Y 1 (16) ai ≥ ( ai ) n . n i=1 i=1 Để chứng minh điều này, sử dụng bất đẳng thức Jensen với f (x) = 2x , 1 λ1 = · · · = λn = và xi = log2 ai , ∀1 = 1, · · · , n. Thế thì: n n n n n P n 1X X X ( xi )/n Y ai = λi f (xi ) ≥ f ( λi xi ) = 2 i=1 =( ai )1/n . n i=1 i=1 i=1 i=1
15 1.6 Nguyên tắc bao hàm loại trừ Nguyên tắc bao hàm loại trừ (Sàng Eratosthenes) là một công cụ đắc lực trong lý thuyết liệt kê, lý thuyết số. Nguyên tắc này liên quan đến lực lượng của hợp các tập hợp, lực lượng của giao các tập hợp, những lực lượng này chúng ta có thể tính được một cách dễ dàng. Cho A và B là 2 tập hợp bất kì.Ta có: |A ∪ B| = |A| + |B| − |A ∩ B|, Nói chung, khi chọn n tập con A1 , · · · , An của tập X, chúng ta muốn tính số phần tử của |A1 ∪ · · · ∪ An |. Để tính xấp xỉ đầu tiên của số này, ta có thể đi tính tổng (17) |A1 | + · · · + |An |. Tuy nhiên, nói chung là con số này lớn hơn số phần tử của |A1 ∪ · · · ∪ An |. Nếu Ai ∩ Aj 6= ∅ thì mỗi phần tử của Ai ∩ Aj được đếm 2 lần trong (17): một lần trong |Ai | và một lần trong |Aj |. Chúng ta có thể xử lý điều này bằng cách trừ đi từ (17) tổng X (18) |Ai ∩ Aj |. 1≤i