Number of ways of writing the integer interval $[1..N]$ as a union of non-overlapping subintervals $[i..j],\,i \le j$ Consider splitting an integer interval $[1..N]$ into non-overlapping subintervals $[i_k..j_k],\,i_k \le j_k$, i.e.
$$
[1..N] = \bigcup_{k=1}^{K} \, [i_k..j_k] \quad i_1 =1, i_{k+1} = j_{k}+1, j_K=N
$$
How many ways can this be done?
Example: $[1,2,3]$: The set of possibilities is $\{[1]\cup[2]\cup[3],[1]\cup[2,3],[1,2]\cup[3],[1,2,3] \}$ for a total of $4$.
This question is related to Splitting the set $A=\{1,2,...,n\}$ into at most $m$ non-empty disjoint subsets, whose union is $A$, but differs in that here the subsets must consist of contiguous numbers.
 A: The wanted number is
\begin{align*}
\color{blue}{2^{N-1}}
\end{align*}
We can identify each of the intervals with the left-most value as in the case $N=3$:
\begin{align*}
\{[\color{blue}{1}]\cup[\color{blue}{2}]\cup[\color{blue}{3}],[\color{blue}{1}]\cup[\color{blue}{2},3],[\color{blue}{1},2]\cup[\color{blue}{3}],[\color{blue}{1},2,3] \}\qquad\longleftrightarrow\qquad (1,2,3),(1,2),(1,3),(1)
\end{align*}

We can write this number as sum
\begin{align*}\color{blue}{\sum_{j=1}^N\sum_{1=i_1<i_2<\cdots<i_j\leq N}1}&=\sum_{j=1}^{N}\binom{N-1}{j-1}\tag{1}\\
&=\sum_{j=0}^{N-1}\binom{N-1}{j}\tag{2}\\
&\,\,\color{blue}{=2^{N-1}}
\end{align*}
according to the claim.

Comment:

*

*In (1) we note that $j_1=1$ since we always start with $1$. $\binom{N-1}{j-1}$ is the number of $j-1$-tuples $\left(i_2,i_3,\ldots,i_{j}\right)$ between $2$ and $N$.


*In (2) we shift the index by one to start with $j=0$ and apply the binomial theorem.
A: The number of ways is $2^{n-1}$. Imagine $n$ objects in a row, numbered $1$ to $n$ from left to right. There are $n-1$ gaps between adjacent objects. In each gap, you can either place a barrier, or not. You can make these $n-1$ binary choices is $2^{n-1}$ ways. The placement of the barriers uniquely determines a partition of $\{1,\dots,n\}$ into intervals.
