Question 58
Let $P$ be a path on the vertex set $V = \{1, 2, \dots, n\}$, where $j$ is joined to $j+1$, $1 \le j \le n-1$. For each subset $A \subset V$ and the induced subgraph $G(A)$ of $P$, define $\mu(A) = |A| + O(G(A))$, where $O(G(A))$ is the number of components of $G(A)$, each with an odd number of vertices; $\mu(\emptyset) = 0$.
Let
$$
T(p, r) = \{ A \subset V \mid |A| = p, \mu(A) = 2r \},
$$
for $r \le p \le 2r$. Prove that
$$
|T(p, r)| = \binom{n-r}{p-r} \binom{n-p+1}{2r-p}.
$$
(Example: Let $V = \{1, 2, \dots, 9\}$ and $A = \{\{1, 2\}, \{4, 5, 6\}, \{9\}\}$. In this case $\mu(A) = 6+2=8$.)
Let
$$
T(p, r) = \{ A \subset V \mid |A| = p, \mu(A) = 2r \},
$$
for $r \le p \le 2r$. Prove that
$$
|T(p, r)| = \binom{n-r}{p-r} \binom{n-p+1}{2r-p}.
$$
(Example: Let $V = \{1, 2, \dots, 9\}$ and $A = \{\{1, 2\}, \{4, 5, 6\}, \{9\}\}$. In this case $\mu(A) = 6+2=8$.)