# Simplex number calculation (all dimensions) in python

How can I calculate simplex numbers in all dimensions?
Example:

dimension:     2|      3|      4|
simpl(1)       1|      1|      1|
simpl(2)       3|      4|      5|
simpl(3)       6|     10|     15|
simpl(4)      10|     20|     35|
simpl(5)      15|     35|     70|


First I considered about a recursive implementation (in python):

def simplex(n, dim):
if dim == 1:
return n
else:
i = 1
ret = 0
while i <= n:
ret += simplex(i, dim-1)
i+=1
return ret


The algorithm works, but because of the recursion its really slow, especially if your dimension number is 5 or higher.

You should use a for loop rather than a while loop to solve the problem. This is as you're just re-writing a for loop. Using a for loop you can change the loop to a comprehension, and take the sum of it. This allows you to get the code:

def simplex(n, dim):
if dim == 1:
return n
dim -= 1
return sum(simplex(i, dim) for i in range(1, n + 1))


However this can be simplified. When dim is the bullet point the function is:

1. $n$
2. $\Sigma_{i = 1}^{n} i$
$= \frac{n(n + 1)}{2}$
3. $\Sigma_{i = 1}^{n} (\Sigma_{j = 1}^{i} j)$
$= \frac{n(n + 1)(n + 2)}{6}$
4. $\Sigma_{i = 1}^{n} (\Sigma_{j = 1}^{i} (\Sigma_{k = 1}^{j} k)))$
$= \frac{n(n + 1)(n + 2)(n + 3)}{24}$
5. $\Sigma_{i = 1}^{n} (\Sigma_{j = 1}^{i} (\Sigma_{k = 1}^{j} (\Sigma_{l = 1}^{k} l))))$
$= \frac{n(n + 1)(n + 2)(n + 3)(n + 4)}{120}$

Since we're getting a pattern, we know that the top part of the fraction is:

$\Pi_{i = 0}^{dim - 1} n + i$

And if we use oeis to find the denominator it says it's probably the factorial sequence. And so it's likely:

$\frac{\Pi_{i = 0}^{dim - 1} n + i}{dim!}$

This is actually really easy to write in Python. And so you can get a significant speed up.

from functools import reduce
from math import factorial
from operator import mul

def simplex(n, dim):
return reduce(mul, (n + i for i in range(dim))) // factorial(dim)

• Good point, but I actually knew the iterative solution already at the time of asking the question (I just asked to share this in the community). As you can see, I answered the question too. I have two mentions to you: do you need the double Slash before factorial(dim)? and I like the while loop more than the for loop, because I expierienced weird things with the order of execution in for loops – Aemyl Sep 30 '16 at 5:41
• @Aemyl I didn't see your answer when I started and finished mine, but it was a thought provoking question, :). To answer your 'mentions', (1) You need either // or /, I chose // as it matches the functions range. (2) I don't know how I can help you like for loops, but I will not retract my encouragement for you to use them. As they objectively make the function much cleaner than the equivalent using a while. – Peilonrayz Sep 30 '16 at 8:28
• I didn't want you to retract your aspect of using for loops :) I just wanted to explain why I use while loops. – Aemyl Sep 30 '16 at 16:55
• consistency: spaces around operators (esp. +=) is not always the same, you should stick to a space before and a space after.
• conditions: since you return from your first if, you don't need the else clause. This saves an indentation level and help distinguish the general algorithm from the special case.
• iteration: you don't need a while loop with an explicit index. for loops are prefered in python.

for i in range(1, n + 1):
ret += simplex(i, dim - 1)

• additions: the sum builtin function should be faster than an explicit accumulation loop. You can combine it with a generator expression for better efficiency.

Overall, the code could be written:

def simplex(n, dim):
if dim == 1:
return n

return sum(simplex(i, dim-1) for i in range(1, n+1))


As regard to the efficiency part, since your are computing results for the lower dimensions several times, you may want to use some form of caching. Take a look at the several techniques of memoization.

• though for loops are prefered in python, I like while loops more then them, because in my opinion (and in python's) explicit is better than implicit. Another point is, I expierienced some really weird things with for loops (the order of iterating through list for example) – Aemyl Sep 30 '16 at 5:51
• @Aemyl Out of "use <name> as a variable to iterate over <stuff> and do …" and "check this <condition> before you do … over and over again"; I don't think the latter is more explicit when, well, iterating over some stuff. And I don't know what you are trying to do with your lists, but order of iteration is always consistent in a for loop. I’d understand if you said set or dict, but not list. – 301_Moved_Permanently Sep 30 '16 at 7:58
• sorry, I guess it was on dictionaries – Aemyl Sep 30 '16 at 16:53
• @Aemyl Then the arbitrary ordering is built into the language. If you want to be able to control it, you may want to have a look at collections.OrderedDict. – 301_Moved_Permanently Oct 1 '16 at 6:24

Fortunatly, there is a iterative variant based on a sum formula by Gauss (the Gauss formula is only for the 2nd dimension):

def fac(n):
i = 1
e = 1
while i <= n:
e*=i
i+=1
return e

def simplex(n, dim):
i = 0
ret = 1
while i < dim:
ret*=(n+i)
i+=1
ret /= fac(dim)
return ret