Câu hỏi 58
Cho $P$ là một đường đi trên tập đỉnh $V = \{1, 2, \dots, n\}$, trong đó $j$ được nối với $j+1$, $1 \le j \le n-1$. Với mỗi tập con $A \subset V$ và đồ thị con cảm sinh $G(A)$ của $P$, định nghĩa $\mu(A) = |A| + O(G(A))$, trong đó $O(G(A))$ là số thành phần liên thông của $G(A)$ có số đỉnh lẻ; $\mu(\emptyset) = 0$.
Đặt
$$
T(p, r) = \{ A \subset V \mid |A| = p, \mu(A) = 2r \},
$$
với $r \le p \le 2r$. Chứng minh rằng
$$
|T(p, r)| = \binom{n-r}{p-r} \binom{n-p+1}{2r-p}.
$$
(Ví dụ: Cho $V = \{1, 2, \dots, 9\}$ và $A = \{\{1, 2\}, \{4, 5, 6\}, \{9\}\}$. Khi đó $\mu(A) = 6+2=8$.)
Đặt
$$
T(p, r) = \{ A \subset V \mid |A| = p, \mu(A) = 2r \},
$$
với $r \le p \le 2r$. Chứng minh rằng
$$
|T(p, r)| = \binom{n-r}{p-r} \binom{n-p+1}{2r-p}.
$$
(Ví dụ: Cho $V = \{1, 2, \dots, 9\}$ và $A = \{\{1, 2\}, \{4, 5, 6\}, \{9\}\}$. Khi đó $\mu(A) = 6+2=8$.)