MathDB

Let

n \ge 2

be an integer. There are

n

beads numbered

1, 2, \ldots, n

. Two necklaces made out of some of these beads are considered the same if we can get one by rotating the other (with no flipping allowed). For example, with

n \ge 5

, the necklace with four beads

1, 5, 3, 2

in the clockwise order is same as the one with

5, 3, 2, 1

in the clockwise order, but is different from the one with

1, 2, 3, 5

in the clockwise order.
We denote by

D_0(n)

(respectively

D_1(n)

) the number of ways in which we can use all the beads to make an even number (resp. an odd number) of necklaces each of length at least

3

. Prove that

n - 1

divides

D_1(n) - D_0(n)

Problem Statement