写像12相

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

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

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

概要

有限集合 N と X、それらの濃度$n=|N|$ と $x=|X|$ を定める。

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

関数には、次の3つの制限（条件）のいずれかが適用される：

1. 条件なし：Nのそれぞれのaは、fによってXの任意のbに写される。 また、この写像は複数回発生し得る。
2. fは単射である：Nのaのそれぞれの値$f(a)$は、互いに異なる必要がある。ゆえにXのそれぞれのbは、fの像として最大1回発生し得る。
3. fは全射である：Xのそれぞれのbについて、$f(a)=b$となるようなNの少なくとも一つのaが必要である。ゆえにXのそれぞれのbは、fの像として少なくとも1回発生する。

（上記3項目の他に、条件としての「fは全単射である」は、$n=x$である場合に適用可能であるが、これは「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つの問題はnとxの乗法的な公式によって解が与えられる。残る5つの問題は、組合せに関わりのある関数（スターリング数、分割数など）によって解が与えられる。

観点

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

ボールと箱

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

公式

12種類の対象と数え上げの公式

f-class	Any f	Injective f	Surjective f
f	n-sequence in X $x^{n}$ 重複順列	n-permutation of X $x^{\underline {n}}$ 順列 下降階乗冪	composition of N with x subsets $\textstyle x!\{{n \atop x}\}$
f ∘ Sn	n-multisubset of X ${\binom {x+n-1}{n}}$ 重複組合せ	n-subset of X ${\binom {x}{n}}$ 組合せ	composition of n with x terms ${\binom {n-1}{n-x}}$ 重複組合せ
Sx ∘ f	partition of N into ≤ x subsets $\sum _{k=0}^{x}\left\{{n \atop k}\right\}$ ベル数	partition of N into ≤ x elements $[n\leq x]$ ( 0 又は 1)	partition of N into x subsets $\left\{{n \atop x}\right\}$ スターリング数(第2種)
Sx ∘ f ∘ Sn	partition of n into ≤ x parts $p_{x}(n+x)$ 分割数	partition of n into ≤ x parts 1 $[n\leq x]$ ( 0 又は 1)	partition of n into x parts $p_{x}(n)$ 分割数

関連項目

• Permutation (曖昧さ回避)
• 置換 (数学)
• 集合の分割
• 自然数の分割
• 重複置換 (同じものを含む順列)
• 完全順列 (攪乱順列)
• 多重集合
• 写像