■包除原理

(Q)1からnまでの自然数の中で2の倍数でも3の倍数でもない数は何個あるか?

という問題を考えてみよう.

(A)#{2の倍数または3の倍数}=#{2の倍数}+#{3の倍数}−#{2の倍数かつ3の倍数}

2と3の最小公倍数は6であるから,#{2の倍数かつ3の倍数}=#{6の倍数}

これより,

  n−[n/2]−[n/3]+[n/6]

が答えになる.

 ここでは包除原理{A∪B}={A}+{B}−{A∩B}が用いられている.集合の数が多くなるとややこしくなるが,包除原理は一般的には

  {A1∪・・・∪An}=Σ{Ai}−Σ{Ai∩Aj}+Σ{Ai∩Aj∩Ak}−・・・+(−1)^(n-1){A1∩・・・∩An}

と書くことができる.

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

  n−[n/2]−[n/3]+[n/6]

はガウス記号を使っているので一括りにすることはできないが,

  n(1−1/2)(1−1/3)

をみて,オイラー関数φ(n)を想起された方も少なくないだろう.φ(n)はnと互いに素な自然数の個数として定義される.たとえば,

  φ(2)=1,φ(3)=2,φ(4)=2,φ(5)=4,φ(6)=2,・・・

 φ(n)の明示式は

  φ(n)=nΠ(1−1/pi)   piはすべての素因数をわたる

で与えられる.たとえば1176=2^3・3・7^2より

  φ(1176)=1176(1-1/2)(1-1/3)(1-1/7)=336

 包除原理はオイラー関数の明示式を示すためにも用いられる.すなわち,

  φ(n)=n−Σn/pi+Σn/pipj−Σn/pipjpk+・・・+(−1)^mΣn/p1p2・・・pm

===================================