Permutations of Rides & Vehicles

permutations.py

import itertools
import math

# https://www.wolframalpha.com/input/?i=1,6,90,2520,113400
# a(n) = (2n)! / 2^n
# https://oeis.org/A000680
def f(n):
    return math.factorial(2 * n) / (2 ** n)

def brute():
    for n in range(6):
        x = range(n) * 2
        p = list(itertools.permutations(x))
        q = set(p)
        print n, len(p), len(q)

def formulaic():
    # 33 rides => more permutations than # of atoms in universe
    for n in range(20):
        print n, f(n)

def g(nrides, nvehicles):
    vehicles = range(nvehicles)
    r = 0
    for assignment in itertools.product(vehicles, repeat=nrides):
        p = 1
        for vehicle in vehicles:
            p *= f(assignment.count(vehicle))
        # print assignment, p
        r += p
    return r

# 2 vehicles: https://oeis.org/A034405
def main():
    values = []
    for rides in range(1, 9):
        for vehicles in [2]:
            result = g(rides, vehicles)
            print vehicles, rides, result
            values.append(result)
    print ','.join(map(str, values))

if __name__ == '__main__':
    main()