1996 Putnam B5

Given a finite string $S$ of symbols $X$ and $O$, we write $\Delta(S)$

for the number of $X$'s in $S$ minus the number of $O$'s. For example,

$\Delta(XOOXOOX) = -1$. We call a string $S$ **balanced** if every

substring $T$ of (consecutive symbols of) $S$ has $-2 \leq \Delta(T)

\leq 2$. Thus,$XOOXOOX$ is not balanced, since it contains the

substring $OOXOO$. Find, with proof, the number of balanced strings of

length $n$.

给定一个由符号 $X$ 和 $O$ 组成的有限字符串 $S$，我们写成 $\Delta(S)$

$S$ 中 $X$ 的数量减去 $O$ 的数量。例如，

$\Delta(XOOXOOX) = -1$。我们称字符串 $S$ **平衡** 如果每个

$S$(的连续符号)的子串 $T$ 有 $-2 \leq \Delta(T)

\leq 2$。因此，$XOOXOOX$ 是不平衡的，因为它包含

子字符串 $OOXOO$。有证据地求出平衡串的数量

长度$n$。