CODEWITHSUNDEEP
algorithmcombinatoricsdiscrete-mathematics
TijuanaTaxi
TijuanaTaxi

Reputation: 121

Faster way of calculating how many ways can $2n$ elements be paired?

So the problem is in how many ways 2n elements can be paired, my approach was multiply all odd numbers less then 2n.

(2n-1)*(2n-3)*...*1

but my professor claimed it can be done much faster in algorithmic sense, but I don't really see the way to do so. Any hints? Thanks!

Upvotes: 0

Views: 514

Answers (2)

GALTIER Jerome
GALTIER Jerome

Reputation: 11

Basically you are calculating (2n)!/(n!2^n), because multiplicating all even numbers less or equal to 2n gives:

2n * (2(n-1)) * (2(n-2)) * ... * 2 = n!2^n

Algortithmically factorials can be computed in specific routines in almost constant times. One way to do it is to use the Stirling approximation formula (for large enough numbers)

n! ~ sqrt(2 pi n)(n/e)^n

Upvotes: 0

miku
miku

Reputation: 188084

Update: This is probably not what you are asking:

Your question rephrased: How many ways to choose two elements from a set of 2n elements? Also known as combination, the binomial coefficient or choice number and read "n choose k".

You can take the formula n! / (k! * (n - k)!), replace n by 2n and then simplify it algebraically to (2n - 1) * n:

#!/usr/bin/env python
# coding: utf-8

def pairs(n):
    return (2 * n - 1) * n

# there is only one pair for an 2n element set {0, 1}
print(pairs(1)) # prints 1

# pairs of {0, 1, 2, 3} = {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}
print(pairs(2)) # prints 6

Upvotes: 1

Related Questions