（その１５）はもともとはネックレスの問題である．

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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　φ（ｍ）は，ｍと互いに素であり，ｍより小さい整数ｒ，１≦ｒ＜ｍの個数として定義される．すなわち，φ（ｍ）は１からｍ−１までの整数のうち，ｍと公約数をもたない数はいくつあるかを数えた数を表す．

　ｍ＝９→１，２，４，５，７，８→φ（９）＝６

　ｍ＝１０→１，３，７，９→φ（１０）＝４

　φ（１）＝１，φ（２）＝１，φ（３）＝２，φ（４）＝２

　φ（５）＝４，φ（６）＝２，φ（７）＝６，φ（８）＝４

　φ（９）＝６，φ（１０）＝４，

　φ（ｐ）＝ｐ−１

　φ（ｐ^a）＝（ｐ−１）ｐ^(a-1)＝ｐ^a（１−１／ｐ）

　φ（ｍ）＝ｍΠ（１−１／ｐi）

　φ（１０）＝１０（１−１／２）（１−１／５）＝４

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［１］ｄをｎの約数とする．

　　Σφ（ｄ）・２^(n/d)／２ｎ

［２］ｎが奇数のとき，２^(n-1)/2

　　　ｎが偶数のとき，２^(n/2-1)＋２^(n/2-2)

　［１］＋［２］で与えられる．

　ここで，φ（ｍ）は，ｍと互いに素であり，ｍより小さい整数ｒ，１≦ｒ＜ｍの個数として定義される．すなわち，φ（ｍ）は１からｍ−１までの整数のうち，ｍと公約数をもたない数はいくつあるかを数えた数を表す．

　ｍ＝９→１，２，４，５，７，８→φ（９）＝６

　ｍ＝１０→１，３，７，９→φ（１０）＝４

　φ（１）＝１，φ（２）＝１，φ（３）＝２，φ（４）＝２

　φ（５）＝４，φ（６）＝２，φ（７）＝６，φ（８）＝４

　φ（９）＝６，φ（１０）＝４，

　φ（ｐ）＝ｐ−１

　φ（ｐ^a）＝（ｐ−１）ｐ^(a-1)＝ｐ^a（１−１／ｐ）

　φ（ｍ）＝ｍΠ（１−１／ｐi）

　φ（１０）＝１０（１−１／２）（１−１／５）＝４

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ｎ＝１のとき，［１］＝１，［２］＝１→２

ｎ＝２のとき，［１］＝１＋１／２，［２］＝１＋１／２→３

ｎ＝３のとき，［１］＝４／３＋２／３，［２］＝２→４

ｎ＝４のとき，［１］＝１６／８＋４／８＋４／８，［２］＝２＋１→６

ｎ＝５のとき，［１］＝３２／１０＋８／１０，［２］＝４→８

ｎ＝６のとき，［１］＝６４／１２＋９／１２＋８／１２＋４／１２，［２］＝４＋２→１３

ｎ＝７のとき，［１］＝１２８／１４＋１２／１４，［２］＝８→１８

ｎ＝８のとき，［１］＝２５６／１６＋１６／１６＋８／１６＋８／１６，［２］＝８＋４→３０

ｎ＝１：２通り

ｎ＝２：３通り

ｎ＝３：４通り

ｎ＝４：６通り

ｎ＝５：８通り

ｎ＝６：１３通り

ｎ＝７：１８通り

ｎ＝８：３０通り

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝