# Content of a Discrete Hyper Pyramid¶

We like to compute the number of possibilities $$P(n, N)$$ for $$x = (x_1, \ldots x_n)$$ such that

$\begin{split}x_i &\in \{0,1,\ldots, N\} \quad \text{and}\\ \sum_i x_i &\leq N.\end{split}$

It is easy to see that $$P(n, N)$$ satisfies the recursion:

$P(n, N) = \sum_{i=0}^N P(n-1, N-i)$

with boundary conditions

$P(1, N) = N+1$

for all $$N$$. Note that this condition can be replaced by $$P(0, N) = 1$$ for all $$N$$.

First the memoize decorator.

#sys.setrecursionlimit(1500)
def memoize(f, cache={}):
def g(*args):
key = ( f, tuple(args) )
if key not in cache:
cache[key] = f(*args)
return cache[key]
return g


Now we can code $$P(N,n)$$ in just one line.

@memoize
def P(n, N):
return (n==0) or sum( P(n-1, N-i) for i in range(N+1) )


An Example

n=5
N=80
print P(n, N)

32801517