動させたとき、王が元居た場所に戻れる異なるルートが何通りあるか考えてほしい。
更に、格子点からなる３次元空間を、王の動きを真似て、ある格子点から次の格子点への
移動を (t_1,t_2,t_3) (ここに t_k=1 or -1 or 0 ; 1≦k≦3 )
但し、(0,0,0)を除く26通りの方向ベクトルのいずれも可能であるものとする。
このとき、３手で王が元の位置に戻れるルートは全部で何通りあるか？
らすかるさんからのコメントです。（令和２年１１月６日付け）
一般に、n次元のとき、
f(n)=Σ[k=1〜n]nCk・2^k・{2^k・3^(n-k)-2}=7^n-3^(n+1)+2通り
と表せるので、代入して平面はf(2)=24通り、立体はf(3)=264通り
(四次元なら2160通り、五次元なら16080通り)
で合ってるかな？
ＧＡＩさんからのコメントです。（令和２年１１月６日付け）
こんな一般に解決できる式をどうやって導いたのですか？ しかもこんな短時間で！
上記の式の左辺から右辺への変形もどうやっているだろうと不思議です。
こちらはごちゃごちゃした式をあれこれ組み合わせてやっとの思いで手に入れていました。
こんなにもスッキリした一般式が存在できるとは思ってもいませんでした。
らすかるさんからのコメントです。（令和２年１１月６日付け）
例えば、三次元では、（説明を簡単にするため、ルービックキューブの用語を使います）
26個のキューブのうち、センターキューブが6個、エッジキューブが12個、コーナーキューブが
8個ですね。
これは、なぜこのような個数になるかというと、
(t_1,t_2,t_3)のうちどれか一つだけ±1で残りが0のものが、センタキューブ
(t_1,t_2,t_3)のうち二つが±1で残りが0のものが、エッジキューブ
(t_1,t_2,t_3)のうち三つ全部が±1のものが、コーナーキューブ
ですから、
センターキューブは、3C1・2^1個、エッジキューブは3C2・2^2個、コーナーキューブは3C3・2^3個
となります。一般のnでは、キューブの種類もn種類となり、
1方向に移動→nC1・2^1個、2方向に移動→nC2・2^2個、・・・、k方向に移動→nCk・2^k個
これがΣの中身の前半です。そして、それぞれの場合に次に動ける先がいくつあるかを考え
ると、
センターキューブでは、3×3×3から1方向に移動したので、1方向だけ1減って3×3×2
エッジキューブでは、3×3×3から2方向に移動したので、2方向が1減って3×2×2
コーナーキューブも同様に、2×2×2
ただし、これは「2回目で元の位置」と「2回目に移動しない」の二つが含まれていますので、2を
引けば2回目に移動可能な場所の個数になります。
つまり、
センターキューブは、3^2・2^1-2通り
エッジキューブは、3^1・2^2-2通り
コーナーキューブは、3^0・2^3-2通り
これは一般のn,kにすると、3^(n-k)・2^k-2となり、これがΣの中身の後半です。
従って、 Σ[k=1〜n]nCk・2^k・{2^k・3^(n-k)-2} と表されることになります。
左辺を右辺の式に変形してくれたのはWolframAlphaさんです。式が簡略化されることを期
待してWolframAlphaに、
sum binom(n,k)*2^k*(2^k*3^(n-k)-2),k=1 to n
と入力したら、-3^(n+1)+7^n+2 という式が得られました。おそらく二項定理の式に適当なも
のを代入すれば簡単に得られると思います。
DD++さんからのコメントです。（令和２年１１月６日付け）
立体的な動きが、各成分の動きの直積っぽい感じになることを利用するのが簡単そうです
かね。
まず、2手で元に戻るルートを数えます。仮に「不動」を認めれば、動きの各方向成分が
3通りずつあるので、全てのルートは 3^3 = 27 通り
このうち2回不動になるルートは 1 通り
よって、不動を認めない場合のルートは、 27-1 = 26 通り
次に、3手で元に戻るルートを数えます。仮に「不動」を認めれば、動きの各方向成分が
7通りずつあるので、全ての動き方は 7^3 = 343 通り
このうち1回だけ不動になるルートは実質2手で戻るルートなので、いつ動くかも考慮して
26*3C2 = 78 通り
3回不動になるルートは 1 通り
よって、不動を認めない場合のルートは、 343-78-1 = 264 通り
ＧＡＩさんからのコメントです。（令和２年１１月６日付け）
DD++さんの思考方法をお借りしますと、
２手で戻る
gp > 3^3-1
%47 = 26
３手で戻る
gp > 7^3-(26*binomial(3,2)+1)
%48 = 264
４手で戻る
gp > 19^3-(264*binomial(4,3)+26*binomial(4,2)+1)
%44 = 5646
５手で戻る
gp > 51^3-(5646*binomial(5,4)+264*binomial(5,3)+26*binomial(5,2)+1)
%45 = 101520
６手で戻る
gp > 141^3-
(101520*binomial(6,5)+5646*binomial(6,4)+264*binomial(6,3)+26*binomial(6,2)+1)
%46 = 2103740
３手に7^3、４手に19^3、５手に51^3、････ を用いている理由は、
U=(1,1),H=(1,0),D=(1,-1)の３通りの選択で、(0,0)-->(3,0),(4,0),(5,0),･･･ （３手、４手、５手に相当）
へのルート数が、7,19,51,･･･(通り）発生するんで、これに伴い３次元での王の行動パターンが
(t_1,t_2,t_3)の方向ベクトル、すなわち王のすべての行動パターンは、
３手なら7^3、４手なら19^3、５手なら51^3、･･･
の総数があることになる、でいいんでしょうか？
DD++さんからのコメントです。（令和２年１１月７日付け）
そうですね。
