当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。
（平成２７年６月９日付け）
３×４の碁盤（正方形が縦に3、横に4連なる形状)があり、これを仕切る線の交点（格子点）
上の２０ヶ所に碁石を置いておく。今、この左下から碁石を取り始め、次は右横に進んで次
の碁石を取るものとする。
このとき、全ての碁石を取って元の位置（格子点の左下）へ戻ってこれる方法は何通りあ
るか？
ただし、全ての格子点は一度しか通過できなく、進む方向は水平か垂直に限るとする。
＜ヒント＞ 手作業でも頑張れば全ルートを発見できる総数です。
そこで、今度はこれの２倍、３×８の碁盤（格子点数３６個）ならば、ルートの総数は何通り
あるか？
＜ヒント＞ 手作業では無理だと思います。
（答） DD++さんが考察されました。（平成２７年６月９日付け）
3×1 0+1=1通り
3×2 1+1=2通り
3×3 2+4=6通り
3×4 6+6=12通り
3×5 12+19=31通り
3×6 31+37=68通り
3×7 68+100=168通り
3×8 168+216=384通り
なんかミスってそう。
らすかるさんが考察されました。（平成２７年６月９日付け）
格子点を、以下のようにA〜Tとして
ABCDE
FGHIJ
KLMNO
PQRST
地道に数えたら、次の１４通りがありましたので、多分１２通りではないと思います。（自信
はありません。まだ数え落としている可能性もあります。）
PQRSTOJEDCBAFGHINMLKP 、PQRSTOJEDCHINMLGBAFKP
PQRSTOJEDINMHCBAFGLKP 、PQRSTOJEDINMLGHCBAFKP
PQRSTONIJEDCBAFGHMLKP 、PQRSTONIJEDCHMLGBAFKP
PQRSTONMHIJEDCBAFGLKP 、PQRSTONMLGHIJEDCBAFKP
PQRMNSTOJEDIHCBAFGLKP 、PQRMHINSTOJEDCBAFGLKP
PQRMLGHINSTOJEDCBAFKP 、PQLMRSTONIJEDCHGBAFKP
PQLGHMRSTONIJEDCBAFKP 、PQLGHINMRSTOJEDCBAFKP
ＧＡＩ さんからのコメントです。（平成２７年６月９日付け）
3×1 0+1=1通り
3×2 1+1=2通り
3×3 2+4=6通り
DD++さんからのコメントです。（平成２７年６月９日付け）
「PQRSTOJEDCHINMLGBAFKP」・・・ あー、DCHIのとこでターンする形があるんですね。
これを見落としていました。「PQLGHINMRSTOJEDCBAFKP」も同様に。そして、列を増築し
ながら数えたので、ここから始まる系列と途中で似たような形になるものが全部抜けた、と。
今度こそ。" "部分を修正して計算も合ったっぽいです。
パターンA・・・右端の4点を2個ずつにわけて回収する。
パターンB・・・右端の4点をまとめて回収する。
パターンX（条件を満たさない）・・・反時計回りの2つのループで全てを回収する。ただし右端
はそれぞれのループで2個ずつ回収する。
"右端2個をただ往復する形に限り同じ場所を2回通ることを許可する。"
とすると、 A[n] = A[n-1] + B[n-1]
B[n] = 2A[n-2] + 3B[n-2] + X[n-2]
X[n] = 2A[n-1] + 2B[n-1] + X[n-1]
という漸化式ができる。
A[1] = 0、B[1] = 1、B[2] = 1、X[1] = 1 から順に計算すると、
A[1] = 0、B[1] = 1、X[1] = 1 → 0+1=1通り
A[2] = 1、B[2] = 1、X[2] = 3 → 1+1=2通り
A[3] = 2、B[3] = 4、X[3] = 7 → 2+4=6通り
A[4] = 6、B[4] = 8、X[4] = 19 → 6+8=14通り
A[5] = 14、B[5] = 23、X[5] = 47 → 14+23=37通り
A[6] = 37、B[6] = 55、X[6] = 121 → 37+55=92通り
A[7] = 92、B[7] =144 → 92+144=236通り
A[8] = 236、B[8] = 360 → 236+360=596通り
ＧＡＩ さんからのコメントです。（平成２７年６月９日付け）
完全正解です。
（参考） A006864によれば、
漸化式：a(n)=2a(n-1)+2a(n-2)-2a(n-3)+a(n-4)
a(0)=0、a(1)=1、a(2)=2、a(3)=6
母関数 G(x)=x2/(1-2x-2x2+2x3-x4)
だそうです。これと類似して、
A006865、A145401、A145416、A145418、A160149、A003763、A222200
などが調査されていました。これらの問題分野として、Hamiltonian Cycle についていろいろ
と調べてみたら、ほんとにいろいろな図形パターンでの調査が既に奥深くなされていること
に驚きました。