組合せ論において、写像12相(しゃぞうじゅうにそう、twelvefold way)とは、2つの有限集合に関する12種の数え上げ問題を体系的に分類したものである。

順列(permutation)、組合せ(combination)、多重集合(multiset)、集合の分割(partition of a set)、自然数の分割(partition of a number) の数を求める古典的な数え上げ問題を含む。

12種類に分類するというアイデアは、数学者・哲学者であるジャン・カルロ・ロタによって与えられた。

概要編集

有限集合 NX、それらの濃度   を定める。

考えるべき一般的な問題は、関数  同値類(Equivalence class)の数え上げである。

関数には、次の3つの制限(条件)のいずれかが適用される:

1. 条件なし:Nのそれぞれのaは、fによってXの任意のbに写される。 また、この写像は複数回発生し得る。

2. f単射である:Naのそれぞれの値 は、互いに異なる必要がある。故にXのそれぞれのbは、fとして最大1回発生し得る。

3. f全射である:Xのそれぞれのbについて、 となるようなNの少なくとも一つのaが必要である。故にXのそれぞれのbは、fの像として少なくとも1回発生する。

(上記3項目の他に、条件としての「fは全単射である」は、 である場合に適用可能であるが、これは「fは単射である」且つ「fは全射である」である、ことと等価である。)

関数fにおいて、4つの異なる同値関係が定義される:

1. 等しい(Equality)

2. N置換(Permutation)による差異を除いて(up to)、等しい

3. Xの置換による差異を除いて、等しい

4. NおよびXの置換による差異を除いて、等しい

関数の3つの条件と4つの同値関係は、3 × 4 = 12通りに組み合わせることができる。

関数の同値類を数え上げる12種の問題は、各々は同じ難易度ではなく、また、それらを解くための1つの体系的な方法は存在しない。12種の問題の内、2つの問題は自明(同値類の数は0または1)であり、5つの問題はnxの乗法的な公式によって解が与えられる。残る5つの問題は組合せに関わりのある関数(スターリング数分割数など)によって解が与えられる。

観点編集

写像12相における問題を考えるにあたり、いくつかの異なる観点からこれらを理解することができる。

ボールと箱編集

伝統的に、写像12相での問題の多くは、関数を定義する代わりに、「ボールを箱にどのように入れるか」(またはいくつかの同様の視覚化)といった観点により定式化されてきた。集合(以下、集合は有限集合を指すものとする)Nはボールを元とする集合として、集合Xは箱を元とする集合として、それぞれ同一であるとみなすことができる。そのため、関数ƒ : NXは、ボールを箱に入れる、それぞれのボールaをそれぞれの箱ƒ(a)に入れる、といった形として表現できる。このように、一意である像をその定義域(domain)の各々の元に帰するという関数の性質は、どのボールも1つの箱のみに入ることができる(尚且つ、箱に入っていないボールがあってはならない)という性質によって反映されている。それ故に、どの箱も(原則として)任意の個数のボールを収容することができる。

サンプリング編集

ラベリング、取り出し、グルーピング編集

ラベリング、取り出し(一緒に取り出すか・取り出さないか)の反復編集

集合と自然数の分割編集

公式編集

12種類の対象と数え上げの公式
f-class Any f Injective f Surjective f
f n-sequence in X
 

重複順列
n-permutation of X
 

順列
下降階乗冪
composition of N with x subsets
 
f ∘ Sn n-multisubset of X
 

重複組合せ
n-subset of X
 

組合せ
composition of n with x terms
 

重複組合せ
Sxf partition of N into ≤ x subsets
 

ベル数
partition of N into ≤ x elements
 

( 0 又は 1)
partition of N into x subsets
 

スターリング数(第2種)
Sxf ∘ Sn partition of n into ≤ x parts
 

分割数
partition of n into ≤ x parts 1
 

( 0 又は 1)
partition of n into x parts
 

分割数

行と列の直感的な理解編集

一般化編集

写像20相編集

関連項目編集