完全順列 サブファクトリアル電卓

完全順列 サブファクトリアル電卓へようこそ。この電卓は、n個の要素のセットに対する完全順列の数を計算する、包括的な組合せ論ツールです。完全順列とは、どの要素も元の位置に現れない並べ替えのことで、!n または D(n) と表記されます。組合せ論の学習、古典的な帽子チェック問題の解決、あるいは確率論の探求など、本ツールはインタラクティブな視覚化と共に、詳細なステップバイステップの解決策を提供します。

完全順列（攪乱順列）とは？

完全順列（またはサブファクトリアル、攪乱順列）とは、集合の要素を並べ替える際、どの要素も元の位置に現れない順列のことです。n個の要素の完全順列の数は !n（nの前に感嘆符を置く）または D(n) と書かれます。

例えば、{1, 2, 3} という位置にある3つの項目を考えます。全部で 3! = 6 通りの順列がありますが、完全順列は以下の2通りだけです：

• (2, 3, 1) — 項目1が位置2へ、項目2が位置3へ、項目3が位置1へ移動
• (3, 1, 2) — 項目1が位置3へ、項目2が位置1へ、項目3が位置2へ移動

したがって、 !3 = 2 となります。

完全順列の公式

包含除外原理による公式

最も基本的な公式は包含除外原理から導かれます：

再帰公式

完全順列は再帰的に計算することもできます：

基本ケース： !0 = 1, !1 = 0

最近整数公式

\(n \geq 1\) の場合、サブファクトリアルは \(n!/e\) に最も近い整数に等しくなります：

帽子チェック問題

完全順列の最も有名な応用例は、帽子チェック問題（problème des rencontres）です。n人の客が帽子を預け、帽子をランダムに返した場合、誰一人として自分の帽子を受け取らない確率はいくらでしょうか？

その答えは \(!n / n!\) で、これは非常に速く \(1/e \approx 0.3679\) に収束します。つまり、要素の数に関わらず、すべてのランダムな順列の約 36.8% が完全順列になります。

本電卓の使い方

1. nを入力： 要素の数（0から170まで）を入力します。クイック例ボタンを使って一般的な値を試すこともできます。
2. 計算： 「!n を計算」をクリックして、完全順列の数を求めます。
3. 結果を確認： !n、n!、完全順列の確率、および 1/e との比率を確認します。
4. アニメーションを探索： 小さなnの場合、アニメーションを操作して完全順列がどのように機能するかを視覚的に確認できます。
5. ステップを学習： 包含除外原理の詳細な内訳と完全順列テーブルを調べます。

最初の15個の完全順列数

完全順列の応用

シークレット・サンタ / プレゼント交換

シークレット・サンタのプレゼント交換を企画する際、各参加者が名前を引きます。誰も自分の名前を引かない「成功した」組み合わせが完全順列です。例えば10人のグループの場合、合計3,628,800通りの組み合わせのうち、有効な組み合わせは1,334,961通りあります。

暗号学と符号理論

完全順列は、置換暗号や誤り訂正符号の分析に登場します。「固定点がない」という概念は、暗号の強度や置換ベースの暗号化を理解する上で重要です。

カードのシャッフルとゲーム

カードゲームにおいて、完全順列はシャッフル後にどのカードも元の位置に戻らない確率を測る指標となります。これはシャッフルの質やゲームの公平性を分析するのに役立ちます。

確率論

完全順列は包含除外原理のエレガントな例を提供し、確率がいかにシンプルな極限（この場合は 1/e）に収束するかを明確に示しています。

主な特性

• 比率 \(!n/n!\) は \(n \to \infty\) のとき \(1/e \approx 0.367879\) に収束します
• 収束は非常に速く、n = 10 の時点ですでに小数点以下6桁まで正確です
• \(!n\) は次の漸化式を満たします： \(!n = n \cdot !(n-1) + (-1)^n\)
• 指数型母関数は \(e^{-x}/(1-x)\) です
• \(!0 = 1\) （空の順列は定義上、空の完全順列とみなされます）

よくある質問

完全順列とは何ですか？

完全順列とは、集合の要素の並べ替えのうち、どの要素も元の位置に現れないもののことです。例えば、要素が {1, 2, 3} の場合、(2, 3, 1) はどの要素も元の場所にないため完全順列です。n個の要素の完全順列の数は !n（サブファクトリアル n）と表記されます。

サブファクトリアル !n の公式は何ですか？

サブファクトリアル !n は包含除外原理を用いて計算できます： \(!n = n! \times \sum_{k=0}^{n} (-1)^k / k!\)。また、再帰的に計算することも可能です： \(!n = (n-1)(!(n-1) + !(n-2))\)、ただし !0 = 1, !1 = 0 です。別の便利な公式として、\(n \geq 1\) のとき \(!n = \text{round}(n! / e)\) もあります。

ランダムな順列が完全順列である確率は？

n個の要素のランダムな順列が完全順列である確率は、nが増えるにつれて \(1/e \approx 0.3679\) に近づきます。nが小さくてもこの近似は非常に正確です。例えば n = 5 の場合、正確な確率は 44/120 ≈ 0.3667 であり、1/e に非常に近い値となります。

帽子チェック問題とは何ですか？

帽子チェック問題（別名：出会いの問題）は、古典的な確率パズルです。n人の客が帽子を預け、帽子がランダムに返却された場合、誰一人として自分の帽子を受け取らない確率はいくらか？という問いです。答えは完全順列の数 !n を全順列の数 n! で割ったもので、\(1/e \approx 36.79\%\) に収束します。

完全順列と階乗の関係は何ですか？

完全順列 (!n) と階乗 (n!) は密接に関連しています： \(!n = n! \times \sum(-1)^k/k!\) (k=0からn)。比率 !n/n! は完全順列の確率を与え、1/e に収束します。また、n ≥ 1 のとき、!n は n!/e に最も近い整数となるため、n!/e は非常に便利な近似になります。

追加リソース

• 攪乱順列 - Wikipedia
• 包含除外原理 - Wikipedia
• OEIS A000166 - サブファクトリアル数列（英語）