LẤY TỔNG SỐ TẤT CÁC CÁC CHỈ SỐ I = 1, 2, . . . , M TA CÓ AI+ BI−1∑M...

4. Lấy tổng số tất các các chỉ số i = 1, 2, . . . , m ta có

a

+ b

∑

n!

≤ 1.

≤ n! ⇒

_i

_i

a

_i

Định lý được chứng minh.

Định nghĩa 1.5. Cho S là một tập hợp hữu hạn. Một họ các tập con A

, A

, . . . , A

của S được gọi là

một xích nếu

A

⊂ A

và | A

| = | A

| + 1 ∀ i = 1, 2, . . . , n.

Định nghĩa 1.6. Cho P là một tập hợp hữu hạn. Một họ các tập con A

, A

, . . . , A

của S được gọi là

một phản xích nếu

A

6⊂ A

, ∀ i 6 = j.

Định lý 1.7 (Bất đẳng thức LYM, Lubell, Yamamoto, Meshalkin). Cho F là một phản xích trong

[n] (ta dùng ký hiệu [n] thay cho { 1, 2, . . . , n } ). Khi đó ta có bất đẳng thức

n

∑

| A |

Chứng minh. 1. Gọi C là tập hợp tất cả các xích C, mỗi xích C gồm n tập hợp, mỗi tập hợp là một

tập con của [n] và đây là xích chứa nhiều phần tử nhất, C

⊂ C

⊂ . . . ⊂ C

, | C

| = i, ∀ i = 1, 2, . . . , n.

Hỏi C có bao nhiêu phần tử? (mỗi phần tử thuộc C là một xích độ dài n). Xét một xích C ∈ C

thì

• Có n cách chọn cho tập C

. Thật vậy, vì | C

| = 1 nên C

∈ {{ 1 } , { 2 } , . . . , { n }} .

• Với mỗi cách chọn tập C

, có n − 1 cách chọn tập C

. Thật vậy, minh họa cho C

= { 3 } , khi

đó

C

∈ {{ 3, 1 } , { 3, 2 } , { 3, 4 } , . . . , { 3, n }} .

• Cứ tiếp tục như vậy, ta có n − 2 cách chọn tập C

, n − 3 cách chọn tập C

, . . . và cuối cùng

là 1 cách chọn tập C

vì C

= [n].

Vậy C có n! phần tử.