■オイラーのトーシェント関数(その29)

 白と黒の真珠,計n個の組み合わせからなるすべて異なるネックレスを何通り作ることができるだろうか? ただし、回転や裏返し,白黒の反転で重なるものは同じものとする。

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

 φ(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

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

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

  Σφ(d)・2^(n/d)/2n

[2]nが奇数のとき,2^(n-1)/2

   nが偶数のとき,2^(n/2-1)+2^(n/2-2)

 [1]+[2]で与えられる.

 ここで,φ(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

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

n=1のとき,[1]=1,[2]=1→2

n=2のとき,[1]=1+1/2,[2]=1+1/2→3

n=3のとき,[1]=4/3+2/3,[2]=2→4

n=4のとき,[1]=16/8+4/8+4/8,[2]=2+1→6

n=5のとき,[1]=32/10+8/10,[2]=4→8

n=6のとき,[1]=64/12+8/12+8/12+4/12,[2]=4+2→13

n=7のとき,[1]=128/14+12/14,[2]=8→18

n=8のとき,[1]=256/16+16/16+8/16+8/16,[2]=8+4→30

n=9のとき,[1]=512/18+2・8/18+6・2/18,[2]=16→46

n=10のとき、[1]=1024/20+32/20+4・4/20+4・2/20,[2]=16+8→78

n=1:2通り

n=2:3通り

n=3:4通り

n=4:6通り

n=5:8通り

n=6:13通り

n=7:18通り

n=8:30通り

n=9:46通り

n=10:78通り

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

回転や裏返し,白黒の反転で重なるものは同じものとする。(裏返しを許すことにする)→正n角形の自己同型からなる二面体群である

巡回群の場合は(裏返しを許さないことにする)

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

  Σφ(d)・2^(n/d)/n

で与えられる。

n=1のとき,[1]=2/1=2

n=2のとき,[1]=4/2+2/2=3

n=3のとき,[1]=8/3+4/3=4

n=4のとき,[1]=16/4+4/4+4/4=6

n=5のとき,[1]=32/5+8/5=8

n=6のとき,[1]=64/6+8/6+8/6+4/6=14

n=7のとき,[1]=128/7+12/7=20

n=8のとき,[1]=256/8+16/8+8/8+8/8=36

n=9のとき,[1]=512/9+2・8/9+6・2/9=60

n=10のとき、[1]=1024/10+32/10+4・4/10+4・2/10=108

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