3. Bây giờ xét một hoán vị của [n] có dạng (a
1, a
2, . . . , a
n). Ta đánh dấu các đoạn cung tròn bởi các
số a
i như hình vẽ ban đầu. Mỗi một tập của F xem như là một k_cung của hoán vị này. Theo
kết quả trên, thì với một hoán vị này ta có ≤ k các k_cung.
• Lấy tổng hết tất cả các hoán vị [n] trên đường tròn, có (n − 1)! hoán vị, thì ta thấy có nhiều
nhất là k(n − 1)! các tập như thế này.
• Tuy nhiên, khi sắp xếp trên đường tròn và trong cách đếm trên, tập A
1được đếm làm nhiều
lần (vì sắp xếp trên đường tròn, thì tập A
1 hay bất kỳ tập nào lấy để làm thứ tự là giống
nhau). Vì trong nhiều lần hoán vị của (n − 1)!, sẽ tạo ra những hoán vị khác nhau, nhưng
phần tử của A
1 vẫn như vậy. Do đó có k! cách sắp xếp các phần tử của A
1 và (n − k)! cách
sắp xếp các phần tử bù của tập A
1. Do đó
| F | k!(n − k)! ≤ k(n − 1)!
n − 1
⇒ | F | ≤ k(n − 1)!
.
k!(n − k)! =
k − 1
Định lý 1.4 (Bollobas). Cho A
1, A
2, . . . , A
m và B
1, B
2, . . . , B
m là các tập con của S = [n]. Đặt a
i= | A
i|
và b
i= | B
i| với mọi i = 1, 2, . . . , m. Giả sử A
i∩ B
j= /0 khi và chỉ khi i = j. Khi đó
a
i+ b
i−1∑
m≤ 1.
a
ii=1Chứng minh. 1. Với mỗi hoán vị trong số n! hoán vị các phần tử của S, ta nói một hoán vị π là
chứa B sau A nếu tất cả các phần tử của A đều đứng trước các phần tử của B trong π .
Bạn đang xem 3. - Chuyên đề Toán chuyên
