写像12相について

順列、組み合わせなど場合の数の問題で、解答までの流れはおぼろげながら理解できるものの、全体像が今一つすっきりとしない、少し複雑な問題に出くわすと途方に暮れてしまう、ということが起こります。良い方法はないかと模索しているうちに、写像という概念に出会いました。写像の考え方を使うと順列、組み合わせなどの場合の数を少し違った角度から整理することができ、解答への見通しが立てやすくなります。

写像

写像の定義と写像ではないもの

写像とは

写像（mapping）は、定義域（domain）と終域（codomain）という二つの集合の間の対応を表すしくみです。それぞれの集合に含まれているものを要素（element）といい、写像は次の通り定義されます。

定義域は集合X、終域は集合Yというように英大文字を使って表記しますが、N、KのようにX、Y以外の文字を使う場合もあります。写像はfなどの文字で表し、$f:X\longrightarrow Y$のように表記します。

例えば、X={1, 2, 3 ,4}、Y={1, 4, 9,16}として、$y=x^2$という対応を考えます。どの$x$に対しても、$y$が1つ決まるので明らかに写像になります。

次にX={1, 2, 3 ,-3}、Y={1, 4, 9, 16}とし、写像$f\colon X \longrightarrow Y$を$y=x^2$と定義すると、f(1)=1、f(2)=4、f(3)=9、f(-3)=9となります。この対応関係を表したのが図表1です。ここで、集合Yの要素{9}は集合Xの2つの要素{3},{-3}に対応付けられていますが、これも写像の定義を満たしています。

また、集合Yの中には{16}のように集合Xから対応付けられない要素がありますが、これも写像の定義を満たしています。なお、{1, 4, 9}のようにXの要素$x$に対応するYの要素$y$を、fによるXの像（image）または値域（range）といい、$y=f(x)$と表記します。したがって、値域は終域の部分集合といえます。

写像でないもの

写像の定義を確認してみましょう。すると、次のような対応は写像とは言えません。つまり、ある値 𝑥 に対して f(x) を計算しようとしても、対応する値が見つからなかったり、複数あって選べなかったりする場合、その対応は写像とはみなされません。

①　集合Xの要素に対応する要素が集合Ｙに存在しない

集合Xの要素$x$に対して、集合Yの中に対応する$y$が存在しないものがある

X={1, 2, 3, 4}、Y={1, 4, 9}と定義し、$y=x^2$を対応させると、集合Yには16が含まれていないので、f(4)の計算をすることができません。このような対応は写像にはなりません。

②　1つの集合Ｘの要素に対して複数の集合Yの要素が対応する。

X={1, 4, 9}、Y={1, 2, 3, -3}と定義し、「$y$は$x$の平方根」という対応を考えます。集合Xの要素9に対して集合Yの要素が2つ対応していて、どちらを選んでいいのかわからないので、やはり写像にはなりません。

集合Xの要素を１つ選ぶと、それに対応するYの要素が0でも複数でもなく、1つだけ決まるような対応を写像と考えます。

写像の特殊な形態、単射　全射

写像の中には、特別な性質を持つものがあります。それが全射、単射、および両方の性質をもつ全単射です。以下、図表3を見ながらみていきます。

全射

集合 Y のすべての要素に対して、必ず集合 X のどれか1つの要素が対応しているような写像を「全射」と呼びます。対応する X の要素が複数あっても問題ありません。

例えばX={1, 2, 3, -3}、Y={1, 4, 9}と定義し、$y=x^2$を対応させると、集合Yに集合Xに対応する要素$y$は存在しません。このような写像を全射といいます。集合xの-3と3が同じ集合Yの9に対応しますが、全射という上では問題になりません。

少しむつかしいですが記号で書くと次のように定義します。

$\forall y\in Y,\exists x\in X:y=f\left(x\right)$

（任意の y が Y に属するならば、ある x が X に属して y=f(x) を満たすものが存在する"For all y in Y, there exists an x in X such that f(x) = y）

全射は「上へ対応」と呼ぶこともあり、英語ではsurjection, surjective mapping、onto mappingといいます。全射では集合X、Yの要素の数をn(X)、n(Y)とすると、$n(X)\geqq n(Y)$という関係が成り立ちます。

単射

X={1, 2, 3}、Y={1, 4, 9, 16}再び、$y=x^2$という対応を考えます。

Xの異なる要素が、必ずYの異なる要素に対応しているような写像を単射といいます。集合Yには集合Xに対応しない16という要素がありますが、単射と呼ぶ上では問題ありません。

少し難しくなりますが、記号では次のように記述します。

$\forall x,x^{\prime }\in X:\left[ x\not=x^{\prime}\Rightarrow f\left(x\right)\not=f\left(x^{\prime }\right) \right] $

任意の x と x' が X に属するならば、x と x' が等しくないならば、f(x) と f(x') も等しくない。

"For all x and x' in X, if x is not equal to x', then f(x) is not equal to f(x')."

単射は英語ではinjection, injective mapping、one-to-one mapping（一対一写像）といいます。

集合X、集合Yの要素の数を$n(X)$、$n(Y)$とすると、単射の場合は$n(X)\leqq n(Y)$となります。

全単射

全射と単射、両方の条件を満たす写像を全単射といいます。すなわち、集合X の各要素が集合 Y の要素1つに正確に対応し、また集合Yの各要素が集合 Xの要素1つに正確に対応するものをいいます。

英語では、bijective function, bijection、one-to-one onto mapping（1対1上への写像、上への1対1写像）、one-to-one correspondence（1対1対応）といいます。細かいところですが、単射は1対1写像、全単射は1対1対応と紛らわしいので注意が必要です。

全単射は全射と単射の両方を兼ねており、全射は$n(X)\geqq n(Y)$、単射は$n(X)\leqq n(Y)$なので、必然的に全単射であるということは、$n(X)=n(Y)$になります。

逆写像

最後に、逆写像という考え方をご紹介します。図のとおり集合Xから集合Yへの$y=x^2$という写像を考えます。

定義域Xの各要素に対して、終域Yの要素がちょうど1つ対応しているので、この対応関係は写像の条件を満たしています。逆に、$x=\sqrt y$という対応を考えます。集合Yの全ての要素に対して集合Xの1つの要素が対応しているので写像の要件を満たしています。f の逆写像は 集合Yの要素を集合Xの要素に対応させるものであり、$f^{-1}$とあらわします。

ここで、写像fが逆写像$f^{-1}$を持つ意味を考えます。

①逆写像が写像の要件を満たしているということは、集合Yに対して集合Xの要素が複数対応することはありません。ということは、Xの異なる要素が、必ずYの異なる要素に対応することになるので、写像fは単射になります。

②集合Yの中に集合Xと対応していない要素は存在しません。ということは、集合Yのすべての要素が、集合Xの要素のどれかと対応しているので、元の写像fは全射になります。

①、②のことから、逆写像が存在する写像は、全単射であるといえます。

集合Xの個数を数えるのが難しい場合、集合Yと全単射の関係にあることを使い計算する方法があります。この際、全単射であることを証明するために逆写像を使うことがよくあります。

写像ではあるが、全射でも単射でもないケース

写像の条件は満たしているものの、集合 Y に未対応の要素があったり、複数のx が同じy に対応していたりすることがあります。このような対応は、一般に特に名称はありませんが、今後一般の写像（general mapping）と呼ぶようにします。

写像の応用

ここまで写像の基本を説明しました。次に、写像が力を発揮する具体例を２つご紹介します。

鳩の巣原理

うまくやれば、全て$\sqrt 2$より離れた点を打つこともできそうな気もしますし、狭い中に10個も点を打つのだから、どこかのペアは $\sqrt 2$より近くならざるを得ないような気もします。いずれにしても、証明する方法はなかなか思いつきません。こんなときに、単射の考え方が役に立ちます。

次のように正方形を3×3=9個の縦横1㎝のマスに区分けし、9個の点Xから10個のマスYへの写像を考えます。$n(X)\geqq n(Y)$から単射にはならないので、少なくとも2つの点が1つのマスに入ることになります。ところでマスの中の2点は、どんなにもがいても対角線の長さ$\sqrt 2$ より短くなります。ということは、 $\sqrt 2$​ 以下となる2点が存在せざるを得ないことになります。

この考え方を鳩の巣原理（Pigeonhole principle）といい、鳩の数が巣の数より多ければあぶれる鳩が出てしまうという、至極当たり前な考え方です。しかし鳩の巣原理を使うと、すっきりと整理することができます。

逆写像の考え方を使うと解ける問題

次は整数の分割（分割数）といわれる難問です。

(1)は11通りになります。たかだか6のような小さな自然数も、正しく数えるのは大変です。一方、pythonを使うと、次のように少ない行数で計算することができます。

[[1, 1, 1, 1, 1, 1],
 [2, 1, 1, 1, 1],
 [2, 2, 1, 1],
 [2, 2, 2],
 [3, 1, 1, 1],
 [3, 2, 1],
 [3, 3],
 [4, 1, 1],
 [4, 2],
 [5, 1],
 [6]]

7.　再帰関数という面白い考え方を使っています。

Pythonをはじめて間もない方には、さっぱりわからないプログラムだと思いますが、このWEBの最後までお付き合い下されば、こんな簡単なコードで計算できることに感動すると思います。

(2)では逆写像の考え方を使います。

集合Xを6の分割数のうち奇数の和だけで表す数として、[5, 1] [3, 3] [3, 1, 1, 1][1, 1, 1, 1, 1, 1]の4通りとなります。

一方、集合Yをすべて異なる数の和で表す数として [6][5, 1] [4, 2] [3, 2, 1]の4通りとなります。確かにn(X)=n(Y)=4となり確かに問題文の通りとなります。しかし、これは6という小さな値だからたまたまそうなっただけで、もっと大きな数となると何とも言えません。どうすれば証明することができるか途方に暮れてしまいます。

そこで、集合Xから集合Yへの対応として、要素で同じ数nがあれば2ｎに置き換える、その結果さらに同じ数があれば同じ置き換えるという操作を同じ数がなくなるまで繰り返します。この操作では各要素の中の合計が6であることを保ったまま、同じ数字をなくしていくので、最終的には相異なる組み合わせになり、写像である要件を満たしています。

一方、集合Yから集合Xへの対応として、これまでの逆、偶数2nがあれば、それを2で割り、その結果の中に偶数があればさら2で割る操作を偶数がなくなるまで繰り返します。最終的には、偶数がなくなり奇数だけの組み合わせになります。この操作では、各要素の中の合計が6であることを保ったまま、偶数をなくしていくので、最終的には奇数の組み合わせとなり、写像である要件を満たしています。

これらのことから集合Xと集合Y対応は全単射といえます。ということは、n(X)=n(Y)になります。

確かにその通りという気もしますが、騙されたような感覚も拭えません。そこで、nをもっと大きくして、pythonのプログラムを作り確認します。

分割数173525　奇数のみ3264　同じ要素なし3264　うち両方満たす93

1.　前掲のpartition関数を使っています。

上記のように49の分割数は173525となります。以下のサイトでは分割数の数が公開されていますが、確かに合っています。

またこの中で、奇数だけの組み合わせ、相異なるものの組み合わせを計算するとともに3264になり一致します。ちなみにこのうち両方の要件を併せ持つものは93個となります。このような証明は逆写像による全単射を使わないと難しいものと思われます。

区別ありと区別なし

写像で場合の数について整理するうえで、全射や単射などとは異なる視点として、「区別あり(labeled)」と「区別なし(unlabeled)」という考え方があります。次の問題を考えます。

(1)は順列の例になります。集合Nは{0,1,2}、集合K{青,黄,赤,紫,緑}　というようにラベルがついているもの(labeled)と考えます。0,1,2がどの色を選んだかで(青、赤、緑)、(青、緑、赤)、(赤、青、緑)、(赤、緑、青)、(緑、赤、青)、(緑、青、赤)は別の順列として考えます。このように

一方、(2)は組み合わせになり、集合Nに区別がなくなります。この結果、前の6つは同じ組み合わせとなります。例えば(青、赤、緑)がこの6つを代表します。このように、区別なし(unlabeled)といいます。このように、同じ単射の写像でも集合の中で区別があるか無いかで全く異なる対応になります。

このように同じ単射の写像であっても、集合Nの区別の有無により異なる事象を扱うことができます。同じように集合Kについても有無があるので、組み合わせると4通りになります。これに対して、全射、単射、制約なしの3つがあるので12通りになります。これを写像12相(Twelvefold way)といいます。一覧にすると次のようになります。

今後、表にある写像12相についてpythonを使って探求していきます。