, 2009

If $p = r = 0$, we have $A = \emptyset$ so that $\mu(A) = 0$. In this case $T(0,0) = \{\emptyset\}$ and $|T(0,0)| = 1$, which agrees with the formula.

Assume $p \ge r \ge 1$. Add two two dummy vertices $0$, $n+1$ to $P$ such that $0$ is joined to $1$ and $n$ is joined to $n+1$. Let
$$\Pi = (l_1, m_1, l_2, m_2, \dots, l_k, m_k, l_{k+1})$$
be an ordered $(2k+1)$-tuple of positive integers such that
$$l_1 + m_1 + l_2 + m_2 + \cdots + l_k + m_k + l_{k+1} = n + 2. \quad (*)$$
(Thus $\Pi$ is an ordered partition of $n+2$ into $2k+1$ parts.) We obtain a subset $A = A(\Pi)$ of $V$ from this as follows: starting from the left end of the sequence $\langle 0, 1, 2, \dots, n+1 \rangle$, we omit the first $l_1$ numbers; choose the next $m_1$ numbers; omit the next $l_2$ numbers; choose the next $m_2$ numbers and so on alternately. Finally, we omit the last $l_{k+1}$ numbers. (Observe, that $l_1 \ge 1$ and $l_{k+1} \ge 1$ implies that the dummy vertices $0$ and $n+1$ are not used at all.) The union of $k$ chosen sets of numbers consisting of $m_1, m_2, \dots, m_k$ elements respectively is defined as $A$. We see that $A \subseteq \{1, 2, 3, \dots, n\}$. Conversely, any $A \subseteq \{1, 2, 3, \dots, n\}$ gives rise to an ordered $2k+1$ tuple of positive integers in a unique way; since $0 \notin A$ and $n+1 \notin A$, we have $l_1 \ge 1$ and $l_{k+1} \ge 1$. Since the $l$'s are positive, we see that $G(A)$ has $k$ components of vertex sizes $m_1, m_2, \dots, m_k$. If $u$ of these $k$ numbers, say, $m_{i_1}, m_{i_2}, \dots, m_{i_u}$ are odd and the remaining $v$ numbers, say, $m_{j_1}, m_{j_2}, \dots, m_{j_v}$ are even, $0 \le u, v \le k$, then $u+v=k$, and $O(G(A)) = u$. Thus $\mu(A) = m_1 + m_2 + \cdots + m_k + u$. We count $A$ for which $\mu(A) = 2r$, $1 \le r \le n$. Let $m_{i_1}, m_{i_2}, \dots, m_{i_u}$ be respectively equal to $2m'_{i_1} - 1, 2m'_{i_2} - 1, \dots, 2m'_{i_u} - 1$ and $m_{j_1}, m_{j_2}, \dots, m_{j_v}$ be equal to $2m'_{j_1}, 2m'_{j_2}, \dots, 2m'_{j_v}$. Then
$$\mu(A) = 2m'_{i_1} + 2m'_{i_2} + \cdots + 2m'_{i_u} + 2m'_{j_1} + 2m'_{j_2} + \cdots 2m'_{j_v} = 2r.$$
Thus we get
$$m'_{i_1} + m'_{i_2} + \cdots + m'_{i_u} + m'_{j_1} + m'_{j_2} + \cdots m'_{j_v} = r.$$
The number of positive solutions of this is $\binom{r-1}{k-1}$. Also we have
$$l_1 + l_2 + \cdots + l_{k+1} = n + 2 - (2r - u) = n - 2r + u + 2.$$
The number of positive solutions to this is $\binom{n-2r+u+1}{k}$. Thus the number of positive solutions of $(*)$ with $\mu(A) = 2r$ is
$$\sum_{k \ge 1} \binom{r-1}{k-1} \binom{n-2r+u+1}{k}.$$
Since $p+u=2r$, we have
$$|T(p, r)| = \sum_{k \ge 1} \binom{r-1}{k-1} \binom{n-2r+u+1}{k} \binom{k}{u}.$$
as any $u$ of the $k$ $m$'s may be chosen to be odd and the rest even, giving rise to the factor $\binom{k}{u}$. Using
$$\binom{n}{k} \binom{k}{m} = \binom{n}{m} \binom{n-m}{n-k},$$
we get
$$\begin{align*} |T(p, r)| &= \binom{n-p+1}{u} \sum_{k \ge 1} \binom{r-1}{k-1} \binom{n-p+1-u}{n-p+1-k} \\ &= \binom{n-p+1}{u} \binom{n-p-u+r}{n-p} \\ &= \binom{n-p+1}{2r-p} \binom{n-r}{n-p} \\ &= \binom{n-r}{p-r} \binom{n-p+1}{2r-p}; \end{align*}$$
where we have used Vander Monde identity.