TITLE: Generalized Catalan number satisfying recursive definition
QUESTION [3 upvotes]: Wondering if the numbers satisfying the following relationship have a name or known closed-form solution. They show up in enumerating possible configurations of swaps during the execution of a bubble sort.
\begin{equation}
F_{k,n} =
\begin{cases}
0 & \text{ k = 0} \\
k & \text{ n = 1} \\
F_{k-1,n} + F_{k+1,n-1} & \text{otherwise}
\end{cases}
\end{equation}
Note that $F_{1,n}$ is the nth Catalan number. The matrix of the first few numbers is:
\begin{array}
01&2&5&14\\
2&5&14&42\\
3&9&28&90\\
4&14&48&165\
\end{array}

REPLY [5 votes]: These are sometimes known as the ballot numbers. Imagine an election where candidate $A$ received $n+k$ votes, and candidate $B$ received $n$ votes. Then $F_{k,n}$ is the number of ways to order the ballots such that $A$ is strictly ahead of $B$ throughout the counting process when the ballots are counted in that order.
They are given by the explicit formula
$$
F_{k,n}=\binom{2n+k}{n}\frac{k}{k+2n}.
$$
{"set_name": "stack_exchange", "score": 3, "question_id": 4405023}