Number of $n$-bead binary necklaces [OEIS-A000013] I tried to obtain the number of $n$-bead binary necklaces from my program written in C++. Then, one formula came up when I looked up the number to see if my thought is correct.

Number of $n$-bead binary necklaces with beads of $2$ colors where the colors may be swapped but turning over is not allowed
$$a(n)=\sum_{d|n}\frac{\phi(2d) \, 2^\frac{n}{d}}{2n}$$ for $n>0$.

Source: A000013
However, although I see the number I obtained from my program was correct, I could not grasp why the formula holds.
Thus, I would appreciate it if someone could explain its derivation to me.
 A: As was suggested in a comment, the Burnside's lemma is possibly the simplest way to deal with similar problems, since you are in fact looking for the number of orbits of an action of $\Pi_n\times\Sigma_2$ on $A_n=\{0,1\}^n$, with $\pi$ and $\sigma$ being rotation and inversion operators:
$$
(\pi a)_k=a_{(k+1)\bmod n},\quad (\sigma a)_k=1-a_k,\quad  k=0\dots n. 
$$
There are altogether $2n$ elements in this action group with general form $\pi^i\sigma^j$ ($i=0\dots n-1;\ j=0,1)$, the element $\pi^0\sigma^0$ being the identity. It remains to find the number of the elements of $A_n$ fixed by each of the $2n$ operations.
The elements fixed by the rotation $\pi^j$ are well known. One can imagine that a necklace is a train consisting of $n/(n,j)$ identical railcars with length $(n,j)$. Clearly the necklace coincides with itself by any rotation $\pi^{k(n,j)}$, particularly by $\pi^j$ and $\pi^n=\pi^0$. As the content of a railcar can be arbitrary the number of fixed elements is $2^{(n,j)}$ for binary necklaces. If the number of railcars $n/(n,j)$ is odd this is the end of story as $\sigma$ cannot come in the game. This changes however if the number is even. In this case the number of fixed elements is doubled since the trains consisting both of identical as well as of alternating "inverted" cars are the fixed elements. It is important to observe that the number $j/(n,j)$ (the number of cars staying between $0$ and $j$) is  always odd in the considered case.
Thus we have by Burnside's lemma for the number of orbits $N$:
$$\begin{align}
N(n)&=\frac1{2n}\left[\sum_{1\le i\le n}^{n/(n,i)=0\bmod 2}2^{(n,i)+1}
+\sum_{1\le i\le n}^{n/(n,i)=1\bmod 2}2^{(n,i)}\right]\\
&=\frac1{2n}\sum_{k|n}\left[\sum_{1\le i\le n}^{(n,i)=k \atop n/k=0\bmod 2}2^{k+1}
+\sum_{1\le i\le n}^{(n,i)=k \atop n/k=1\bmod 2}2^{k}\right]\\
&=\frac1{2n}\left[\sum_{k|n}^{n/k=0\bmod 2}2^{k+1}\sum_{1\le i\le n}^{(n,i)=k}1
+\sum_{k|n}^{n/k=1\bmod 2}2^{k}\sum_{1\le i\le n}^{(n,i)=k}1\right]\\
&=\frac1{2n}\left[\sum_{k|n}^{n/k=0\bmod 2}2^{k+1}\phi(n/k)
+\sum_{k|n}^{n/k=1\bmod 2}2^{k}\phi(n/k)\right]\\
&=\frac1{2n}\left[\sum_{d|n}^{d=0\bmod 2} 2^{n/d}\cdot2\phi(d)
+\sum_{d|n}^{d=1\bmod 2}2^{n/d}\cdot\phi(d)\right]\\
&=\frac1{2n}\sum_{d|n} 2^{n/d}\phi(2d),
\end{align}
$$
where the last equality follows from already mentioned in comments property:
$$
\phi(2d)=\begin{cases}
2\phi(d),& d=0\bmod 2\\
\phi(d),& d=1\bmod 2\\
\end{cases}.
$$
