問題
との2文字からなる文字列を次の規則(イ)，(ロ)で順次定めていく．
(イ) とおく．
(ロ) の中に現れるすべてのをで，すべてのをで置き換えてできる文字列をとする．
例えば，，である．2次の正方行列，に対して，の中のをで，をで置き換え，行列の積をつくってできる行列をとする．例えば，，(行列の積)である．
，のとき，ならばであることを示せ．
出典：京都大学 1995年度 前期日程 第2次学力試験 理系 第4問
方針
1回の置換を直接追うと積の順序が複雑になるので、置換を2回まとめる。、 に対応する行列積を計算すると、それぞれ と単位行列になる。残りは に含まれる の個数が常に奇数であることを示し、 から結論を得る。
解答
まず、求める行列を
とおく。また単位行列を とする。
直接計算すると
であり、したがって
である。また であり、さらに である。
次に、文字列の置換を2回続けて見る。1回の置換では であるから、2回続けると である。行列積に直すと、 は 、 は に対応する。
したがって、 から作られる行列 は、 の中の各 を に、各 を に置き換えて積をとったものに等しい。 は積に影響しないので、 に含まれる の個数を とすれば である。
あとは が常に奇数であることを示せばよい。 に含まれる の個数を とすると、置換規則より である。右辺の第2項 は偶数なので、 と の偶奇は同じである。 だから、すべての について は奇数である。
よって であり、すべての について が成り立つ。すなわち ならば
である。