円テーブルで席替え

円テーブルで席替え

締め切りが 2017/09/12 10:00 AM なので，その 1 分後に投稿されるように予約

設問

先生1人と生徒 n-1 人の、合わせて n 人が丸いテーブルに座っています。
途中で席替えをして、隣の人を変えることにしました。

例えば、n = 5 のとき、最初に左図のように座っていると、右図のように席替えをすればすべての人の隣が変わることになります。
このとき、先生は動かないものとします。

標準入力から n が与えられたとき、席替えをして両隣の人が変わるような並び順は何通りあるかを求め、その数を標準出力に出力してください。

n = 5 のときは、上記以外に右図の左右を反転したパターンがありますので、標準出力に「2」を出力します。
なお、n は n ≦ 10を満たす正の整数とします。

【入出力サンプル】
標準入力
5

標準出力
2

=======================================================

シンプルに並べ替えを行い，隣が全部違うかどうか調べ，そうならばカウントする。
なお，隣が同じかどうかというのは，隣との差を取り，その絶対値が 1 でも n-1 でもないということ。

permutations = function (n) {
    z = matrix(1)
    for (i in 2:n) {
        x = cbind(z, i)
        a = c(1:i, 1:(i - 1))
        z = matrix(0, ncol = ncol(x), nrow = i * nrow(x))
        z[1:nrow(x), ] = x
        for (j in 2:i - 1) {
            z[j * nrow(x) + 1:nrow(x), ] = x[, a[1:i + j]]
        }
    }
    z
}

f = function(n) {
    count = 0
    p = cbind(1, permutations(n-1)+1) # 1 が先生
    junk = apply(p, 1, function(x) {
        y = c(x, x[1])
        z = abs(diff(y))
        if (all(z != 1, z != n-1)) {
            count+1 ->> count
        }
    })
    cat(count)
}
# f(scan(file("stdin", "r")))
f(4) # 0
f(5) # 2
f(6) # 6
f(7) # 46
f(8) # 354
system.time(f(9)) # 3106, 0.499sec.
system.time(f(10)) # 29926, 3.955sec.

シンプルなプログラムでは，ちょっと計算時間が掛かる。
そこで，オンライン整数列大辞典を参照すると，https://oeis.org/A078603 があり，これは https://oeis.org/A002816 を 2 倍したもの。

f = function(n) {
    sum = factorial(n-1)/2 + (-1)^n
    for (k in 1:(n-1)) {
        for (j in 1:min(n-k, k)) {
            sum = sum+(-1)^k*choose(k-1, j-1)*choose(n-k, j)*n/(n-k)*factorial(n-k-1)/2*2^j
        }
    }
    cat(sum*2)
}