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