Let $ T(r,n)$ be the number of cyclic sequences of length $n$ on the alphabet $\{1,\ldots,r\}$.Show that
$$2^{2^n-n-1} < T(2,2^n) \leq 2^{2^n-n+1} $$
I cannot prove the right hand side bound. In particular here is what I thougth:
$$T(2,2^n) = \frac{1}{2^n} \sum_{d\mid 2^n} \phi(\frac{2^n}{d}) 2^d = \frac{1}{2^n} (\phi(2^n)2+\phi(2^{n-1})2^2+\phi(2^{n-2})2^{2^2}+\ldots) = \frac{1}{2^n} \sum_{k=0}^n \phi(2^{n-k})2^{2^k}= \frac{1}{2^n} \sum_{k=0}^{n}2^{n-k}2^{n-k-1}2^{2^k} = 2^n\sum_{k=0}^n 2^{2^k-2k-1}$$ Where $\phi$ is the Euler totient function. Now i can obtain easily the left hand side one by considering just the last element of the sum but i cannot prove the $\leq$ part.