Consider the set of elements $$ \Sigma = \{ s, a_1, a_2, \dots, a_m \} \cup \alpha_1 \cup \dots \cup \alpha_m $$ where $\alpha_i = \{ \alpha_{i, 1}, \dots, \alpha_{i, n_i} \}$ for some fixed numbers $n_i, i = 1, \dots, m$.
We are interested in the number of permutations which fulfill the following set of rules:
- $s$ is the first element.
- For all $i = 1, \dots, m$ and for all $k = 1, \dots, n_i$, it holds that $\alpha_{i, k}$ comes after $a_i$.
- $a_1$ comes before $a_2$ comes before $a_3$, $\dots$, $a_{m-1}$ comes before $a_{m}$.
Idea:
Let $|\Sigma| = n$. Without any condition, there are $n!$ permutations of $\Sigma$. Taking the first condition into account, there are $$ n! \cdot \frac 1 n = (n - 1)! $$ permutations since by symmetry, there is an equal number of permutations where each element is in the first position. Similarly, there are $$ (n - 1)! \cdot \prod_{i = 1}^{m} \frac 1 {|\alpha_i| + 1} $$ permutations taking both condition 1. and 2. into account.
Now comes the tricky part where I am unsure: Consider the condition "$a_k$ before $a_{k + 1}$" for some $k$. By symmetry, only one half of the permutations fulfills this condition since in the other half, $a_k$ comes after $a_{k + 1}$. If this argument is true, then it could (maybe) be used repetitively, which yields $$ (n - 1)! \cdot \prod_{i = 1}^{m} \left( \frac 1 {|\alpha_i| + 1} \right) \cdot \frac 1 {2^{m-1}} $$ permutations in total.
Answer: The number of valid sequences is $$ (n-1)!\times \prod_{i=1}^m \frac1{\sum_{j=m+1-i}^{m}(n_j+1)}\tag1 $$
Proof: There are $(n-1)!$ permutations for which $s$ comes first. Of these,
The fraction of permutations for which $a_m$ comes before each $\alpha_{m,k}$ is $\frac1{n_m+1}$. This because, of the $n_1+1$ symbols $\{a_m,\alpha_{m,1},\dots,\alpha_{m,n_m}\}$, each is equally likely to appear first, and we need $a_m$ to appear first.
Next, we require two things. We require $a_{m-1}$ to appear before any of the $\alpha_{m-1,k}$'s, and we require $a_{m-1}$ to appear before $a_m$. Since we already required $a_m$ to appear before the $\alpha_{m,k}$'s in the previous bullet point, this is equivalent to requiring $a_{m-1}$ to appear first among the following collection of $(n_m+1)+(n_{m-1}+1)$ symbols:$$a_{m-1},\alpha_{m-1,1},\dots,\alpha_{m-1,n_{m-1}},a_m,\alpha_{m,1},\dots,\alpha_{m,n_m}$$Since each of these symbols is equally likely to appear first, the proportion of permutations for which this happens is $\frac1{(n_m+1)+(n_{m-1}+1)}$. Furthermore, the event that $a_{m-1}$ appears before anything else in the above list, is independent of the previous event that $a_m$ appears before any of the $\alpha_{m,k}$. Therefore, we can safely multiply these two fractions, as we do in $(1)$.
This pattern persists. For each $i\in \{1,\dots,m\}$, at the $i^\text{th}$ stage, we consider the event that $a_{m+1-i}$ occurs first among the list $(n_m+1)+(n_{m-1}+1)+\dots+(n_{m+1-i}+1)$ symbols consisting of $a_j$ for $j\in \{m+1-i,\dots,m\}$, together with $\alpha_{j,k}$, for $j\in \{m+1-i,\dots,m\}$, and $k\in \{1,\dots,n_j\}$. Each of these symbols is equally likely to first, independently of the previous considerations. Therefore, the probability is $$ \frac1{(n_{m+1-i}+1)+(n_{m+2-i}+1)+\dots+(n_m+1)} $$