左右に行ったり来たり
締め切りが 2017/03/28 10:00 AM なので，その 1 分後に投稿されるように予約
設問
一列に n 個のマスが並んでおり、各マスには 1～(n-1) のいずれかの数字が書かれています。
この一列のマスに対して、書かれている数字の数だけ左右に移動します。
このとき、進む方向は「左」「右」を交互に繰り返します。
最初、左端から右向きにスタートして、右端のマスに到達するような数字の配置を考えます。
なお、右端のマスに到達した時点で終了するため、右端のマスは0とします。
また、左端のマスより左、右端のマスより右には移動できないため、そのような数字の配置はできないものとします。
例えば、以下のマスのように配置されていると、図のように移動します。
このように、右端に到達できる数字の配置のうち、すべてのマスでちょうど一度ずつ止まるものが何通りあるかを求めてください。
例えば、n = 6 の場合は、上記の左図の他に右図のようなパターンがあり、全部で5通りです。
なお、n は12以下の整数とします。
【入出力サンプル】
標準入力
6
標準出力
5
===============================
小さな n の場合の結果を計算する，以下のような簡単なプログラムを書き，既知の数列かどうか検索する。
check = function(n, nm1, p) {
location = integer(nm1)
i = 1
for (j in 1:nm1) {
location[i] = p[i]
i = i+location[i]*ifelse(j %% 2 == 1, 1, -1)
if (i < 1 || i > n) {
return(FALSE)
} else if (i == n) {
return(all(location != 0))
} else if (location[i] != 0) {
return(FALSE)
}
}
return(FALSE)
}
f = function(n) {
nm1 = n - 1
p = rep(1, nm1)
p[1] = 2
ptr = nm1
count = 0
repeat {
count = count+check(n, nm1, p)
p[ptr] = p[ptr] + 1
if (p[ptr] == n) {
temp = ptr
repeat {
temp = temp - 1
if (temp == 0) {
break
} else if (p[temp] < nm1) {
p[temp] = p[temp]+1
p[(temp+1):nm1] = 1
break
}
}
if (temp == 0 || p[1] == nm1) {
break
}
}
}
count
}
n が奇数の場合は F(n) = 0
R だと，n = 8 はかなり時間が掛かる。
Java でも，n = 10 までで，n = 12 は止めておこうという気になる。
n = 2, 4, 6, 8, 10 に対して，F(n) = 1, 5, 61, 1385
結果として，既知の数列である。
https://oeis.org/search?q=1%2C5%2C61%2C1385&language=japanese&go=%E6%A4%9C%E7%B4%A2
a(n) = Sum_{k = 0..2*n} Sum_{j = 0..k} (-1)^(n-j) *binomial(2*n+1,k-j)*(j+1/2)^(2*n)
これを取り込んだプログラム
f = function(n) {
s = 0
if (n%%2 == 0) {
n = n/2-1
for (k in 0:(2 * n)) {
for (j in 0:k) {
s = s + (-1)^(n - j) * choose(2 * n + 1, k - j) * (j + 0.5)^(2 * n)
}
}
}
options(scipen = 100)
cat(s)
}
f(4) # 1
f(5) # 0
f(6) # 5
f(8) # 61
f(10) # 1385
f(12) # 50521
f(14) # 2702765
f(16) # 199360981 であるが，計算誤差のため 199360916 になってしまう
gmp を使えばよい。
