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

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

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

概要

編集

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

ここで考えたい一般的な問題は、写像  同値類数え上げである。

写像 f に、次の3つの条件のいずれかを適用する:

  1. 条件なし:fNX の任意の b に写さなくても(写しても)よい。また、ある b に、N の複数の a を写してもよい。
  2. f単射である:f が写した X の値 f(a) は、互いに異なる。言い換えると、f は、X のどの b にも複数回写すことはない(高々 1回である)。
  3. f全射である:fNX の全ての b に写す。言い換えると、f は、X のどの b にも N から写している。

(条件2. かつ 3. の場合は「f全単射である」となる。これは n = x の場合のみ成立可能である。)

写像 f に、4種類の同値関係が定義される:

  1. 等しい
  2. N置換による違いを除いて、等しい
  3. X の置換による違いを除いて、等しい
  4. N および X の置換による違いを除いて、等しい

結局、写像 f に適用する条件は、上記の3条件と4つの同値関係の、3 × 4 = 12通りがある。

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

観点

編集

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

球と箱

編集

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

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

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

公式

編集
12種類の対象と数え上げの公式
写像の
同値類
条件なし 単射 全射
f X の点の n点数列
 

重複順列
Xn点順列
 

順列(下降階乗冪
Nx人への集合分配
 
f ∘ Sn Xn点部分多重集合
 

重複組合せ
Xn点部分集合
 

組合せ
n個の x人への分配
 

組合せ
Sxf Nx個以下への集合分割
 

ベル数
Nx個以下への要素分割
 

(0 or 1)
Nx個への集合分割
 

スターリング数(第2種)
Sxf ∘ Sn nx個以下への和分解
 

分割数
nx個以下への単位分割
 

(0 or 1)
nx個への和分解
 

分割数

関連項目

編集

外部リンク

編集