A tuple is represented by $(a_i,a_{i-1},...,a_1)$ where $a_i<a_{i-1}$ and $i \in \{2...N\}$
So, valid tuples are $(1,2,3,4)$ and $(2,5,9,41)$
You are given the sum of these tuples
$a_i + a_{i-1} + \ldots +a_1 = S$
Can you compute in how many ways these tuples can be organized so that the order is increasing.
For example
If the sum is 5, then there are 2 ways to organize the tuples
$(1,4)$ and $(2,3)$
If the sum is 10, then there are 9 ways to organize the tuples
$(1,9)$, $(2,8)$, $(3,7)$, $(4,6)$, $(1,2,7)$, $(1,3,6)$, $(1,4,5)$, $(2,3,5)$ and $(1,2,3,4)$
Can you come up with any general formula to calculate that?
I was able to come with a recursive algorithm that generates all the sequences, however, it is too slow.
I believe that you are talking about a form of Partitions without repitition of individual numbers. What you can do in your case is calculate the number of tuples for an initial number. In your case, it would be $3$. From there, you calculate the number of partitions of order two as $\left\lfloor\frac n 2\right\rfloor-1$. You can calculate the number of partitions of order three by choosing a number $m$ and finding all partitions of $n-m$ such that all values used in the partition are greater than $m$. You continue on from there until you reach $k$ numbers in the tuple such that $n\geq\frac{k(k+1)}2$.