このタイトルを付けて思い出したけど、一昨日に多項式と形式的べき級数を学んだ。
具体的には、次のサイトの問題を解いた。
ということで、次の条件を満たす数え上げ問題は、多項式・形式的べき級数の問題に言い換えられるようになった。
- 状態が数で表せる
- 遷移が状態への加算か減算である
言い換えたあとの問題を解くことはまだできないけど、問題を整理するときに使える。あと、言い換えがけっこう楽しい。つい言い換えたくなる。いい傾向。
問題
今座標平面上の原点にいる。
現在位置を(x, y)としたとき、1秒につき次の場所のどこかに移動できる。
(x + 1, y)(x - 1, y)(x, y + 1)(x, y - 1)(x + 1, y + 1)(x - 1, y - 1)
T秒後に(X, Y)にいるルートは何通りあるか。
言い換え後の問題
(x + x^{-1} + y + y^{-1} + xy + (xy)^{-1})^Tを展開したときの(x^X)(y^Y)の係数はいくつか。
終わりに
追突に言い換えをしたくなるほど言い換えが楽しい。
あとは言い換え後の問題を考察する力が欲しい。これは慣れていけばよさそう。言い換えた問題をもとに考察する習慣をつければ自然と身に付いていく。
