オートマトン・形式言語の問題

$L(r)$ の文字列の分解の一意性 $L(r)$ の文字列は、ブロック $a,ab,abb$ をいくつか並べたものである。どのブロックも $a$ で始まり、ブロックの中で $a$ は先頭の 1 個だけなので、空でない $w\in L(r)$ では「各 $a$ の位置からブロックが始まる」と決まり、ブロックへの分け方はただ 1 通りである。したがって $L(r)$ の長さ $8$ の文字列は、「長さが $1,2,3$ のいずれかであるブロックを並べて合計の長さを $8$ にする並べ方」と 1 対 1 に対応する。つまり、$8$ を $1,2,3$ のいずれかの正の整数の順序付きの和に分ける方法（合成）の数を数えればよい。

$b$ の個数とブロック数の関係 長さ $\ell$ のブロックは $b$ を $\ell -1$ 個含む。ブロックが $k$ 個のとき、$b$ の個数は
$$\sum ({\ell }_i-1)=8-k$$
である。よって $b$ の個数が偶数 $⟺$ $8-k$ が偶数 $⟺$ $k$ が偶数。

ブロック数 $k$ ごとの数え上げ 各ブロックの長さを ${\ell }_i=1+e_i$（$0\le e_i\le 2$）とおくと、$e_1+\cdots +e_k=8-k$ を満たす $0$ 以上の整数の組 $(e_1,\dots ,e_k)$（各 $e_i\le 2$）の個数を数えればよい。$k\ge 3$ が必要（$3k\ge 8$）である。偶数の $k$ は $4,6,8$。

• $k=8$: $e_1+\cdots +e_8=0$ より $1$ 通り
• $k=6$: $e_1+\cdots +e_6=2$。合計が $2$ なので $e_i\le 2$ は自動的に満たされ、重複組合せで $\left(\genfrac{}{}{0ex}{}{2+5}{5}\right)=\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$ 通り
• $k=4$: $e_1+\cdots +e_4=4$。制限なしでは $\left(\genfrac{}{}{0ex}{}{4+3}{3}\right)=35$ 通り。このうちある $e_i\ge 3$ となるものは、$e_i^{\prime }=e_i-3$ とおくと $e_1+\cdots +e_i^{\prime }+\cdots +e_4=1$ で $4$ 通り、$i$ の選び方が $4$ 通りで計 $16$ 通り（2 つ同時に $3$ 以上にはなれない）。よって $35-16=19$ 通り

したがって求める個数は
$$1+21+19=41$$

（確認: 奇数の $k$ も数えると $k=7$ で $7$ 通り、$k=5$ で $\left(\genfrac{}{}{0ex}{}{7}{4}\right)-5=30$ 通り、$k=3$ で $3$ 通りとなり、合計 $1+7+21+30+19+3=81$。これは $L(r)$ の長さ $n$ の文字列の個数 $c_n$ の漸化式 $c_n=c_{n-1}+c_{n-2}+c_{n-3}$（$c_0=1,c_1=1,c_2=2$）から得られる $c_8=81$ と一致する。）

$L(r)$ は $a,ab,abb$ の連接でできる文字列全体。どのブロックも $a$ で始まり、その後ろの $b$ は 0〜2 個なので、文字列を $a$ の位置で区切れば分解は一意に決まる。したがって長さ 8 の $L(r)$ の元は、8 を 1, 2, 3 の和（順序つき）で表す方法（合成）と 1 対 1 に対応する（ブロックの長さ 1, 2, 3 がそれぞれ $a$, $ab$, $abb$ に対応）。

ブロックの個数を $k$ とすると $a$ の個数は $k$、$b$ の個数は $8-k$。$b$ の個数が偶数 $⟺$ $k$ が偶数。

長さ 8 でブロック数 $k$ の合成の個数は $(x+x^2+x^3{)}^k$ の $x^8$ の係数、すなわち $(1+x+x^2{)}^k$ の $x^{8-k}$ の係数:
- $k=2$: 最大でも長さ 6 なので 0
- $k=4$: $(1+x+x^2{)}^4$ の $x^4$ の係数は 19
- $k=6$: $(1+x+x^2{)}^6$ の $x^2$ の係数は $6+\left(\genfrac{}{}{0ex}{}{6}{2}\right)=21$
- $k=8$: 1（$a^8$）

合計 $19+21+1=41$。

検算: 奇数 $k$ の側は $k=3$: 3、$k=5$: 30、$k=7$: 7 で計 40。合計 $41+40=81$ は、1, 2, 3 を使った 8 の合成の総数（トリボナッチ型の漸化式 $c_n=c_{n-1}+c_{n-2}+c_{n-3}$, $c_0=1,c_1=1,c_2=2,\dots ,c_8=81$）と一致する。

答え: 41