Determining the number of nontrivial families of increasing substrings of $\{1,...,k\}$

Question

Let us say that we have the order $\{1,2,3,4,5,...,k\}$ of $k$ elements. Now, I want to determine in how many different ways can we pick a family of increasing substrings from $\{1,...,k\}$? The rules are the following:

1. We do not consider the trivial case of picking the entire $\{1,...,k\}$ as a whole.
2. We want to pick at least one increasing substring, but we can pick multiple different ones (such as if $k=5$ we can pick just $\{1,2\}$, but we may also pick $\{1,2\}$ and $\{3,4,5\}$, using the entire sequence and it would also be possible to pick something like $\{1,2\}$ and $\{3,4\}$).
3. The substrings may not overlap with one another (i.e. if for example $k=5$ we cannot have $\{1,2,3\}$ and $\{3,4\}$).
4. The increasing substrings must only consist of consecutive numbers (i.e. we cannot have anything like $\{1,3,4\}$).
5. A substring cannot be just one single number i.e. $\{1\}$.

So basically, we are curious about how many different combinations of these substrings we can have in total as families. An example would be, for the case of $k=4$ the following:

$\Big\{ \{1,2\}, \{1,2,3\}, \{2,3\}, \{3,4\}, \{2,3,4\}, \{\{1,2\}, \{3,4\}\} \Big\}$

so the number of families in this case would be $6$.

I have thought about it this way: if I have $\{1,...,k\}$ and enumerate them starting from only having one increasing substring such as $\{1,2\}$ or anything $\{1,...,j\}$ where $j \le k-1$. There are the total of $k-1$ of these.

Then we would enumerate any substrings of the length two on their own (minus 1 from the previous part), length three (minus 1 from the previous part), length $k-1$ (minus one from the previous part).

I believe how this is how we would do it for the case of considering only single substrings, but we also want to consider different combinations of multiple substrings, and I am not sure how to go about doing this.

Answer 1

This is the same as asking for the number of subsets of $\{1, \cdots, k\}$ with evenly many elements (not including the empty set or the set $\{1,k\}$). Indeed, we just pair the elements in the subset sequentially to get the first and last elements of your substrings. Thus, with $k=11$ the subset $\{3,6,7,11\}$ corresponds to the family $\{\{3,4,5,6\}, \{7,8,9,10,11\}\}$.

In general there are $2^{k-1}$ subsets with evenly many elements (see, e.g., this question). As we wish to exclude the empty set and the set $\{1,k\}$ the answer is $$\boxed {S_k=2^{k-1}-2}$$

Note that $S_3=4-2=2$ and $S_4=8-2=6$ in harmony with your examples.