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






$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

  • 1
    $\begingroup$ I get the same numbers as you, and $7158444465$ for $n=8$. $\endgroup$ – Jaap Scherphuis Nov 5 '18 at 12:05
  • 1
    $\begingroup$ These numbers occur in A276837 at column $n$, row $2n$. No formula is listed there. $\endgroup$ – Jaap Scherphuis Nov 5 '18 at 12:21

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\\$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.