順列：順序付き配列、数え上げの公式、一般的な表現方法
順列の概要。異なる要素の順序付き配列、階乗と多項係数による数え上げ、互換、巡回置換・リストによる表現、および数学・計算機科学・統計学での代表例を解説します。
順列とは、ある集合の要素を特定の順序で並べたものを指す。言い換えると、異なる項目からなる集まりがあるとき、順列はそれらを選んだ順番で列挙した特定の並びである。この概念は数学で広く用いられるほか、計算機科学や統計学など多くの応用分野でも利用される。
定義と基本的な考え方
順列は、配置や整列と考えることができる。与えられた対象の集合について、異なる並べ方はそれぞれ異なる順列として数える。2つの項目の位置を入れ替えると別の順列になり、ある項目を新しい位置へ移して他の項目をずらす場合も、別の順列が得られる。
画像ギャラリー
1 画像
順列の数え上げ
異なる対象がn個あるとき、n個すべての順列の総数はnの階乗であり、n!と書く。これは1・2・3・…・nに等しい。たとえば、異なる3つの項目は3! = 6通りに並べられる。
一部の対象が同一である場合、異なる順列の数はより少なくなる。n個の項目に、それぞれn1、n2、…、nk個からなる同一項目のグループが含まれ、n1 + n2 + … + nk = nであるとき、異なる並びの数は次の式で表される。
n! / (n1! n2! … nk!)
これは、同一の項目どうしだけを交換しても、新たに区別できる配置は生じないためである。
一般的な例
- 座席配置：テーブルの周囲や車内の決まった座席に人が座る方法の違いは、人の順列である。
- 単語と文字：文字の並び順が異なれば異なる文字列になる。たとえばA、B、Cの3文字には、ABC、ACB、BAC、BCA、CAB、CBAという6つの順列がある。
補足
- 2つの要素を単純に入れ替える操作は互換と呼ばれる。どの順列も、互換を列として行うことで構成できる。
- 順列には複数の表現方法がある。各位置の行き先を示すリストによる表現や、要素が位置間をどのように移動するかに従って要素をまとめる巡回置換の表記がある。
関連項目
著者
AlegsaOnline.com 順列：順序付き配列、数え上げの公式、一般的な表現方法 Leandro Alegsa
URL: https://ja.alegsaonline.com/art/75877