#!/usr/bin/env coffee
## This file is dedicated to the public domain.
## Count up duplicates in an array, and get a map where keys are
## set members, and values are the number of occurrences.
## Only works when all the duplicates are next to each other,
## which they are in count_open_toratopes where it's called.
map_dupes = (ar) ->
r = {}
last = num = null
for ari in ar
if ari is last
++num
else
r[last] = num if num?
last = ari
num = 1
r[last] = num if num?
r
choose = (n, k) ->
return 0 if k > n
return 1 if k < 1
return 1 if k is n
return n if k in [1, n-1]
# Optimise to avoid calculating factorials (and running into overflow issues),
# by only multiplying and dividing what we actually need to.
p = n-k
r = n
while --n > 1
if p < n > k
r *= n
else if p >= n <= k
r /= n
r
## List out all the partitions of n, only using parts between the specified minimum and maximum.
partitions = (n, min_part=1, max_part=null) ->
max_part ?= n
r = []
r.push [n] if n <= max_part
i = n - min_part
i = max_part if i > max_part
while i >= min_part
r.push ([i].concat x for x in partitions(n-i, min_part, i))...
--i
r
toratope_partitions = (n) -> partitions n, 2, n-2
## Number of open toratopes in n dimensions.
## Half the number of total toratopes in n dimensions.
## Same as http://oeis.org/A000669
count_open_toratopes = (n) ->
n = parseInt(n)
if n <= 2
1
else
sum = 2*count_open_toratopes(n-1)
for p in toratope_partitions n
prod = 1
for m, k of map_dupes p
prod *= choose(count_open_toratopes(m) + k - 1, k)
sum += prod
sum
console.log count_open_toratopes process.argv[2]