写像12相のソースを表示

[[組合せ数学|組合せ論]]において、'''写像12相'''（しゃぞうじゅうにそう、{{lang-en-short|twelvefold way}}）とは、[[有限集合]]の間の[[写像]]の[[数え上げ]]問題を、12種に、体系的に分類したものである。

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

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

== 概要 ==
有限集合 {{mvar|N}} と {{mvar|X}}、それらの[[濃度 (数学)|濃度]] <math>|N|=n</math> と <math>|X|=x</math> を定める。

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

写像 {{mvar|f}} に、次の3つの[[論理包含|条件]]のいずれかを適用する：
# 条件なし：{{mvar|f}} は {{mvar|N}} を {{mvar|X}} の任意の {{mvar|b}} に写さなくても（写しても）よい。また、ある {{mvar|b}} に、{{mvar|N}} の複数の {{mvar|a}} を写してもよい。
# {{mvar|f}} は[[単射]]である：{{mvar|f}} が写した {{mvar|X}} の値 {{math2|''f''(''a'')}} は、互いに異なる。言い換えると、{{mvar|f}} は、{{mvar|X}} のどの {{mvar|b}} にも複数回写すことはない（[[高々 (数学)|高々]] 1回である）。
# {{mvar|f}} は[[全射]]である：{{mvar|f}} は {{mvar|N}} を {{mvar|X}} の全ての {{mvar|b}} に写す。言い換えると、{{mvar|f}} は、{{mvar|X}} のどの {{mvar|b}} にも {{mvar|N}} から写している。
（条件2. かつ 3. の場合は「{{mvar|f}} は[[全単射]]である」となる。これは {{math2|1=''n'' = ''x''}} の場合のみ成立可能である。）

写像 {{mvar|f}} に、4種類の[[同値関係]]が定義される：
# [[等式|等しい]]
# {{mvar|N}} の[[置換 (数学)|置換]]による[[違いを除いて]]、等しい
# {{mvar|X}} の置換による違いを除いて、等しい
# {{mvar|N}} および {{mvar|X}} の置換による違いを除いて、等しい
結局、写像 {{mvar|f}} に適用する条件は、上記の3条件と4つの同値関係の、{{math2|1=3 × 4 = 12}}通りがある。

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

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

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

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

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

== 公式 ==
{|class="wikitable" style="margin-left:auto;margin-right:auto;text-align:center;border:none"
|+12種類の対象と数え上げの公式
!写像の<br />同値類
!条件なし
!単射
!全射
|-
<!--|{{mvar|f}} 
|[[#case f|any function ''f'': ''N'' → ''X'' ]]
|[[#case i|injective function ''f'': ''N'' → ''X'']]
|[[#case s|surjective function ''f'': ''N'' → ''X'']]
|{{mvar|f}} 
|- -->
!{{mvar|f}} 
|[[#case f|''X'' の点の ''n''点数列<br /><math>x^n</math>]]<br />[[重複順列]]
|[[#case i|''X'' の ''n''点順列<br /><math>x^{\underline n}</math>]]<br />[[順列]]（下降[[階乗冪]]）
|[[#case s|''N'' の ''x''人への集合分配<br /><math>x! \left\{ {n\atop x} \right\}</math>]]
|-
!{{math|''f'' ∘ S{{sub|''n''}}}} 
|[[#case fn|''X'' の ''n''点部分多重集合<br /><math>\binom{x+n-1}n</math>]]<br />[[重複組合せ]]
|[[#case in|''X'' の''n''点部分集合<br /><math>\binom xn</math>]]<br />[[組合せ]]
|[[#case sn|''n''個の ''x''人への分配<br /><math>\binom{n-1}{x-1}</math>]]<br />組合せ
|-
!{{math|S{{sub|''x''}} ∘ ''f''}} 
|[[#case fx|''N'' の ''x''個以下への集合分割<br /><math>\textstyle\sum\limits_{k=0}^x \displaystyle\left\{ {n\atop k} \right\}</math>]]<br />[[ベル数]]
|[[#case ix|''N'' の ''x''個以下への要素分割<br /><math>[n\leq x]</math>]]<br />(0 or 1)
|[[#case sx|''N'' の ''x''個への集合分割<br /><math>\left\{{n\atop x}\right\}</math>]]<br />[[スターリング数]](第2種)
|-
!{{math|S{{sub|''x''}} ∘ ''f'' ∘ S{{sub|''n''}}}} 
|[[#case fnx|''n'' の ''x''個以下への和分解<br /><math>p_x(n+x)</math>]]<br />[[分割数]]
|[[#case inx|''n'' の ''x''個以下への単位分割<br /><math>[n\leq x]</math>]]<br />(0 or 1)
|[[#case snx|''n'' の ''x''個への和分解<br /><math>p_x(n)</math>]]<br />[[分割数]]
|}

== 関連項目 ==
* [[Permutation]]（曖昧さ回避）
* [[置換 (数学)]]
* [[集合の分割]]
* [[自然数の分割]]
* [[重複置換]]
* [[完全順列]]
* [[多重集合]]
* [[写像]]

== 外部リンク ==
* {{高校数学の美しい物語|893|写像12相（場合の数の有名問題）}}

{{DEFAULTSORT:しやそうしゆうにそう}}
[[Category:組合せ論]]
[[Category:置換]]
[[Category:数学に関する記事]]
[[Category:名数12]]