Given the set of elements $\{a_1 \dots a_n\}$ and $\{b_1 \dots b_n\}$
How many permutations of all $2n$ elements are there such that $a_i$ is to the left of $b_j$ for all $i \leq j$?
$n=1$ gives $1$ permutation
$\{a_1, b_1\}$
$n=2$ gives $5$ permutations
$\{a_1,a_2,b_2,b_1\}$,
$\{a_1,a_2,b_1,b_2\}$,
$\{a_1,b_1,a_2,b_2\}$,
$\{a_2,a_1,b_1,b_2\}$,
$\{a_2,a_1,b_2,b_1\}$
$n=3$ gives $57$ permutations
$n=4$ gives $1145$ permutations
$n=5$ gives $35505$ permutations
$n=6$ gives $1566813$ permutations
$n=7$ gives $93109737$ permutations (7 hours to calculate)
$n=8$ gives $7158444465$ permutations (Jaap Scherphuis)
This sequence is not yet on OEIS, so I have been unable to look up a formula.
Does appear in A276837 in column n row 2n
Thanks in advance for any help,
Ben Crossley
Best Answer
Let $f(n,k)$ be the number of such permutations on two sets of $n$ elements where the rightmost element $a_i$ from the first set is at position $k$.
Clearly, for any $n>0$, $f(n,k)>0$ only if $n\le k<2n$.
By considering the possible positions of each new pair $(a_n,b_n)$, you will find that $$f(n,k)=(2n-k)\cdot k\cdot f(n-1,k-1)+(2n-k)\sum_{i=n-1}^{k-2} f(n-1,i)$$
Let $f(n)=\sum_k f(n,k)$. Using the recurrence above, I got the following values:
$f(1)=1\\ f(2)=5\\ f(3)=57\\ f(4)=1145\\ f(5)=35505\\ f(6)=1566813\\ f(7)=93109737\\ f(8)=7158444465\\ f(9)=690665206113\\ f(10)=81648757479285\\ f(11)=11600465117974425\\ f(12)=1949518933483370409\\ f(13)=382385860587332190225\\ f(14)=86548201546165179374925\\ f(15)=22384061540470612338958665\\ f(16)=6558992881564560855032903265\\ f(17)=2161200782586444088187793593025\\ f(18)=795476007328144767489928007834085\\ f(19)=325131395894891669468123689359576825\\ f(20)=146784397748821461094492189898168139225\\$