隣の人と異なる仮装

隣の人と異なる仮装

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

いよいよハロウィンの季節がやってきました。
ハロウィンと言えば仮装ですね。
ただ、せっかく仮装しても他の人と同じ衣装になるのは避けたいもの。

そこで、全員が横一列に並んだときに、隣の人とは異なる仮装をすることにしました。
m 人が仮装をしたとき、衣装の数がちょうど n 種類である「並び方」が何通りあるかを求めてください。

例えば、m = 5, n = 3 のとき、同じ文字が同じ衣装を表すものとすると、以下の7通りの並び方があります。
(1) A B A B C
(2) A B A C A
(3) A B A C B
(4) A B C A B
(5) A B C A C
(6) A B C B A
(7) A B C B C
※衣装の内容は問わないものとし、衣装を入れ替えたものは同じと考えます。
　（例：B A B A Cは(1)と同じなのでカウントしない。）

標準入力から m, n が与えられたとき、その並び方が何通りあるかを求め、標準出力に出力してください。
なお、m, n はともに整数で 0 < n < m < 20 を満たすものとします。

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

標準出力
7

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

これは，第2種スターリング数 f(m-1, n-1)

f = function(n, k) {
    # The Stirling numbers of the second kind S(n, k)
    ans = 0
    for (j in 0:k) {
        ans = ans+(-1)^(k-j)*choose(k, j)*j^n
    }
    cat(ans/factorial(k))
}

第2種スターリング数であることは，以下のプログラムで求める m, n の小さいときの結果を考察してのこと。

bincombinations = function (p) {
    retval = matrix(0, nrow = 2^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (2^p/2^n)), rep(1, (2^p/2^n))),
            length = 2^p)
    }
    retval
}

tricombinations = function(p) {
    retval = matrix(0, nrow = 3^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (3^p/3^n)), rep(1, (3^p/3^n)), rep(2, (3^p/3^n))),
            length = 3^p)
    }
    retval
}

quatrcombinations = function(p) {
    retval = matrix(0, nrow = 4^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (4^p/4^n)), rep(1, (4^p/4^n)), rep(2, (4^p/4^n)), rep(3, (4^p/4^n))),
            length = 4^p)
    }
    retval
}

quintcombinations = function(p) {
    retval = matrix(0, nrow = 5^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (5^p/5^n)), rep(1, (5^p/5^n)), rep(2, (5^p/5^n)), rep(3, (5^p/5^n)), rep(4, (5^p/5^n))),
            length = 5^p)
    }
    retval
}

sextetcombinations = function(p) {
    retval = matrix(0, nrow = 6^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (6^p/6^n)), rep(1, (6^p/6^n)), rep(2, (6^p/6^n)), rep(3, (6^p/6^n)), rep(4, (6^p/6^n)), rep(5, (6^p/6^n))),
            length = 6^p)
    }
    retval
}

septetcombinations = function(p) {
    retval = matrix(0, nrow = 7^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (7^p/7^n)), rep(1, (7^p/7^n)), rep(2, (7^p/7^n)), rep(3, (7^p/7^n)), rep(4, (7^p/7^n)), rep(5, (7^p/7^n)), rep(6, (7^p/7^n))),
            length = 7^p)
    }
    retval
}

f = function(m, n) {
    if (n == 2) {
        a = bincombinations(m-1)
    } else if (n == 3) {
        a = tricombinations(m-1)
    } else if (n == 4) {
        a = quatrcombinations(m-1)
    } else if (n == 5) {
        a = quintcombinations(m-1)
    } else if (n == 6) {
        a = sextetcombinations(m-1)
    } else if (n == 7) {
        a = septetcombinations(m-1)
    }
    a = cbind(0, a[a[,1] != 0,, drop=FALSE])

    b = rep(1, nrow(a))
    for (i in 1:(m-1)) {
        b = b & (a[,i] != a[,i+1])
    }
    a = a[b,, drop=FALSE]
    b = apply(a, 1, function(x) sum(0:(n-1) %in% x) == n)
    a = a[b,, drop=FALSE]
    nrow(a)/factorial(n-1)
}