Given, for example, the following set of integers $\{1,2,3,4\}$, how can you compute the number of all possible sequence scenarios, where a scenario consists of a number of sequences, as following ones^
scenario 1: $(1,2,3,4)$
scenario 2: $(1,4)(2,4)(3,4)$
scenario 3: $(1,4)(2,3,4)$
scenario 4: $(1,2,4)(3,4)$
scenario 5: $(1,3,4)(2,4)$
In general, given a set of $n$ integers, how many sequence scenarios you can create if a scenario is defined as a set of sequences such that:
- all integers from 1 to n-1 are used within a scenario exactly once.
- each sequence has n as the last integer
- in each sequence, integers are ordered with increasing ordering
- the ordering of the sequences is not relevant, it is important that no scenario is the same to any other
What would be a mathematical equation for computing a number of those scenarios? Or at least what could be an algorithm for their computing?
These are the Bell numbers, given in OEIS A000110. You are asking for the number of ways to partition $n-1$ labeled items into disjoint subsets. You then sort the subsets and append $n$ to each to get one of your scenarios. The sequence begins $$1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570$$ where the $5$ represents $B_3$ because you partition $\{1,2,3\}$ and there are $5$ ways to do it as you found. The recurrence for them is $$B_{n+1}=\sum_{k=0}^n{n \choose k}B_k$$