Calculating the number of all the possible decreasing sequences made from a set of points?

Question

Forgive my english, not native, but here it goes:

We are given several values: {a1, a2, a3... ai}

We can create the point Ai only if the sum of its non-negative integer coordinates xi+yi = ai

We also define a decreasing sequence if for each 2 points - Ai(xi, yi) and A(i+1) (x(i+1), y(i+1)), we have xi ≤ x(i+1) and yi ≥ y(i+1). (see image below)

Sequence example

Example:

a1 = 4

a2 = 5

a3 = 3

This should give us 10 possible decreasing sequences.

How could I calculate this? Thank you.

Answer 1

Let $f(k,x)$ be the number of integer sequences $x_1,x_2,\ldots, x_k$ with

• $0\le x_1\le x_2\le\ldots\le x_k=x$
• $a_1-x_1\ge a_2-x_2\ge\ldots \ge a_k-x_k\ge 0$

You want to calculate $\sum_{x=0}^{a_i}f(i,x)$. You may achieve this by using the recursion $$f(k+1,x)=\begin{cases}0&\text{if }x>a_{k+1}\\\sum_{j=0}^{x} f(k,j)&\text{if} x\le a_{k+1}\le a_k\\ \sum_{j=0}^{x+a_k-a_{k+1}} f(k,j)&\text{otherwise} \end{cases} $$