# 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
```