# Equation to find possible combinations of combining lists while retaining order

Lets say I have two ordered lists of size n, [A1, A2, ..., An] and [B1, B2, ...,Bn]. I want to find all the possible combinations of the two lists where the new lists has [A1, A2, ..., An] and [B1, B2, .., Bn] in the same order.

So the new list would have A(p - 1) before Ap and B(p - 1) before Bp. In simpler terms, A1 must be before A2, A2 before A3, B1 before B2, B2 before B3, and so on.

As an example lets have the two ordered lists be [a, b, c, d] and [1, 2, 3, 4]

A few acceptable combinations: [a, b, 1, 2, c, d, 3, 4], [1, 2, a, 3, b, 4, c, d], [a, 1, b, 2, c, 3, d, 4]
A few unacceptable combinations: [b, a, c, d, 1, 2, 3, 4], [a, 2, c, d, b, 1, 3, 4]


I found that I can solve this using recursion (python):

def combinations (first_list_size, second_list_size):
if first_list_size == 1 and second_list_size == 1:
return 2
if first_list_size == 0 or second_list_size == 0:
return 1
return combinations (first_list_size - 1, second_list_size) + combinations (first_list_size, second_list_size - 1)


So for the [a, b, c, d] and [1, 2, 3, 4] example the # of possible combinations is 70 (in python combinations(4, 4))

Here is a computed table

n combinations
2 6
3 20
4 70
5 252
6 924
7 3432
8 12870
9 48620
10 184756
11 705432
12 2704156
13 10400600


I am trying to find a algebraic function to find how many possible combinations, given the restrictions, two lists of n size will have. So f(n)=combinations

Any help would be much appreciated. Thanks in advance.

-

Make $2n$ slots in a row and choose $n$ of them for the $A$'s. We place the $A$'s in the chosen slots in the right order, and do the same thing with the remaining slots for the $B$'s. The number arrangements is therefore $\dbinom{2n}{n}$. This can be rewritten in various ways, such as $\dfrac{(2n)!}{n!n!}$.
The Central Binomial Coefficients $\binom{2n}{n}$ come up quite often in combinatorics. –  André Nicolas Mar 7 '13 at 7:58