3
$\begingroup$

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}

$\endgroup$
3
  • 1
    $\begingroup$ They may or may not have a special name, but there is a fairly straightforward way to describe them. These numbers are simply the number of ways of reaching a lattice point in a gridwalk where you cannot cross the $x=y$ line. $\endgroup$
    – zhuli
    Commented Mar 16, 2022 at 20:15
  • 1
    $\begingroup$ The fourth row seems to be OEIS sequence A002057. Searching for the third row also brings up results that might be relevant. $\endgroup$
    – joriki
    Commented Mar 16, 2022 at 20:40
  • 1
    $\begingroup$ If you read your table along the diagonals starting from the upper left corner you get $1,2,2,3,5,5,4,9,14,14,5,14,28,42$. This seems to be exactly OEIS A115126. You can find a closed form there. $\endgroup$
    – Fabius Wiesner
    Commented Mar 16, 2022 at 21:17

1 Answer 1

Reset to default
5
$\begingroup$

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}. $$

$\endgroup$
2
  • $\begingroup$ Thank you! In fact, I am counting preference rankings, so that checks out. Any suggestions on where to read more? $\endgroup$
    – elplatt
    Commented Mar 16, 2022 at 21:48
  • 1
    $\begingroup$ Well, the Wikipedia article on Bertrand's ballot theorem is good, and I think that Four proofs of the ballot theorem by Marc Renault is very interesting. There's also lots of relevant info on the OEIS for this sequence: oeis.org/A009766, with more sources. $\endgroup$
    – Mike Earnest
    Commented Mar 17, 2022 at 1:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .