■トーシェント関数と非トーション(その38)

 φ(m)は,mと互いに素であり,mより小さい整数r,1≦r<mの個数として定義される.すなわち,φ(m)は1からm−1までの整数のうち,mと公約数をもたない数はいくつあるかを数えた数を表す.

 m=9→1,2,4,5,7,8→φ(9)=6

 m=10→1,3,7,9→φ(10)=4

 φ(1)=1,φ(2)=1,φ(3)=2,φ(4)=2

 φ(5)=4,φ(6)=2,φ(7)=6,φ(8)=4

 φ(9)=6,φ(10)=4,

 φ(p)=p−1

 φ(p^a)=(p−1)p^(a-1)=p^a(1−1/p)

 φ(m)=mΠ(1−1/pi)

 φ(10)=10(1−1/2)(1−1/5)=4

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

巡回群で、白がk個、黒がn-k個含まれている長さnのネックレスの個数は?

kとnが互いに素ならば

1/n・(n、k)に等しくなる。

そうでないとき、

[2]dをnの約数とする.

  Σφ(d)・(n/d、k/d)/n

で与えられる。

n=12,k=12の場合、

d=1→φ(1)・(12、12)=1

d=2→φ(2)・(6、6)=1

d=3→φ(3)・(4、4)=2

d=4→φ(4)・(3、3)=2

d=6→φ(6)・(2、2)=2

d=12→φ(12)・(1、1)=4

12/12=1通りのネックレスが存在する?

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

n=12

k=1の場合・・・1通り・・・K=11の場合

k=2の場合・・・6通り・・・K=10の場合

k=3の場合・・・19通り・・・K=9の場合

k=4の場合・・・43通り・・・K=8の場合

k=5の場合・・・66通り・・・K=7の場合

k=6の場合・・・80通り

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