乱列の総数
組み合わせ、順列の問題で具体例を挙げてみたものの、本の公式と計算結果が合わないので質問します。
問題 n個のものの集合のなかで、r個の指定された要素をすべて動かすような置換の総数をもとめよ。
置換はある集合の要素を互いに入れ替えること、nCrを(n,r)と表記し、Aの補集合をAバーと表記し、|A|で集合Aの要素の個数を表します。お願いします。
解 その集合の要素を{1,2,3,・・・・,n}という番号で表す。その置換の総数はn個のものの順列の総数n!であることに注意する。1,2,3,・・・・,rを動かさないすべての置換の集合をそれぞれ、A_1,A_2,A_3,・・・A_rで表す。
|A_1バー∧A_2バー∧A_3バー∧・・・∧A_ｒバー|=n!-(r,1)(n-1)!+(r,2)(n-2)!・・・
+(-1)^(r-1)(r,r-1)(n-r+1)!+(-1)^r(r,r)(n-r)! ・・・・(★)
本では、ここですべての要素を動かすとするとr=nだから、(★)のrをnに書き換えて、完全(攪乱)順列の数を求めていました。
自分はn=4,r=3の場合を具体例をあげて求めてみました。
1,2,3をうごかす 2,3,1と3,1,2。1,2,4をうごかす 2,4,1と4,1,2。1,3,4をうごかす 3,4,1と4,1,3。2,3,4をうごかす 3,4,2と4,2,3。と8通りでしたが、n=4,r=3を(★)に代入すると、4!-(3,1)3!+(3,2)2!+(-1)^(3)1!=11でした。
自分がどこを間違えて、具体例と計算結果が合わなくなったかをどなたか教えてください。お願いします。
補足
全数検索であるため、というような内容の文章があるだけでした。 具体的にO(2＾n)になる理由の説明はありませんでした。 誠に申し訳ありません。 まだ、解決できておりませんが、回答を締め切らせて頂きます。 急ぐ必要がなくなりましたので、図書館などで、他の書籍をみて 調べてみたいと思います。 せっかく回答を頂いたのにすみません。