組合せ論において、写像12相（しゃぞうじゅうにそう、英: twelvefold way）とは、有限集合の間の写像の数え上げ問題を、12種に、体系的に分類したものである。
順列、組合せ、多重集合、集合の分割、自然数の分割の数を求める古典的な数え上げ問題を含む。
12種類に分類するというアイデアは、数学者・哲学者であるジャン・カルロ・ロタによって与えられた。
概要
有限集合 N と X、それらの濃度 と を定める。
ここで考えたい一般的な問題は、写像 の同値類の数え上げである。
写像 f に、次の3つの条件のいずれかを適用する：
- 条件なし：f は N を X の任意の b に写さなくても（写しても）よい。また、ある b に、N の複数の a を写してもよい。
- f は単射である：f が写した X の値 f(a) は、互いに異なる。言い換えると、f は、X のどの b にも複数回写すことはない（高々 1回である）。
- f は全射である：f は N を X の全ての b に写す。言い換えると、f は、X のどの b にも N から写している。
（条件2. かつ 3. の場合は「f は全単射である」となる。これは n = x の場合のみ成立可能である。）
写像 f に、4種類の同値関係が定義される：
結局、写像 f に適用する条件は、上記の3条件と4つの同値関係の、3 × 4 = 12通りがある。
写像の同値類を数え上げる12種の問題は、各々は同じ難易度ではなく、また、これらを統一的に解く方法は知られていない。12種の問題のうち、2つの問題は自明（同値類の数は0または1）であり、5つの問題は解が n, x の乗法的な公式で与えられる。残る5つの問題は、組合せに関わりのある関数（スターリング数、分割数など）によって解が与えられる。
観点
写像12相における問題を考えるにあたり、集合と写像による現代数学の記法を身近で具体的な例（またはいくつかの同様の視覚化）に置き換えて説明し理解することができる。
球と箱
伝統的に、写像12相での問題の多くは、「有限個の球全てを有限個の箱にどのように入れるか」といったモデルで説明されてきた。集合 N を有限個の球からなる集合、集合 X を有限個の箱からなる集合とし、写像 ƒ : N → X は、それぞれの球 a を箱 ƒ(a) に入れる操作に置き換えて考えることができる。
f が単射であることは、「箱に入る球は1個だけ」、f が全射であることは「箱には必ず球を入れる」に対応する。
N の置換による違いを同一視するのは「球を区別しない」、X の置換による違いを同一視するのは「箱を区別しない」に対応する。
公式
| 写像の 同値類 | 条件なし | 単射 | 全射 |
|---|---|---|---|
| f | X の点の n点数列 重複順列 | X の n点順列 順列（下降階乗冪） | N の x人への集合分配 |
| f ∘ Sn | X の n点部分多重集合 重複組合せ | X のn点部分集合 組合せ | n個の x人への分配 組合せ |
| Sx ∘ f | N の x個以下への集合分割 ベル数 | N の x個以下への要素分割 (0 or 1) | N の x個への集合分割 スターリング数(第2種) |
| Sx ∘ f ∘ Sn | n の x個以下への和分解 分割数 | n の x個以下への単位分割 (0 or 1) | n の x個への和分解 分割数 |
関連項目
外部リンク
- 『写像12相（場合の数の有名問題）』 - 高校数学の美しい物語