部分順列

組合せ数学において、有限集合S上の部分順列、つまり繰り返しのないシーケンスは、Sの指定された 2 つの部分集合間の全単射 である。つまり、等しいサイズの 2 つの部分集合UとVと、UからVへの1 対 1 のマッピングによって定義される。同様に、これは順列に拡張できるS上の部分関数である。^{[1] [2]}

集合Sが単に最初のn個の整数の集合 {1, 2, ..., n } である場合を考えるのが一般的です。この場合、部分順列はn個の記号の文字列で表すことができます。これらの記号の一部は 1 から までの範囲の異なる数字で、残りは特別な「穴」記号 ◊ です。この定式化では、部分順列のドメインU は文字列内の穴を含まない位置で構成され、各位置はその位置の数字にマッピングされます。たとえば、文字列 "1 ◊ 2" は、1 をそれ自身にマッピングし、3 を 2 にマッピングする部分順列を表します。^[3] 2 つの項目の 7 つの部分順列は次のとおりです 。${\displaystyle n}$

◊◊、◊1、◊2、1◊、2◊、12、21。

n = 0, 1, 2, ... の場合のn個のアイテムの部分順列の数は、整数列で与えられる。

1、2、7、34、209、1546、13327、130922、1441729、17572114、234662231、...（OEISのシーケンスA002720）

ここで、シーケンスの n番目の項目は、合計式によって与えられます。

${\displaystyle \sum _{i=0}^{n}i!{\binom {n}{i}}^{2}}$

ここで、i番目の項は、サイズiのサポートを持つ部分順列の数、つまりi 個の非ホール要素を持つ部分順列の数を数える。あるいは、再帰関係によって計算することもできる。

${\displaystyle P(n)=2nP(n-1)-(n-1)^{2}P(n-2).}$

これは次のように決定されます。

1. ${\displaystyle P(n-1)}$各集合の最後の要素を省略した部分順列:
2. ${\displaystyle P(n-1)}$各セットの最後の要素が互いにマッピングされる部分的な順列。
3. ${\displaystyle (n-1)P(n-1)}$最初のセットの最後の要素は含まれるが、2 番目のセットの最後の要素にはマッピングされない部分的な順列
4. ${\displaystyle (n-1)P(n-1)}$2 番目のセットの最後の要素は含まれるが、最初のセットの最後の要素にはマッピングされない部分的な順列
5. ${\displaystyle -(n-1)^{2}P(n-2)}$、カウント 3 と 4 の両方に含まれる部分順列、つまり、両方のセットの最終要素が含まれるが、互いにマッピングされない順列。

一部の著者は、部分順列を制限して、一対一のドメイン^[4] または値域^{[3]のいずれかが、ある}kに対して、順列されるn個の項目の集合の最初のk個の項目で構成されるように強制します。前者の場合、n集合からの長さkの部分順列は、 n集合からのk個の項の繰り返しのないシーケンスにすぎません。(初等組合せ論では、これらのオブジェクトはn集合の「 k順列」と呼ばれることもあり、紛らわしいです。)