順列と組み合わせ

順列は対象の順序付けられた配置を数え、組み合わせは順序付けられていない選択を数えます。これらは共に、数え上げの基本的な核を形成します。

Definition

集合の順列とは、その要素の順序付けられた配置（または集合からそれ自身への全単射）であり、組み合わせとは、集合から固定された数の要素を順序付けずに選択することです。

Scope

このトピックでは、配置（繰り返しあり・なし）、選択、およびその洗練された形式（攪乱順列、円順列、制限された位置を持つ順列を含む）の数え上げについて展開します。また、降下、転倒、サイクル構造などの順列統計を導入し、初等的な数え上げと対称群のより豊かな現代理論との関連性を示します。

Core questions

• n個の異なるオブジェクトを順序付ける方法は何通りありますか、またそのうちr個を順序付ける方法は何通りありますか？
• 繰り返しと区別不能性は、配置の数にどのように影響しますか？
• 攪乱順列とは何ですか、またランダムな順列がどのくらいの頻度で要素を固定しないのですか？
• 順列に関するどの統計量が等分布していますか？

Key concepts

• 階乗と下降階乗
• 繰り返しあり・なしの配置
• 攪乱順列
• 円順列
• 転倒と降下
• スターリング数

Key theories

順列のサイクル分解

すべての順列は互いに素なサイクルに一意に分解されます。サイクル型による順列の数え上げは、第一種スターリング数によって支配され、対称群の構造の基礎となります。

攪乱順列の数え上げ

不動点を持たない順列の数は、包除原理によって導出され、n!/eに近づきます。これは、順列の約37%が攪乱順列であるという古典的な結果を与えます。

Clinical relevance

順列と組み合わせの数は、確率（等確率の事象）、ソートおよびシャッフルアルゴリズム、実験計画、および暗号鍵空間において現れます。これらの分野では、配置空間のサイズが難易度とセキュリティを決定します。

History

順列の組み合わせ論は、20世紀初頭のマクマホンによる組み合わせ解析に関する研究によって体系化され、後に順列統計の現代理論を通じて深化しました。

Key figures

• Percy MacMahon
• Richard P. Stanley

Seminal works

• stanley2011

Frequently asked questions

n個の要素を持つ集合にはいくつの順列がありますか？

n個の順列があります。これはnまでのすべての正の整数の積であり、n個の各位置が異なる残りの要素で埋められるためです。

攪乱順列とは何ですか？

攪乱順列とは、どの要素も元の位置に残らない順列のことです。例えば、手紙がどの封筒にも戻らないようなシャッフルがこれにあたります。