Permutations containing a given subsequence Let $f(n)$ denote the number of $4n$-long strings formed from $2n$ a's and $2n$ b's, such that the string contains, as a (possibly non-consecutive) subsequence, a pattern containing $n$ a's and $n$ b's.  (Note that $f(n)$ doesn't depend on the pattern, so two possible patterns would be
$$\overbrace{\strut a\cdots a}^{n\textrm{ times}}\, \overbrace{\strut b\cdots b}^{n\textrm{ times}}\quad\textrm{ or }\quad \overbrace{abab\cdots ab}^{n \textrm{ pairs}}.)$$
In the notation of this post, this number is $\left[\begin{array}{c}2n,2n\\n,n\end{array}\right]$.
By using the first pattern, and summing over the number of b's which occur before the $n$-th a, we find that
$$(*)\quad f(n)= \sum_{r=0}^n \binom{n+r-1}{r}\binom{3n-r}{n}.$$
The resulting sequence is $$1, 5, 53, 662, 8885, 124130, 1778966, 25947612, 383358645, \ldots$$
which appears in OEIS as A036910, where we find a nice closed form for the $n$-th term:
$$(**)\quad\frac12\left(\binom{4n}{2n}+\binom{2n}{n}^2\right).$$
The WZ-pair machinery should prove that $(*)$ and $(**)$ are equal, so that's not a concern.  My question: is there a straightforward combinatorial argument which gives the count $(**)$ directly (i.e., not as the result of evaluating a sum)?
The closed form suggests the cycle index formula for an involution, but I'm not seeing an answer along those lines.
 A: In the following we consider without loss of generality the string $a^nb^n$ of length $2n$, which is a shorthand for
\begin{align*}
\overbrace{\strut a\cdots a}^{n\textrm{ times}}\, \overbrace{\strut b\cdots b}^{n\textrm{ times}}
\end{align*}

We show the number of strings of length $4n$ with  $2n$ $a$'s and  $2n$ $b$'s  containing the (not  necessarily  contiguous) subsequence $a^nb^n$ is
  \begin{align*}
\frac{1}{2}\left[\binom{4n}{2n}+\binom{2n}{n}^2\right] \tag{1}
\end{align*}

The number of possibilities to select $2n$ positions out of $4n$ to place the string $a^nb^n$ is
\begin{align*}
\binom{4n}{2n}
\end{align*}
The other $2n$ positions can be freely placed by the other $n$ a's and $n$ b's. 

First step: In order to count each valid string not more than once, we have to respect symmetries.
Therefore we count only those patterns out of the $\binom{4n}{2n}$ strings where we place no $b's$  at the left half. In other words, we count those patterns with less or equal $n$ positions selected on the left half.
Since we have $n$ $a$'s and $n$ $b$'s in reserve, we can always fill positions on the left half with $b$'s from the reserve accordingly, correspondingly to the patterns out of the $\binom{4n}{2n}$ selections with $k>n$ positions on the left side.
This leads nearly to
  \begin{align*}
\frac{1}{2}\binom{4n}{2n}\tag{2}
\end{align*}
The formula (2) correctly counts the cases with $0\leq k <n$ $a$'s at the left half, but not the case with $k=n$ $a's$.
Second step: We have additionally the special case with $k=n$ $a$'s to consider.
In all other cases, whenever we consider $0\leq k<n$ $a$'s on the left hand, we have the pendant of $n$ $a$'s and $n-k$ $b$'s on the left hand giving $\binom{2n}{k}=\binom{2n}{n-k}$ possibilities. But, in case of $k=n$ $a$'s we have to 
  count each occurrence with $n$ $a$'s on the left side without cut them in halves. The number of all valid strings with exactly $n$ $a$'s at the left side and $n$ $b$'s at the right side is
  \begin{align*}
\binom{2n}{n}^2
\end{align*}
  Since half of  these possibilities is already counted by (2) we have to add the other half $\frac{1}{2}\binom{2n}{n}^2$ and so we finally see that the claim (1) is valid.

Note: The combinatorial interpretation is based upon the binomial identity
\begin{align*}
\sum_{k=0}^{2n}\binom{2n}{k}^2=\binom{4n}{2n}
\end{align*}
and the symmetry
\begin{align*}
\binom{4n}{2n}&=\sum_{k=0}^{n-1}\binom{2n}{k}\binom{2n}{2n-k}+\binom{2n}{n}^2+\sum_{k=n+1}^{2n}\binom{2n}{k}\binom{2n}{2n-k}\\
&=2\sum_{k=0}^{n-1}\binom{2n}{k}^2+\binom{2n}{n}^2\\
\end{align*}
from which
\begin{align*}
\sum_{k=0}^{n-1}\binom{2n}{k}^2&=\frac{1}{2}\left[\binom{4n}{2n}-\binom{2n}{n}^2\right]\\
\text{and}\\
\sum_{k=0}^{n}\binom{2n}{k}^2&=\frac{1}{2}\left[\binom{4n}{2n}+\binom{2n}{n}^2\right]\\
\end{align*}
follow.
A: Here's a direct counting argument.  Let $S$ be the set of permutations of the word $a^{2n}b^{2n}$.  For any word $w\in S$, and for any pattern $p$, write $w\vdash p$ to mean that $w$ contains $p$ as a subsequence.
Set $A=\{w\in S\mid w\vdash a^nb^n\}$ and
$B=\{w\in S\mid w\vdash b^n a^n\}=\{w\in S\mid \bar w\vdash a^n b^n\}$; note
$$|A|=|B|=\left[\matrix{2n,2n\\n,n}\right].$$
The key observation is that $A\cup B=S$; that is, for any $w\in S$, at least one of $\{w,\bar w\}$ contains $a^n b^n$ as a subsequence.  (To see this, let $a_i$ and $b_i$ be the position of the $i$-th occurrence of $a$ and $b$ in $w$ respectively.  If $w\not\vdash a^nb^n$, then there are at most $n-1$ $b$'s after the $n$-th $a$, so $b_{n+1}<a_n$, hence $w\vdash b^{n+1}a^{n+1}$ and in particular $\bar w\vdash a^nb^n$.)
Hence
$$2\left[\matrix{2n,2n\\n,n}\right]=|A|+|B|=|A\cup B|+|A\cap B|=|S|+|A\cap B|.$$
We claim $A\cap B$ consists precisely of the words in which both the first and last half contain exactly $n$ $a$'s and $n$ $b$'s. (To see this, note that $w\in A\cap B$ iff $b_{n+1}>a_n \textrm{ and } a_{n+1}>b_n$, so $b_{n+1}\ge 2n+1$ and $a_{n+1}\ge 2n+1$.  This implies that the second half of $w$ contains at least $n$ $a$'s and $n$ $b$'s, so the characterization follows.)  It follows that $|A\cap B|={\binom{2n}n}^2$.  Since $|S|=\binom{4n}{2n}$, we're done.
Remark. This argument can be cast in terms of the cycle index formula as well.  Define an action of ${\Bbb Z}_2$ on $S$ via the involution $\iota:S\to S$ sending $w\mapsto w$ if $w\in A\cap B$, and $w\mapsto\bar w$ otherwise.  The observation above says that each ${\Bbb Z}_2$-orbit contains exactly one $w$ such that $w\vdash a^nb^n$.  Then the number of ${\Bbb Z}_2$-orbits on $S$ is
$$\left[\matrix{2n,2n\\n,n}\right]=
   \frac12\left(|\textrm{Fix}(\textrm{id})|+|\textrm{Fix}(\iota)|\right)
   =\frac12\left(|S|+|A\cap B|\right).
$$
