問題3.nを3以上の自然数とする. このとき、以下の問いに答えよ. (1) {1,2,3,....n} から {1,2} への全射写像が2"2個であることを証明せよ。 (2) {1,2.3.....n} から{1.2.3} への全射写像が3" -3-2" +3個であることを数学的帰納法を用い て証明せよ。 (ヒント: (1) 全射ではない写像は像が1だけか, 2だけということになります。 (2) 数学的帰納法を用 いずとも証明はできますが、ここでは解き方を制限します。 写像 f: {1.2.3.....nn+1} {1,2,3} において,fの定義域を {1.2.3..... n} に制限することによりf': {1.2.3....,n} {1,2,3}が定まり ます(要するに, n +1の部分を忘れてしまう)。 ここで,f': {1,2,3....,n} {1,2,3}が全射であっ たものはf(n+1) の像はなんでも考えられます. f': {1,2,3,....n}{1,2,3} が定値写像ではない が全射でなかった場合はn+1の像はf' の写像の像に属していない元が対応していなくてはなりま せん。 例えば, Im (f') = {1,2}だったとすればf(n+1)=3でなくてはなりません。 それぞれの場合 の数を数えます。 後者は (1) も使います.)