Неожиданное количество последовательностей

[EtCetera]

Найти количество последовательностей из $n$ чисел $\alpha_i\in\{0^{-},0^{+},-1,+1\}$ (где $0^{-}=0^{+}=0$), удовлетворяющих условиям

$$\begin{cases}\sum\limits_{i=1}^n\alpha_i=0\\ \sum\limits_{i=1}^k\alpha_i\ne 0,\ \forall k\colon 1\leqslant k< n\end{cases}$$

...и объяснить его неожиданность.

[tolstopuz]

Закодируем каждый член последовательности двумя битами:

\begin{aligned}+1 \to ++ \\ -1 \to -- \\ 0^+ \to +- \\ 0^- \to -+\end{aligned}

Получится биекция с хорошо известной задачей, имеющей простой и красивый результат.

[Dmitriy40]

Либо я чего-то не понял, либо подходят два класса: $(+1, 0^\pm, \ldots, 0^\pm, -1)$ и $(-1, 0^\pm, \ldots, 0^\pm, +1)$ - количество нулей в середине $n-2$, нули в каждой позиции можно ставить любой из двух, соответственно общее количество легко считается по количеству комбинаций нулей. Зачем здесь битовое кодирование не понял.

[grizzly]

Dmitriy40 в сообщении #1355640 писал(а):

$(+1, 0^\pm, \ldots, 0^\pm, -1)$ и $(-1, 0^\pm, \ldots, 0^\pm, +1)$ - количество нулей в середине $n-2$,

Ещё $(+1, +1, 0^\pm, \ldots, 0^\pm, -1, -1)$ - количество нулей в середине $n-4$ и т.п.

[Sergic Primazon]

$2K_{n-1}$ ( $ K_n-$ число Каталана)