Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

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

share|improve this answer
    
How did you come up with that so quickly? Works like a charm, thanks a million. –  Patrick Lorio Mar 7 '13 at 7:52
    
The Central Binomial Coefficients $\binom{2n}{n}$ come up quite often in combinatorics. –  André Nicolas Mar 7 '13 at 7:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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