Counting certain graphs defined over consecutive sets of natural numbers Let $[n] = \{1,\ldots, n\}$ and call a subset $M \subseteq [n]$ a consecutive subset if $$M = \{m,m+1,\ldots,m+|M|-1\}$$
for some $m \in [n]$, i.e., $M$ contains a smallest and a largest number and all numbers in between, or equivalently if $x,y \in M$ implies $z \in M$ for all $x \le z \le y$.
Consider directed graphs $G_n = (V, E)$ with vertex set $V \subseteq \{ M \subseteq [n] \mid M \mbox{ is consecutive } \}$ and edge set $E = \{ (N, M) \in V\times V\mid M \subseteq N \land |N\setminus M| = 1 \}$ with the additonal constraint that from $[n]$ we have at least one path to every other vertex and $[n] \in V$.
For example if $n = 3$ one such graph is:

and in total we have $17$ different such graphs for $n = 3$, one of these is the above and the other are:

Note that by the additional requirement that we have a path from $\{1,2,3\}$ to every other vertex, for example the graph $G = (V, E)$ with $V = \{\{1,2,3\}, \{1\}\}$ and $E = \emptyset$ is excluded.
How to count the number of such graphs for given $n$? For $n = 1$ we have one,
for $n = 2$ we have $4$ and for $n = 3$ we have $17$. I cannot count inductively because certain nodes (like $\{2\}$ in the above example) get merged, so I cannot give an inductive formula by counting sub-graphs and constructing a new graph.
 A: Let's rephrase.
Let $[a, b] = \{x \in \mathbb{N} : a \le x \le b\}$ and $[n] = [1, n]$.
Consider the directed graph $G_n = (V_n, E_n)$ with vertices $$V_n = \{[a, b] : 1 \le a \le b \le n\}$$ and edges $$E_n = \bigcup_{(a, b) \in V_n,\\ a < b} \{ ((a,b),(a+1,b)), ((a,b),(a,b-1)) \}$$
What you want to count are induced subgraphs $H \subseteq G_n$ which contain $[n]$ and for which every vertex is reachable from $[n]$.

I think it is useful to look at an isomorphic graph $G'_n \sim G_n$ whose vertices are pairs $$V'_n = \{(x, y) \in \mathbb{N}\times\mathbb{N}: x+y < n\}$$ and edges $$E'_n = \bigcup_{x+y<n-1} \{ ((x,y),(x+1,y)), ((x,y),(x,y+1)) \}$$ where the vertex $(x,y) \in V'_n$ corresponds to the vertex $[x+1, n-y] \in V_n$. Then $G'_n \subset G'_{n+1}$ and the root vertex is always $(0, 0)$.
Observe that $G'_n$ is a layered graph: $(x,y)$ is in layer $x+y+1$, which contains $x+y+1$ vertices. The reachability of vertices in layer $k+1$ depends solely on which vertices from layer $k$ are in the subgraph, so we can count based on subsets of layers. Let $C_k: 2^{[0,k-1]} \to \mathbb{N}$ count the number of induced subgraphs of $G'_k$ which contain a given subset of $\{(0,k-1), (1,k-2), \ldots, (k-1,0)\}$. Then $$\begin{eqnarray}
C_1(\emptyset) &=& 0 \\
C_1(\{(0,0)\}) &=& 1 \\
C_{k+1}(S) &=& \sum_{T \in 2^{[0,k-1]} \\ S \subseteq N(T)} C_k(T) \\
N(T) &=& \bigcup_{x \in T} \{ x, x+1 \}
\end{eqnarray}$$
For practical computation I think it's preferable to calculate $N(T)$ and then propagate to its subsets rather than to iterate over all $T$ checking whether $S$ is a subset.
