裏 RjpWiki

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

この問題，2 年前にも同じようなのが出題されたんだよね。（ 完全順列 http://blog.goo.ne.jp/r-de-r/s/完全順列 ）

 一人一台のパソコンを支給されている、社員N人の会社があります。
このパソコンは見た目がすべて同じため、他の人のパソコンを間違って持ち帰ってしまう場合がありました。

N人全員が他人のパソコンを持って帰ってしまうような組み合わせが何通りあるかを求めてください。
使用するプログラミング言語は問いません。

なお、出力は64bit整数に収まります。

【入出力サンプル】

Input
5

Output
44

==========

前は再帰で書いたので，別の書き方で 2 通りのプログラム

f = function(n) {
    options(scipen=100)
    a = 0
    b = 1
    for (i in 3:n) {
        x = (i - 1) * (a + b)
        a = b
        b = x
    }
    cat(x)
}

f = function(n) {
    options(scipen=100)
    k = 2:n
    cat(sum( (-1)^k * factorial(n) / factorial(k) ))
}

f(5) # 44
f(12) # 176214841
f(17) # 130850092279664

> 12人全員が他人のパソコンを持って帰ってしまうような組み合わせが何通りあるか

Wikipedia 曰く，

完全順列（かんぜんじゅんれつ、英 Derangement）、もしくは攪乱順列（かくらんじゅんれつ）とは、整数 1, 2, 3, …, n を要素とする順列において、i 番目 (i ≤ n) が i でない順列である。

完全順列の総数はモンモール数という。

モンモール数 a_n を与える漸化式は a_n = (n-1)(a_n-1+a_n-2), n ≧ 3

a₁ = 0, a₂ = 1

> an = function(n) {
+     if (n == 1) {
+         return(0)
+     } else if (n == 2) {
+         return(1)
+     } else {
+         return((n-1)*(Recall(n-1)+Recall(n-2)))
+     }
+ }

> an(3)
[1] 2

> an(4)
[1] 9

> an(12)
[1] 176214841