(9) 合成写像 2つの写像f:A→B, g:B→Cについて,各元aEAに対
し、Cの元g(f(a))を対応させる写像をfとgの合成写像といい,gofで表す。
(10) 制限写像 写像f:A→Bと部分集合CCAについて, flc:C→ B
をceCに対しflc(c) = f(c) と定め,fのCへの制限写像という。
(11) 有限集合集合 Aが有限集合であるとは,A=0であるか,またはある
正整数nと全単射f:{1,2, , n}→ Aが存在する場合をいう.このとき, nを
Aの元の個数といい, |A|で表す。.なお, 空集合については, |0|=0である。
包除の原理 有限集合 A1, A2,
An について,次の等式が成立する:
n
|41U A2U…UAn|= >A|- 1AnAj||
=1
1<i<j<n
と 1AnAjn A|+…
1<i<j<k<n
+(-1)"=1| A」NA2N……nAn|-
とくに,
|41U A2||=|A1|+|A2|-|A10 A2 |,
|A1U A2 U A3| =|A1|+|A2|+|43||
ー|A10A2|-1A20 As|-|A3n Ai |
+|A」n A2n As|.
例題1(AMC12/2001) 2001 以下の正の整数であって, 3もしくは4の
倍数であるが,5の倍数でないようなものはいくつあるか.
解答 2001 以下の正の整数のうち, 3の倍数は [2001/3」 =D 667 個, 4の倍数
は [2001/4」 =D 500 個ある. 3の倍数でありかつ 4の倍数でもあるものは12の倍