Luận văn Thạc sĩ Toán học: Bóng của tập hợp trên vành Bul hữu hạn

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

Thêm vào BST

Báo xấu

63
lượt xem 5
download

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

Luận văn Thạc sĩ Toán học: Bóng của tập hợp trên vành Bul hữu hạn trình bày các khái niệm và tính chất quan trọng của hai Bul hữu hạn quen thuộc, độ lớn của một đoạn đầu và bóng của một đoạn đầu trong sự sắp xếp các phần tử của vành Bul dưới thứ tự từ điển và một số nội dùng khác.

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: Bóng của tập hợp trên vành Bul hữu hạn

Luận văn Thạc sĩ Toán học Chuyên ngành Đại Số BÓNG CỦA TẬP HỢP TRÊN VÀNH BUL HỮU HẠN Người thực hiện : HOÀNG CÔNG CHỨC Người hướng dẫn : TS.TRẦN HUYÊN Ngày 5 tháng 10 năm 2004
LỜI CẢM ƠN Trước tiên, tôi xin chân thành bày tỏ lòng biết ơn sâu sắc nhất đến thầy hướng dẫn, Tiến sĩ Trần Huyên, thuộc Trường Đại Học Sư Phạm Thành phố Hồ Chí Minh, người thầy khả kính đã dành nhiều công sức và thời gian quý báu để hướng dẫn tôi từng bước trên con đường nghiên cứu khoa học với tất cả niềm say mê. Những kết quả trong luận văn này là không thể có được nếu không có sự tận tình và tâm huyết của thầy. Tôi cũng xin vô cùng biết ơn PGS-TS Bùi Tường Trí, PGS-TS Mỵ Vinh Quang, PGS-TS Bùi Xuân Hải và tất cả Quý Thầy, Cô trong Khoa Toán-Tin học Trường Đại Học Sư Phạm Thành phố Hồ Chí Minh, những người thầy đã tận tình dạy dỗ và truyền đạt cho tôi những kiến thức toán học hết sức giá trị trong niềm đam mê vô tận đối với Toán học. Tôi xin chân thành cảm ơn Ban Giám Hiệu, Phòng Khoa Học Công Nghệ - Sau Đại Học, Khoa Toán-Tin học của Trường Đại Học Sư Phạm Thành phố Hồ Chí Minh, Ban Giám Hiệu Trường Trung học Thực hành-ĐHSP Thành phố Hồ Chí Minh cùng Quý Thầy, Cô và các bạn đồng nghiệp đã không ngừng động viên, giúp đỡ, tạo mọi điều kiện thuận lợi về tinh thần cũng như vật chất cho tôi trong quá trình thực hiện luận văn này. Tác giả luận văn
LỜI NÓI ĐẦU Dưới sự phát triển của khoa học và công nghệ thông tin, lý thuyết Combinatorics nhanh chóng được quan tâm và phát triển để đáp ứng các yêu cầu của thực tiễn. Từ năm 1928, sau khi Sperner công bố một định lý rất đẹp về giá trị cực đại của hệ đơn xích các tập con của tập hữu hạn S, Combinatorics lại càng thu hút được sự chú ý của rất nhiều nhà Toán học. Hàng loạt các kết quả nghiên cứu về hệ các tập con của một tập hữu hạn được công bố. Một trong những bài toán thiết thực và thú vị của lý thuyết Combinatorics là giải quyết vấn đề cực trị của hệ các tập con của một tập hữu hạn mà chúng thỏa mãn một tính chất nào đó. Nghiên cứu lớp các bài toán này, Kruskal và Katona đã đưa ra và chứng minh một kết quả rất quan trọng và hữu ích, Định lý Kruskal-Katona về giá trị nhỏ nhất của bóng của tập hợp. Trong quá trình sử dụng và mở rộng định lý trên, người ta thu được nhiều kết quả lý thú, nhiều vấn đề mới nảy sinh cần giải quyết, nhất là khi xem xét lớp các bài toán về cực trị và đánh giá độ lớn của tập hợp trong vành Bul hữu hạn. Trong luận văn này, chúng ta xem xét một cách cụ thể và sâu sắc hơn các kết quả liên quan đến bóng của một tập hợp trong vành Bul hữu hạn. Đồng thời, chúng ta cũng đưa ra các kết quả đánh giá độ lớn của bóng, mở rộng thêm các kết quả đã đạt được cũng như các hướng nghiên cứu tiếp theo. Luận văn gồm 4 chương.
2 Chương I : Trình bày các khái niệm và các tính chất quan trọng của hai vành Bul hữu hạn quen thuộc là vành P(S) và B(n) . Chương II : Các kết quả xác định độ lớn của một đoạn đầu và bóng của một đoạn đầu trong sự sắp xếp các phần tử của vành Bul dưới thứ tự từ điển. Chương III : Trình bày chứng minh Định lý cơ bản và các kết quả của nó, đồng thời đưa ra một hướng mở rộng phạm vi nghiên cứu định lý quan trọng này. Chương IV : Các kết quả đánh giá đánh giá bóng của một tập hợp thông qua việc áp dụng Định lý cơ bản và bóng của một đoạn đầu trong vành Bul hữu hạn. Do thời gian và trình độ có hạn, luận văn không tránh khỏi những sai sót. Vì vậy, tôi rất mong nhận được sự thông cảm, giúp đỡ và những góp ý quý báu của Quý Thầy, Cô, các bạn đồng nghiệp và đọc giả.
Mục lục I Các khái niệm cơ bản trên vành Bul hữu hạn 1 I.1 Vành P(S) . . . . . . . . . . . . . . . . . . . . . . . . 2 I.1.1 Cấu trúc vành trên P(S) . . . . . . . . . . . . . 2 I.1.2 Cấu trúc thứ tự trên P(S) . . . . . . . . . . . . 2 I.1.3 Bóng của tập hợp trong P(S) . . . . . . . . . . 4 I.2 Vành B(n) . . . . . . . . . . . . . . . . . . . . . . . . 6 I.2.1 Cấu trúc vành trên B(n) . . . . . . . . . . . . 6 I.2.2 Cấu trúc thứ tự trên B(n) . . . . . . . . . . . . 7 I.2.3 Bóng của tập hợp trên B(n) . . . . . . . . . . . 7 I.3 Quan hệ giữa vành B(n) và vành P(S) . . . . . . . . . 9 II Biểu diễn k-nhị thức và Bóng của đoạn đầu 10 II.1 Một số bài toán mở đầu . . . . . . . . . . . . . . . . . 11 II.2 Biểu diễn k-nhị thức của một số . . . . . . . . . . . . . 14 II.3 Bóng của đoạn đầu . . . . . . . . . . . . . . . . . . . . 23 III Định lý cơ bản về Bóng của tập hợp và sự mở rộng phạm vi ứng dụng 29 III.1 Toán tử nâng Sj . . . . . . . . . . . . . . . . . . . . . . 29 III.2 Định lý cơ bản về bóng của tập hợp . . . . . . . . . . . 35 III.3 Một hướng mở rộng phạm vi ứng dụng của Định lý cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 IV Vài kết quả đánh giá bóng của đoạn đầu 46 IV.1 Các định lý về phép cộng dưới . . . . . . . . . . . . . . 46 IV.2 Một ước lượng lực lượng của đoạn đầu thông qua bóng 55
Chương I Các khái niệm cơ bản trên vành Bul hữu hạn Lớp các vành Bul hữu hạn có rất nhiều tính chất quan trọng và lý thú, những tính chất đó được thể hiện rõ nhất trong hai vành Bul hữu hạn quen thuộc sau đây: 1. Cho S là tập hợp hữu hạn có n phần tử, vành Bul hữu hạn P(S) được xây dựng trên tập tất cả các tập con của tập S. 2. Cho số nguyên dương n, vành Bul hữu hạn B(n) , được xây dựng trên tập hợp B(n) xác định như sau B(n) = {(εn , εn−1 , . . . , ε1 ) : εi = 0 hoặc εi = 1 với i = 1, 2, . . . , n} Ta gọi tập S có n phần tử là n-tập S, tập con gồm k phần tử của tập S là k-tập con của S.Với n-tập S cho trước, chúng ta dễ dàng kiểm tra được vành P(S) và vành B(n) là đẳng cấu với nhau. Hơn nữa, mọi vành Bul hữu hạn đều đẳng cấu với hai vành trên. Vì vậy, tùy theo từng vấn đề cụ thể, việc xem xét chúng được thực hiện trên vành P(S) hoặc vành B(n) mà sự lựa chọn này không đưa đến sự thay đổi nào đối với kết luận chung trên lớp các vành Bul hữu hạn. Trong chương này, chúng ta đưa ra một số khái niệm liên quan đến bóng của tập hợp vành Bul hữu hạn thông qua việc xem xét cấu trúc thứ tự trên vành P(S) và vành B(n) .
I.1.Vành P(S) 2 I.1 Vành P(S) Cho S là tập hợp hữu hạn n phần tử, n ≥ 1, n ∈ Z, để đơn giản ta xét S = {1, 2, . . . , n}. Khi đó, P(S)={A | A ⊆ S} là tập tất cả các tập con của S. Như vậy, số phần tử của P(S) là 2n . Nếu không có gì nhầm lẫn, ta ký hiệu tập A = {a1 , a2 , . . . , ak } ⊆ S là A = a1 a2 . . . ak . I.1.1 Cấu trúc vành trên P(S) Ta xây dựng cấu trúc vành trên P(S) bằng cách định nghĩa phép toán cộng (+) và phép toán nhân (·) các phần tử của P(S) như sau: Với mọi A, B ∈ P(S) A+B =A4B A.B = A ∩ B Trong đó, A 4 B = (A \ B) ∪ (B \ A) là hiệu đối xứng của A và B. Ta dễ dàng kiểm tra tính hợp lý của hai phép toán trên và (P(S), +, ·) là vành giao hoán, phần tử đơn vị là S, phần tử 0 là tập rỗng ∅. Với mọi A ∈ P(S) ta có A2 = A.A = A ∩ A = A. Do đó, (P(S), +, ·) là vành Bul hữu hạn. Với mỗi tập A ∈ P(S), ta gọi tập A0 = S − A là phần bù của A trong S. Từ định nghĩa của phép toán cộng, ta có ngay: A + B = A0 + B 0 với mọi A, B ∈ P(S). I.1.2 Cấu trúc thứ tự trên P(S) Trước hết, ta có quan hệ thứ tự thông thường ≤ trên vành P(S) dựa trên quan hệ bao hàm các tập hợp như sau: Với mọi A, B ∈ P(S) ta nói A ≤ B khi A ⊆ B. Hiển nhiên ≤ là quan hệ thứ tự bộ phận trên P(S). Sau đây, chúng ta xem xét một quan hệ thứ tự khá thú vị trên hệ tất cả các tập hợp con có cùng số phần tử của tập S.
I.1.Vành P(S) 3 Thứ tự nén trên hệ các k-tập con của n-tập S Với A ∈ P(S), ta đặt |A| là số phần tử của tập A. Khi đó, với mỗi k ∈ {0, 1, . . . , n}, ta gọi mức thứ k của P(S) là tập hợp Pk (S) = {A ⊆ S : |A| = k} gồm tất cả các k-tập con của n-tập S. Trên Pk (S) ta xác định quan hệ thứ tự
I.1.Vành P(S) 4 dưới thứ tự nén cũng chính là vị trí của A ∈ Pk (S 0 ) trong sắp xếp Pk (S 0 ) dưới thứ tự nén, ở đây S 0 = {1, 2, . . . , nA } với nA = max A. ◦ Tính chất 3: Phần tử lớn nhất của Pk (S) dưới thứ tự nén là tập {n, n − 1, . . . , n − k + 1} ◦ Tính chất 4: Cho A ⊆ Pk (S), ta gọi tập A0 = {A0 = S−A : A ∈ A} là phần bù của A. Khi đó, nếu A = {A1 , A2 , . . . , Am } thỏa mãn A1
I.1.Vành P(S) 5 •Bóng trên của A là tập hợp ∇A được xác định như sau: ∇A = {B ∈ Pk+1 (S) : A ⊂ B với A là tập nào đó trong A} • Với 1 ≤ r ≤ k, bóng cấp r của A là tập hợp ∆r A gồm tất cả các (k − r)-tập con của S mà chúng được chứa trong A ∆r A = {B ∈ Pk−r (S) : B ⊂ A} • Với 1 ≤ r ≤ k, bóng cấp r của tập A là tập hợp ∆r A được xác định ¡ ¢ theo công thức quy nạp ∆1 A = ∆A và ∆r+1 A = ∆ ∆r A . Khi đó ∆r A là bóng của A ở mức thứ k − r. ∆r A = {B ∈ Pk−r (S) : B ⊂ A với A là tập nào đó trong A} • Với 1 ≤ r ≤ n − k, bóng trên cấp r của A là tập hợp ∇r A gồm tất cả các (k + r)-tập con của S mà chúng chứa A ∇r A = {B ∈ Pk+r (S) : A ⊂ B} • Với 1 ≤ r ≤ n − k, bóng trên cấp r của A là tập hợp ∇r A được xác ¡ ¢ định theo công thức quy nạp ∇1 A = ∇A và ∇r+1 A = ∇ ∇r A . Khi đó ∇r A là bóng trên của A ở mức thứ k + r. ∇r A = {B ∈ Pk+r (S) : A ⊂ B với A là tập nào đó trong A} Ta có ngay các tính chất về bóng của tập hợp trong P(S) như sau: ¡¢ ¡ ¢ ? Với A ∈ Pk (S) ta có: |∆r A| = kr và |∇r A| = n−k r S S ? Với A ⊆ Pk (S) ta có: ∆ A = A∈A ∆ A và ∇ A = A∈A ∇r A r r r Định lý I.1.1. Cho A ⊆ Pk (S) là hệ các k-tập con nào đó của n-tập S. Khi đó với mỗi số nguyên dương r, 1 ≤ r ≤ min {k, n − k} ta có : |∆r A| = |∇r A0 | và |∇r A| = |∆r A0 | Chứng minh. Với mỗi B ∈ ∇r A, ta tìm được tập A ∈ A thỏa mãn A ⊂ B. Ta có B 0 = S − B ⊂ S − A = A0 ∈ A0 ⊆ Pn−k (S)
I.2.Vành B(n) 6 Mặt khác |B| = k + r, |B 0 | = |S − B| = n − (k + r) = (n − k) − r. Từ đó suy ra B 0 ∈ ∆r A0 . Vậy có sự tương ứng 1 − 1 giữa tập B ∈ ∇r A và tập B 0 = S − B ∈ ∆r A0 . Do đó |∇r A| ≤ |∆r A0 |. Ngược lại, với mỗi tập B 0 ∈ ∆r A0 ta tìm được tập A0 ∈ A0 sao cho B 0 ⊂ A0 . Ta có B = S − B 0 ⊃ S − A0 = A ∈ A ⊆ Pk (S) Ta lại có |B 0 | = (n−k)−r, |B| = |S −B 0 | = n−(n−k −r) = k +r. Từ đó suy ra B ∈ ∇r A. Vậy có sự tương ứng 1 − 1 giữa tập B 0 ∈ ∆r A0 và tập B = S − B 0 ∈ ∇r A. Do đó |∆r A0 | ≤ |∇r A|. Vậy |∆r A0 | = |∇r A|. Bằng cách thay A bởi A0 ta có |∆r A| = |∇r A0 | ¥ I.2 Vành B(n) Cho n ∈ Z, n ≥ 1, ta đặt B(n) là tập hợp gồm tất cả các dãy có n thành phần là 0 hoặc 1 xác định như sau: B(n) = {(εn , εn−1 , . . . , ε1 ) : εi = 0 hoặc εi = 1 với mọi i = 1, 2, . . . , n} Như vậy, mỗi phần tử của B(n) là một dãy ngược (εn , εn−1 , . . . , ε1 ). Nếu không có gì nhầm lẫn, ta ký hiệu εn εn−1 . . . ε1 thay cho (εn , εn−1 , . . . , ε1 ). Rõ ràng số phần tử của B(n) là 2n . I.2.1 Cấu trúc vành trên B(n) Ta xây dựng vành Bul B(n) bằng cách định nghĩa phép toán cộng (+) và phép toán nhân (·) như sau: Với mọi x, y ∈ B(n), x = (εn , εn−1 , . . . , ε1 ), y = (ε0n , ε0n−1 , . . . , ε01 ) x + y = (εn + ε0n , εn−1 + ε0n−1 , . . . , ε1 + ε01 ) x.y = (εn ε0n , εn−1 ε0n−1 , . . . , ε1 ε01 ) Trong đó, với mọi i = 1, 2, . . . , n: ½ ½ εi + ε0i = 0 nếu εi = ε0i εi ε0i = 1 nếu εi = ε0i = 1 và εi + ε0i = 1 nếu εi = 6 ε0i εi ε0i = 0 nếu εi = 0 hoặc ε0i = 0
I.2.Vành B(n) 7 Chúng ta dễ dàng kiểm tra tính hợp lý của hai phép toán trên và (B(n), +, ·) là vành giao hoán, phần tử đơn vị là 11...1 | {z } , phần tử 0 là n 00...0 | {z }. Với mọi x ∈ B(n), x = (εn , εn−1 , . . . , ε1 ) ta có: n x2 = x.x = (εn εn , εn−1 εn−1 , . . . , ε1 ε1 ) = (εn , εn−1 , . . . , ε1 ) = x Vậy (B(n), +, ·) là vành Bul hữu hạn. I.2.2 Cấu trúc thứ tự trên B(n) Trên vành B(n) , chúng ta có quan hệ thứ tự bộ phận quen thuộc được xây dựng dựa vào phép toán nhân các phần tử là : Với mọi x, y ∈ B(n) ta nói x ≤ y nếu x.y = x. Sau đây chúng ta xét một thứ tự khác liên quan đến sự sắp xếp các dãy εn εn−1 . . . ε1 . Trước hết, với mọi x ∈ B(n), x = εn εn−1 . . . ε1 , ta gọi hạng của x là số tự nhiên k = |x| = εn + εn−1 + . . . + ε1 . Khi đó, với mỗi k ∈ {0, 1, . . . , n} ta gọi mức thứ k của B(n) là tập hợp B(n, k) gồm tất cả các phần tử hạng k của B(n) B(n, k) = {x ∈ B(n) : |x| = k} Ta định nghĩa trên B(n, k) thứ tự
I.2.Vành B(n) 8 A ⊆ B(n, k) là tập hợp bất kỳ các phần tử hạng k của B(n) . Khi đó: • Bóng của x là tập hợp ∆x = {y ∈ B(n, k-1) : y ≤ x} • Bóng của tập A là tập hợp ∆A được xác định bởi ∆A = {y ∈ B(n, k-1) : y ≤ x với x là phần tử nào đó của A} • Bóng trên của x là tập hợp ∇x = {y ∈ B(n, k+1) : x ≤ y} • Bóng trên của tập A là tập hợp ∇A xác định bởi ∇A = {y ∈ B(n, k+1) : x ≤ y với x là phần tử nào đó của A} • Với 1 ≤ r ≤ k, bóng cấp r của x là tập hợp ∆r x = {y ∈ B(n, k-r) : y ≤ x} • Với 1 ≤ r ≤ k, bóng cấp r của tập A là tập hợp ∆r A được xác định ¡ ¢ theo công thức quy nạp ∆1 A = ∆A và ∆r+1 A = ∆ ∆r A . Khi đó ∆r A là bóng của A ở mức thứ k − r. ∆r A = {y ∈ B(n, k-r) : y ≤ x với x là phần tử nào đó của A} • Với 1 ≤ r ≤ n − k, bóng trên cấp r của x là tập hợp ∇r x = {y ∈ B(n, k+r) : x ≤ y} • Với 1 ≤ r ≤ n − k, bóng trên cấp r của tập A là tập hợp ∇r A được ¡ ¢ xác định theo công thức quy nạp ∇1 A = ∇A và ∇r+1 A = ∇ ∇r A . Khi đó ∇r A là bóng trên của A ở mức thứ k + r. ∇r A = {y ∈ B(n, k+r) : x ≤ y với x là phần tử nào đó của A} Ta có các tính chất cơ bản về bóng của tập hợp trong B(n, k) như sau S S 1. ∆r A = x∈A ∆r x và ∇r A = x∈A ∇r x 2. Với x = εn εn−1 . . . ε1 ∈ B(n, k), các phần tử của ∇r x được tạo ra từ x bằng cách giữ nguyên k thành phần bằng 1, thay r trong số ¡ ¢ n − k thành phần bằng 0 bởi r số 1. Như vậy |∇r x| = n−k r . Các phần tử của ∆r x được tạo ra từ x bằng cách giữ nguyên n−k thành phần bằng 0, thay r trong số k thành phần bằng 1 bởi r ¡¢ số 0. Như vậy |∆r x| = kr .
I.3.Quan hệ giữa vành B(n) và vành P(S) 9 I.3 Quan hệ giữa vành B(n) và vành P(S) Vành B(n) và vành P(S) có mối liên hệ rất chặt chẽ với nhau, chúng ta hãy xét một số tính chất tương ứng của hai vành này: 1) Với mỗi tập A ∈ P(S), ta xác lập dãy ngược a = εn εn−1 . . . ε1 bằng cách lấy εi = 1 nếu i ∈ A và εi = 0 nếu i ∈ / A. Dãy ngược a xác định như trên là một phần tử của B(n) và được gọi là phần tử đại diện hay dãy đại diện của tập A trong B(n) . Như vậy, chúng ta có một tương ứng 1 − 1 giữa một tập con của n-tập S với một phần tử đại diện cho nó trong B(n) . Hơn nữa, ta cũng có một tương ứng 1 − 1 giữa một k-tập con của n-tập S với một phần tử đại diện hạng k của nó trong B(n, k). 2) Thứ tự nén các k-tập con của S trong Pk (S) tương ứng với thứ tự từ điển các phần tử hạng k trong B(n, k). Thật vậy, xét các k-tập con A, B ∈ Pk (S) mà các phần tử đại diện của chúng trong B(n, k) lần lượt là a = εn εn−1 . . . ε1 và b = ε0n ε0n−1 . . . ε01 . Khi đó ta có : A
Chương II Biểu diễn k-nhị thức và Bóng của đoạn đầu Từ những tính chất của vành Bul hữu hạn B(n) và P(S), chúng ta tiếp tục xem xét một số vấn đề cơ bản của lý thuyết Combinatorial trên B(n, k)và Pk (S) sau đây: • Cho A ∈ Pk (S), xác định vị trí của A trong sự sắp xếp Pk (S) dưới thứ tự nén. Một cách tương ứng, cho a = εn εn−1 . . . ε1 là phần tử hạng k của B(n) , xác định vị trí của a trong sự sắp xếp các phần tử của B(n, k) dưới thứ tự từ điển. • Xác định k-tập con A của n-tập S khi biết vị trí m của A trong sự sắp xếp Pk (S) dưới thứ tự nén. Một cách tương ứng, xác định phần tử a = εn εn−1 . . . ε1 ∈ B(n, k) khi biết vị trí m của nó trong sự sắp xếp các phần tử của B(n, k) dưới thứ tự từ điển. Mặt khác, vị trí m của A ∈ Pk (S) trong sự sắp xếp các phần tử của Pk (S) dưới thứ tự nén cũng chính là độ lớn của tập hợp gồm A và các tập con đầu tiên đứng trước A trong sự sắp xếp các phần tử của Pk (S) dưới thứ tự nén. Ngược lại, với số nguyên dương m cho trước, tập A ở vị trí m trong sự sắp xếp Pk (S) dưới thứ tự nén chính là tập đứng cuối cùng trong đoạn đầu tiên gồm m tập trong sự sắp xếp các phần tử của Pk (S) dưới thứ tự nén. Hiển nhiên những đặc điểm trên cũng được xác lập trên B(n, k) dưới thứ tự từ điển. Để thuận tiện cho việc trình bày các kết quả, ta đưa ra các khái niệm và ký hiệu sau :
II.1.Một số bài toán mở đầu 11 Với A ∈ Pk (S), khi đó đoạn đầu của Pk (S) được kết thúc bởi A là tập hợp Fk (A) gồm A và các tập con đầu tiên đứng trước A trong sự sắp xếp Pk (S) dưới thứ tự nén. Fk (A) = {B ∈ Pk (S) : B ≤S A} Tương tự, với dãy a = εn εn−1 . . . ε1 ∈ B(n, k), ta gọi đoạn đầu của B(n, k) được kết thúc bởi a là tập hợp Fk (a) gồm a và các dãy đầu tiên đứng trước a trong sự sắp xếp B(n, k) dưới thứ tự từ điển. Fk (a) = {b ∈ B(n, k) : b ≤L a} Cuối cùng, với số nguyên dương m, ta ký hiệu Fk (m) là đoạn đầu gồm m phần tử của B(n, k) hoặc Pk (S). Cùng với hai vấn đề trên là các kết quả liên quan đến bóng cùa tập hợp. Trước hết ta xem xét bóng của một đoạn đầu qua việc giải quyết các vấn đề sau: 1. Bóng của một đoạn đầu có phải là một đoạn đầu không? 2. Xác định độ lớn của bóng của một đoạn đầu. 3. Đánh giá độ lớn của bóng của một đoạn đầu với độ lớn của bóng của một tập hợp bất kỳ mà tập hợp đó có cùng độ lớn với đoạn đầu đang xét. II.1 Một số bài toán mở đầu Bài toán 1: Cho A = {4, 5, 6, 7} xác định vị trí của A trong sự sắp xếp P4 (S) dưới thứ tự nén. Giải: Theo Tính chất 2, mục I.1.2 ta chỉ cần xét n = max A = 7, khi đó S = {1, 2, . . . , 7}. Dãy đại diện của A là a = 1111000 ∈ B(7, 4). Hiển nhiên a là dãy cuối cùng trong sự sắp xếp các phần tử của B(7, 4) dưới thứ tự từ điển. Vậy vị trí của A là: µ ¶ 7 m = |F4 (A) | = |F4 (a) | = | B(7, 4)| = 4
II.1.Một số bài toán mở đầu 12 Ta có nhận xét rằng : Dãy 11 . . . 1} 00 | {z . . . 0} là dãy đứng ở vị trí cuối | {z r s cùng trong sự sắp xếp các phần tử của B(r+s, r) dưới thứ tự từ điển, ¡ ¢ do đó, vị trí của dãy này là m = |B(r+s, r)| = r+s r . Bài toán 2: Cho A = {1, 3, 5, 6, 8} xác định vị trí của A trong sự sắp xếp P5 (S) dưới thứ tự nén. Giải: Theo Tính chất 2, mục I.1.2 ta chỉ cần xét n = max A = 8, khi đó S = {1, 2, . . . , 8}. Dãy đại diện của A là a = 10110101 ∈ B(8, 5). Để xác định m = |F5 (a) | ta đếm số các dãy đứng trước a trong sự sắp xếp B(8, 5) dưới thứ tự từ điển, cho đến khi gặp a: • Trước hết là các dãy đứng đầu tiên của B(8, 5) , chúng được bắt ¡¢ đầu bởi số 0, các dãy này có dạng 0ε7 ε6 ε5 ε4 ε3 ε2 ε1 . Có 75 dãy như thế. • Tiếp theo là các dãy có dạng 10ε6 ε5 ε4 ε3 ε2 ε1 , chúng được bắt đầu bởi 10. So sánh với a = 10110101, ta cần xác định vị trí của a1 = 110101 trong sự sắp xếp B(6, 4) dưới thứ tự từ điển. Trở lại lập luận ban đầu đối với a1 = 110101 ∈ B(6, 4) ta có: • Các dãy đứng đầu tiên của B(6, 4) được bắt đầu bởi 0, chúng có ¡¢ dạng 0ε5 ε4 ε3 ε2 ε1 . Có 54 dãy như thế. • Tiếp theo là các dãy có dạng 10ε4 ε3 ε2 ε1 , chúng được bắt đầu bởi ¡¢ 10. Có 43 dãy như thế. • Các dãy tiếp theo được bắt đầu bởi 110, chúng có dạng 110ε3 ε2 ε1 . So sánh với a1 = 110101, ta cần xác định vị trí của a2 = 101 trong sự sắp xếp B(3, 2) dưới thứ tự từ điển. Trở lại lập luận trên đối với a2 = 101 ∈ B(3, 2) ta có: • Các dãy đứng đầu tiên của B(3, 2) được bắt đầu bởi 0, chúng có ¡¢ dạng 0ε2 ε1 . Có 22 dãy như thế. • Tiếp theo là các dãy có dạng 10ε1 , chúng được bắt đầu bởi 10. So sánh với a2 = 101, ta cần xác định vị trí của a3 = 1 trong sự
II.1.Một số bài toán mở đầu 13 sắp xếp B(1, 1) dưới thứ tự từ điển. Hiển nhiên vị trí của a3 = 1 ¡¢ trong sự sắp xếp B(1, 1) dưới thứ tự từ điển là 11 . Quá trình đếm kết thúc. Vậy vị trí của A là : µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ 7 5 4 2 1 m= + + + + = 32 5 4 3 2 1 Bài toán 3: Cho A = {3, 4, 5, 6, 9} xác định vị trí của A trong sự sắp xếp P5 (S) dưới thứ tự nén. Giải: Theo Tính chất 2, mục I.1.2, ta chỉ cần xét n = max A = 9, khi đó S = {1, 2, . . . , 9}. Dãy đại diện của A là a = 100111100 ∈ B(9, 5). Theo lập luận của Bài toán 2 ta có: • Các dãy đứng đầu tiên của B(9, 5) được bắt đầu bởi 0, chúng có ¡¢ dạng 0ε8 ε7 ε6 ε5 ε4 ε3 ε2 ε1 . Có 85 dãy như thế. • Các dãy tiếp theo được bắt đầu bởi 10, so sánh với a = 100111100, ta cần xác định vị trí của a1 = 111100 trong sự sắp xếp B(6, 4) ¡¢ dưới thứ tự từ điển. Theo Bài toán 1 vị trí đó là 64 . Vậy vị trí của A là µ ¶ µ ¶ 8 6 m= + = 71 5 4 Đến đây, ta có thể thấy phương pháp giải quyết trong Bài toán 2 và Bài toán 3 phương pháp "bóc" dần các số 1 trong dãy εn εn−1 . . . ε1 , từ trái sang phải, cho đến khi gặp dãy dạng 11 . . . 1} 00 | {z . . . 0}. Vị trí của | {z r s dãy dạng này đã được xác định theo nhận xét của Bài toán 1. Các bài toán trên hình thành cho ta ý tưởng để giải quyết vấn đề thứ nhất bằng phương pháp "bóc" dần các số 1 trong dãy εn εn−1 . . . ε1 , từ trái sang phải. Vị trí m được biểu diễn dưới dạng tổng của các số tổ hợp. Câu hỏi đặt ra là ta có thể giải quyết vấn đề thứ hai bằng cách "đi ngược" lời giải của các bài toán trên không? Để "đi ngược " phương pháp trên, trước hết ta xem xét sự biểu diễn số nguyên dương m thành tổng các số tổ hợp qua khái niệm biểu diễn k-nhị thức của một số.
II.2.Biểu diễn k-nhị thức của một số 14 II.2 Biểu diễn k-nhị thức của một số Định lý II.2.1. Cho các số nguyên dương m và k, khi đó có một sự biểu diễn duy nhất số m dưới dạng: µ ¶ µ ¶ µ ¶ ak ak−1 at m= + + ··· + (II.1) k k−1 t trong đó ak > ak−1 > · · · > at ≥ t ≥ 1 Công thức (II.1) gọi là biểu diễn k-nhị thức của m. Chứng minh. Ta luôn luôn chọn được số nguyên dương ak lớn nhất ¡ ¢ sao cho akk ≤ m. Nói cách khác: ∃ak ∈ Z, ak ≥ 1 thỏa mãn µ ¶ µ ¶ ak 1 + ak ≤m< k k ¡ ¢ Nếu akk < m thì ∃ak−1 ∈ Z, ak−1 ≥ 1 thỏa mãn µ ¶ µ ¶ µ ¶ ak−1 ak 1 + ak−1 ≤m− < k−1 k k−1 Giả sử ak ≤ ak−1 , khi đó µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ ak ak−1 ak ak 1 + ak m≥ + ≥ + = k k−1 k k−1 k Điều này trái với cách chọn ak . Do đó ak > ak−1 . Tiếp tục quá trình trên sau hữu hạn bước ta sẽ chọn được số nguyên dương at với t > 1 sao cho µ ¶ µ ¶ µ ¶ µ ¶ at ak ak−1 at+1 =m− − − ··· − t k k−1 t+1 trong đó ak > ak−1 > · · · > at ≥ t > 1. Hoặc chọn được số nguyên dương a1 sao cho µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ a1 ak ak−1 a2 1 + a1 ≤m− − − ··· − < 1 k k−1 2 1
II.2.Biểu diễn k-nhị thức của một số 15 Nhưng khi đó µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ ak ak−1 a2 a1 1 + a1 a1 0 ≤ m− − −· · ·− − < − =1 k k−1 2 1 1 1 Vậy µ ¶ µ ¶ µ ¶ ak ak−1 a1 m= + + ··· + k k−1 1 trong đó ak > ak−1 > · · · > a2 > a1 ≥ 1. Bây giờ ta chứng minh sự biểu diễn số m theo công thức (II.1) là duy nhất bằng lý luận quy nạp như sau: ¡ ¢ Với k = 1 thì m = m1 là biểu diễn duy nhất của m theo công thức (II.1). Giả sử ta đã chứng minh được sự biểu diễn m theo công thức (II.1) là duy nhất đến k = l − 1, (l ≥ 2). Xét k = l và giả sử rằng m được biểu diễn theo công thức (II.1) dưới 2 dạng sau : µ ¶ µ ¶ µ ¶ al al−1 at m = + + ··· + , al > · · · > at ≥ t ≥ 1 l l−1 t µ ¶ µ ¶ µ ¶ bl bl−1 br m = + + ··· + , bl > · · · > br ≥ r ≥ 1 l l−1 r Nếu al 6= bl thì ta có thể giả sử al < bl . Khi đó µ ¶ µ ¶ µ ¶ al al−1 at m= + + ··· + l l−1 t µ ¶ µ ¶ µ ¶ µ ¶ al al − 1 al − l + t al − l + 1 ≤ + + ··· + + ··· + l l−1 t 1 µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ 1 + al al − l 1 + al 1 + al bl = − = −1< ≤ ≤m l 0 l l l Điều mâu thuẫn này chứng tỏ không thể xảy ra trường hợp al 6= bl . ¡ ¢ ¡ ¢ ¡ ¢ Từ đó suy ra al = bl , nhưng khi đó ta có all = bll và m − all có 2 biểu diễn (l − 1)-nhị thức, theo giả thiết quy nạp, ta suy ra ai = bi với mọi i. Vậy biểu diễn k-nhị thức của m theo công thức (II.1) là duy nhất. ¥