写像12相

組合せ論において、写像12相（しゃぞうじゅうにそう、テンプレート:Lang-en-short）とは、有限集合の間の写像の数え上げ問題を、12種に、体系的に分類したものである。

順列、組合せ、多重集合、集合の分割、自然数の分割の数を求める古典的な数え上げ問題を含む。

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

概要

有限集合 テンプレート:Mvar と テンプレート:Mvar、それらの濃度 $|N|=n$ と $|X|=x$ を定める。

ここで考えたい一般的な問題は、写像 $f:N\to X$ の同値類の数え上げである。

写像 テンプレート:Mvar に、次の3つの条件のいずれかを適用する：

1. 条件なし：テンプレート:Mvar は テンプレート:Mvar を テンプレート:Mvar の任意の テンプレート:Mvar に写さなくても（写しても）よい。また、ある テンプレート:Mvar に、テンプレート:Mvar の複数の テンプレート:Mvar を写してもよい。
2. テンプレート:Mvar は単射である：テンプレート:Mvar が写した テンプレート:Mvar の値 テンプレート:Math2 は、互いに異なる。言い換えると、テンプレート:Mvar は、テンプレート:Mvar のどの テンプレート:Mvar にも複数回写すことはない（高々 1回である）。
3. テンプレート:Mvar は全射である：テンプレート:Mvar は テンプレート:Mvar を テンプレート:Mvar の全ての テンプレート:Mvar に写す。言い換えると、テンプレート:Mvar は、テンプレート:Mvar のどの テンプレート:Mvar にも テンプレート:Mvar から写している。

（条件2. かつ 3. の場合は「テンプレート:Mvar は全単射である」となる。これは テンプレート:Math2 の場合のみ成立可能である。）

写像 テンプレート:Mvar に、4種類の同値関係が定義される：

1. 等しい
2. テンプレート:Mvar の置換による違いを除いて、等しい
3. テンプレート:Mvar の置換による違いを除いて、等しい
4. テンプレート:Mvar および テンプレート:Mvar の置換による違いを除いて、等しい

結局、写像 テンプレート:Mvar に適用する条件は、上記の3条件と4つの同値関係の、テンプレート:Math2通りがある。

写像の同値類を数え上げる12種の問題は、各々は同じ難易度ではなく、また、これらを統一的に解く方法は知られていない。12種の問題のうち、2つの問題は自明（同値類の数は0または1）であり、5つの問題は解が テンプレート:Math2 の乗法的な公式で与えられる。残る5つの問題は、組合せに関わりのある関数（スターリング数、分割数など）によって解が与えられる。

観点

写像12相における問題を考えるにあたり、集合と写像による現代数学の記法を身近で具体的な例（またはいくつかの同様の視覚化）に置き換えて説明し理解することができる。

球と箱

伝統的に、写像12相での問題の多くは、「有限個の球全てを有限個の箱にどのように入れるか」といったモデルで説明されてきた。集合 N を有限個の球からなる集合、集合 X を有限個の箱からなる集合とし、写像 テンプレート:Math2 は、それぞれの球 a を箱 ƒ(a) に入れる操作に置き換えて考えることができる。

f が単射であることは、「箱に入る球は1個だけ」、f が全射であることは「箱には必ず球を入れる」に対応する。

N の置換による違いを同一視するのは「球を区別しない」、X の置換による違いを同一視するのは「箱を区別しない」に対応する。

公式

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

写像の 同値類	条件なし	単射	全射
テンプレート:Mvar	X の点の n点数列 $x^n$ 重複順列	X の n点順列 $x^{\underset{\_}{n}}$ 順列（下降階乗冪）	N の x人への集合分配 $x!\left\{\genfrac{}{}{0ex}{}{n}{x}\right\}$
テンプレート:Math	X の n点部分多重集合 $(\genfrac{}{}{0ex}{}{x+n-1}{n})$ 重複組合せ	X のn点部分集合 $(\genfrac{}{}{0ex}{}{x}{n})$ 組合せ	n個の x人への分配 $(\genfrac{}{}{0ex}{}{n-1}{x-1})$ 組合せ
テンプレート:Math	N の x個以下への集合分割 $\sum _{k=0}^x\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$ ベル数	N の x個以下への要素分割 $[n\le x]$ (0 or 1)	N の x個への集合分割 $\left\{\genfrac{}{}{0ex}{}{n}{x}\right\}$ スターリング数(第2種)
テンプレート:Math	n の x個以下への和分解 $p_x(n+x)$ 分割数	n の x個以下への単位分割 $[n\le x]$ (0 or 1)	n の x個への和分解 $p_x(n)$ 分割数

関連項目

• Permutation（曖昧さ回避）
• 置換 (数学)
• 集合の分割
• 自然数の分割
• 重複置換
• 完全順列
• 多重集合
• 写像

外部リンク

• テンプレート:高校数学の美しい物語