# Number of permutations? (2 groups of n elements with a condition)

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

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

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