モンモール問題、完全順列、攪乱順列の拡張

質問

モンモール問題、完全順列、攪乱順列で検索するといろいろな言い回しがあります。

1，2，3，・・・，n の数を並び替えたとき、先頭から数えた順番と数が一致するものが1つもない並べ方

n人がプレゼントをもちよって、バラバラに交換したとき、1人も自分自身の用意したプレゼントをもらわない方法

写像f:{1,2,…,n}→{1,2,…,n}ただし、単射かつ∀i∈{1,2,…,n},f(i)≠i
の総数

これらの場合の数は、n!Σ[k=0,n]{(-1)^k}/k!であることはよく知られています。

そこで、拡張として次の総数を考えるとどうなるのでしょうか？

n≦mとする。
写像f:{1,2,…,n}→{1,2,…,m}ただし、単射かつ∀i∈{1,2,…,n},f(i)≠i
の総数

たとえば、n=3,m=4のとき、
(f(1),f(2),f(3))=(2,1,4),(2,3,1),(2,3,4),(3,1,2),(3,1,4),(3,4,1),(3,4,2),(4,1,2),(4,3,1),(4,3,2)

回答No.1

AssurBanipal · ベストアンサー

＞n≦mとする。
＞写像f:{1,2,…,n}→{1,2,…,m}ただし、単射かつ∀i∈{1,2,…,n},f(i)≠i
＞の総数

求める写像の総数を S(n,m) とする。包除原理より、
S(n,m)
=Σ[k=0,n]{comb(n,k)*((-1)^k)*comb(m-k,n-k)*(n-k)!}
=(n!)*Σ[k=0,n]{((-1)^k)*(m-k)!/((m-n)!*(n-k)!*k!)}. (答)

計算例：
S(3,4)=11,
S(5,9)=8544,
S(11,14)=6581134823.

＞たとえば、n=3,m=4のとき、
＞(f(1),f(2),f(3))=(2,1,4),(2,3,1),(2,3,4),(3,1,2),(3,1,4),(3,4,1),(3,4,2),(4,1,2),
＞(4,3,1),(4,3,2)

上記の10個の写像に加え、
(f(1),f(2),f(3))=(2,4,1)も条件をみたす写像。

お礼

ありがとうございます。
すごいです。
じっくり検討いたします。

回答No.4

tecchan22

あ、まったく一緒でしたね。(>_<)
ごめんなさい。m(＿)m

回答No.3

tecchan22

＃１とやりかたは同じやけど、答えの表現を整理して、

P(m,n)－P(m-1,n-1)×n＋P(m-2,n-2)×C(n,2)－・・・
＝n !Σ[k=0,n](-1)^k (1/k !) C(m-k,n-k)

Pは順列、Cは組み合わせです。

この形だと、ｍ＝ｎのときの拡張になっていることが分かりやすいと思います。