Empecé a escribir esto tratando de completar la demo de la primera observación que había hecho y de demostrar el dato gracioso que mágicamente había visto Brian. De alguna manera terminé con una solución que se siente como una mezcla de las de Fede y el Turko, pero vamos allá.
Vamos a construir las sucesiones impar-par con términos menores o iguales a $n$ a partir de las sucesiones impar-par con términos menores o iguales a $n-1$. Sean $T(n)$ la cantidad de sucesiones impar-par con términos menores o iguales a $n$, $I(n)$ la cantidad de sucesiones impar-par con términos menores o iguales a $n$ de longitud impar y $P(n)$ la cantidad de sucesiones impar-par con términos menores o iguales a $n$ de longitud par. Entonces tenemos que $T(n)=I(n)+P(n)$.
Notemos que $I(2n+1)=I(2n)+P(2n)+1$, pues tenemos todas las sucesiones de longitud impar para $2n$, todas las sucesiones de longitud par para $2n$ a las que les agregamos al final el término $2n+1$ y una sucesión "extra" que es la que está formada únicamente por $2n+1$ (y todas las sucesiones se construyen de esta manera). Notemos también que $I(2n+2)=I(2n+1)$, porque las sucesiones de longitud impar tienen que terminar con un impar, así que podemos formar exactamente las mismas sucesiones teniendo a $2n+2$ como el mayor término que puede aparecer en una sucesión que teniendo a $2n+1$ como el mayor término que puede aparecer en una sucesión (y todas las sucesiones se construyen de esta manera).
Notemos que $P(2n+1)=P(2n)$ por el mismo argumento de recién. Notemos también que $P(2n+2)=I(2n)+P(2n)$, pues tenemos a todas las sucesiones de longitud impar para $2n$ a las que les agregamos al final el término $2n+2$ y todas las sucesiones de longitud par para $2n$ (y todas las sucesiones se construyen de esta manera).
De acá podemos demostrar por inducción que $I(2n)=F_{2n}$ y que $P(2n)=F_{2n+1}-1$, resultando así\begin{align*}T(2n) & =I(2n)+P(2n) \\
& =F_{2n}+F_{2n+1}-1 \\
& =F_{2n+2}-1
\end{align*}y\begin{align*}T(2n+1) & =I(2n+1)+P(2n+1) \\
& =I(2n+2)+P(2n) \\
& =F_{2n+2}+F_{2n+1}-1 \\
& =F_{2n+3}-1,
\end{align*}de modo que en general $T(n)=F_{n+2}-1$ para todo $n\in \mathbb{N}$, donde $F_n$ es el $n$-ésimo número de Fibonacci (la primera observación había sido que $T(n+2)=T(n)+T(n+1)+1$, que se puede demostrar directamente teniendo la formulita general de $T$). En particular tenemos que $T(10)=F_{12}-1=143$.
Entonces para $n = 1$ tenemos $a_{1, 1} = 1$ y $a_{2,1} = 0$ ya que no hay sucesiones de $2$ términos.
Para $n = 2$ $a_{1, 2} = 1$ y $a_{2,2} = 1$.
Para $n = 3: a_{1, 3} = 2, a_{2, 3} = 1, a_{3, 3} = 1$
Para $n = 4: a_{1, 4} = 2, a_{2, 4} = 3, a_{3, 4} = 1, a_{4,4} = 1$
Notemos que cada vez que le sumamos $1$ a $n$ estamos agregando una nueva sucesión $\{1, 2, \dots, n\}$ a la cual le corresponde $a_{n, n} = 1$.
Ahora como ejemplo pongo $n = 5$, veamos que este si o si tiene que ir al final de cada sucesión por ser el mas grande. Por consiguiente, las sucesiones de $2$ y $4$ términos quedan intactas ya que no podemos poner un $5$ en una posición par. Entonces, la cantidad de sucesiones de $2$ y $4$ términos que había en $n = 4$ va a ser la misma para $n = 5$ y por lo tanto $a_{2,4} = a_{2, 5}$ y $a_{4, 4} = a_{4,5}$.
En general, si $n$ es impar
$$a_{2k, n-1} = a_{2k, n}$$
y si $n$ es par, el razonamiento es análogo y por lo tanto
$$a_{2k+1, n-1} = a_{2k+1, n}$$
Pero ahora veamos que pasa con las sucesiones, a las cuales si se les puede agregar un termino al final. Por ejemplo si $n = 5$, podemos "desbloquear" nuevas sucesiones que no existían para $n = 4$ las cuales son: $\{5\}, \{1, 2, 5\}, \{3, 4, 5\}, \{1, 4, 5\}, \{1, 2, 3, 4, 5\}$. Esta claro que el $5$ tiene que ir al final de cada una, entonces si no contamos al $5$, las sucesiones nos quedan $\{1, 2\}, \{3, 4\}, \{1, 4\}, \{1, 2, 3, 4\}$, cada una de estas sucesiones tiene $2, 2, 2, 4$ términos respectivamente, y además son sucesiones que ya consideramos en $n = 4$. Para ser mas precisos, podemos formar $3$ sucesiones de $3$ términos mediante las sucesiones ya existentes de $2$ términos en $n = 4$, y de igual manera podemos formar una sucesión de $5$ términos mediante la sucesión ya existe de $4$ términos. En general, si $n$ es impar sabemos que
$$a_{2k+1, n} = \underbrace{a_{2k+1, n-1}}_{\text{Sucesiones ya existentes de $2k+1$ términos}} + \underbrace{a_{2k, n-1}}_{\text{Sucesiones nuevas de $2k+1$ términos que se forman mediante las de $2k$ términos}} $$
(Definimos $a_{0, n} = 1$, de esta manera consideramos el caso cuando agregamos la sucesión $\{n\}$ cuando $n$ es impar)
Y para $n$ par nos queda algo parecido:
$$a_{2k, n} = \underbrace{a_{2k, n-1}}_{\text{Sucesiones ya existentes de $2k$ términos}} + \underbrace{a_{2k-1, n-1}}_{\text{Sucesiones nuevas de $2k$ términos que se forman mediante las de $2k-1$ términos}}$$
Por comodidad asumamos que la sucesión empieza con un $0$ imaginario. Entonces en cada paso como cambia de paridad y es creciente aumenta en $2k + 1$ para algún $k \geq 0$. Si fijamos la longitud, agreguemos también al final un $10$ u $11$ dependiendo paridad, que así nos asegura que el último elemento es a lo sumo $10$.
Como entonces la suma de las diferencias queda fija, lo que queremos contar ahora es entonces equivalente a formas de elegir $k_i \geq 0$ tal que: $$
\sum_{i=1}^{l} (2k_i + 1) = t
$$ donde $t \in \{10, 11\}$ y $l$ es la cantidad de saltos (que es uno más que la longitud de la sucesión por cómo la definimos). Manipulando un poco esta expresión llegamos a que $$
2\sum_{i=1}^l k_i + l = t \Leftrightarrow \sum_{i=1}^l k_i = \frac{t - l}{2}
$$ Que es equivalente a meter $\frac{t - l}{2}$ bolitas en $l$ cajitas por lo que hay $$
\binom{\frac{t - l}{2} + l - 1}{l - 1} = \binom{\frac{t + l - 2}{2}}{l - 1}
$$ formas de elegir esto. Esta cuenta sólo tiene sentido para $2 \leq l \leq 11$ por lo que representa. Sea $l=2s$, es decir los casos con $t=10$, evaluando obtenemos: $$
\sum_{s=1}^{5} \binom{\frac{10 + 2s - 2}{2}}{2s - 1} = \sum_{s=1}^{5} \binom{s + 4}{2s - 1} = 5 + 20 + 21 + 8 + 1 = 55
$$ De la misma forma con los casos donde $l = 2s+1$, donde $t=11$ $$
\sum_{s=1}^{5} \binom{\frac{11 + 2s + 1 - 2}{2}}{2s + 1 - 1} = \sum_{s=1}^{5} \binom{s + 5}{2s} = 15 + 35 + 28 + 9 + 1 = 88
$$ Por lo tanto, hay en total $55 + 88 = \boxed{143}$ sucesiones. $\blacksquare$
