Tổ hợp Olympic

Đồ thị không tam giác không cho phép hai đỉnh kề nhau có chung một hàng xóm, nên tổng bậc của chúng bị chặn chặt bởi $n$; việc chia đỉnh thành hai nhóm gần bằng nhau rồi nối mọi cặp chéo sẽ bão hòa chặn này ở khắp nơi cùng lúc, đó là lý do đồ thị lưỡng phân đầy đủ cân bằng là ví dụ cực trị.

Ta quy nạp theo $n$. Với $n \le 2$ khẳng định là hiển nhiên vì $\lfloor n^2/4 \rfloor \ge 0$ và mọi đồ thị trên tối đa 2 đỉnh có tối đa 1 cạnh.

Giả sử khẳng định đúng với mọi đồ thị không tam giác trên ít hơn $n$ đỉnh, và cho $G$ là đồ thị không tam giác trên $n$ đỉnh. Nếu $G$ không có cạnh thì chặn hiển nhiên đúng, nên giả sử $G$ có một cạnh $uv$. Vì $G$ không có tam giác, $u$ và $v$ không có hàng xóm chung, tức $N(u) \cap N(v) = \varnothing$.

Vì $N(u)$ và $N(v)$ là các tập con rời nhau của tập $n$ đỉnh, $\deg(u)+\deg(v) = |N(u)|+|N(v)| = |N(u) \cup N(v)| \le n$.

Xóa $u$ và $v$ khỏi $G$ để được đồ thị không tam giác $G'$ trên $n-2$ đỉnh. Mỗi cạnh của $G$ hoặc là cạnh $uv$, hoặc là cạnh từ $u$ hay $v$ đến phần còn lại, hoặc là cạnh của $G'$; đếm cẩn thận ta có $e(G) = e(G') + \deg(u) + \deg(v) - 1$ (số hạng $-1$ điều chỉnh vì cạnh $uv$ được đếm một lần trong $\deg(u)+\deg(v)$ nhưng nó không phải cạnh của $G'$).

Theo giả thiết quy nạp $e(G') \le \lfloor (n-2)^2/4 \rfloor$, nên $e(G) \le \lfloor (n-2)^2/4 \rfloor + n - 1$. Tính trực tiếp cho $(n-2)^2/4 + n - 1 = n^2/4 - n + 1 + n - 1 = n^2/4$, và kiểm tra riêng trường hợp $n$ chẵn/lẻ cho thấy $\lfloor (n-2)^2/4 \rfloor + n - 1 \le \lfloor n^2/4 \rfloor$ đúng. Vậy $e(G) \le \lfloor n^2/4 \rfloor$, hoàn tất quy nạp.

Với trường hợp cực trị, đồ thị lưỡng phân đầy đủ với hai phần kích thước $\lfloor n/2 \rfloor$ và $\lceil n/2 \rceil$ không có tam giác (mọi tam giác cần một cạnh trong cùng một phần, nhưng không có cạnh nào như vậy) và có đúng $\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \lfloor n^2/4 \rfloor$ cạnh, nên chặn này chặt.

Cả hai vế đếm cùng một thứ — số cách chọn $n$ người trong $2n$ người — nên hoàn toàn không cần biến đổi đại số hệ số nhị thức, chỉ cần mô tả cẩn thận một quá trình chọn theo hai thứ tự khác nhau.

Xét một tập gồm $2n$ người, trong đó có $n$ nam và $n$ nữ. Ta đếm, theo hai cách, số cách chọn một ủy ban đúng $n$ người từ tập $2n$ người này.

Trực tiếp, theo định nghĩa, số này là $\binom{2n}{n}$, vì ta chỉ đơn giản chọn $n$ đối tượng trong $2n$.

Cách khác, chia mọi ủy ban hợp lệ theo số nam nó chứa. Nếu ủy ban chứa đúng $k$ nam, với một số $k$ nào đó thỏa $0 \le k \le n$, thì $k$ nam đó có thể chọn theo $\binom{n}{k}$ cách, và $n-k$ thành viên còn lại phải là nữ, chọn từ $n$ nữ theo $\binom{n}{n-k}$ cách. Theo đẳng thức đối xứng $\binom{n}{n-k} = \binom{n}{k}$, số ủy ban với đúng $k$ nam là $\binom{n}{k} \cdot \binom{n}{k} = \binom{n}{k}^2$.

Mọi ủy ban hợp lệ $n$ người đều có một số nam $k$ xác định giữa $0$ và $n$, và không ủy ban nào bị đếm hai lần ở các giá trị $k$ khác nhau, nên tổng theo mọi $k$ cho tổng số ủy ban là $\sum_{k=0}^{n} \binom{n}{k}^2$.

Vì cả hai biểu thức đếm đúng cùng một tập ủy ban, chúng phải bằng nhau: $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$.