MathLabs

Bài 6

Một hoán vị (x1,x2,…,x2n)(x_1,x_2,\ldots,x_{2n}) của {1,2,…,2n}\{1,2,\ldots,2n\} có tính chất PP nếu ∣xi−xi+1∣=n|x_i-x_{i+1}|=n với ít nhất một i∈{1,…,2n−1}i\in\{1,\ldots,2n-1\}. Chứng minh rằng với mọi số nguyên dương nn, số hoán vị có tính chất PP lớn hơn số hoán vị không có tính chất đó.
Bước 4 trên 5: Cắt công thức bao hàm–loại trừ
Bước trướcBước tiếp
Hiểu nôm na

Bao hàm–loại trừ chỉ cần hai lớp đầu để có cận dưới hữu ích.

∣A∣≥∑k∣Ak∣−∑k<l∣Ak∩Al∣=2n2(2n−2)!|A|\ge\sum_k|A_k|-\sum_{k<l}|A_k\cap A_l|=2n^2(2n-2)!
Phân tích chi tiết

Công thức bao hàm–loại trừ đầy đủ có các hạng luân phiên với độ lớn giảm dần, nên cắt sau các giao đôi cho ∣A∣≥∑k∣Ak∣−∑k<l∣Ak∩Al∣|A|\ge\sum_k|A_k|-\sum_{k<l}|A_k\cap A_l|. Thay Bước 2–3 vào được ∣A∣≥2n2(2n−2)!|A|\ge2n^2(2n-2)!.