Number of sequences from numbers $\{1, 2, ..., k\}$ How many sequences of $n$ numbers are there such that each number is from a set $\{1, 2, ..., k\}$ (repetitions of numbers are allowed) with restriction that two sequences are considered the same if one can be obtained from the other by doing cyclic shift (for example sequence $2, 1, 3, 4$ is a cyclic shift of $1, 3, 4, 2$).
 A: You can find the analysis of the general situation at MathChat's suggested link on k-ary necklaces.
For your example case of $(n,k)=(4,2)$, we can break the analysis down as follows:


*

*there are $k^n = 2^4=16$ "raw" strings generated

*$k=2$ of these strings will be single-valued $\big[$ $(1, 1, 1, 1)$, $(2, 2, 2, 2)$ $\big]$

*for strings with a pattern repeat of length $2$, consider length $m=2$ and thus $m^k-k$ $= 2^2-2$ $=2$ such strings will be present, contributing $\frac 2m=\frac 22=1$ string to the total  $\big[$ $(2, 1, 2, 1)$ $\big]$

*the remaining $16-2-2=12$ will have no pattern repeat (= pattern length of $4$) contributing  $\frac {12}4=3$ strings to the total $\big[$ $(2, 1, 1, 1)$, $(2, 2, 1, 1)$, $(2, 2, 2, 1)$ $\big]$

*giving $2+1+3 = 6$ distinct necklaces as you found


The analysis becomes more complicated, the more factors that $n$ has (and hence the more potential for short repeated patterns). For the case where $n=p$ prime, the number is simply $p+\frac {k^{\,\large{p}}-p}p$ - the single-colour strings plus the length-$p$ "patterns" after cyclic reduction.

Note that the "example case" I refer to was removed from the question, but read as follows:

If $n = 4$ and $k = 2$ the answer is $6$ and the sequences are $(1, 1, 1, 1)$; $(2, 1, 1, 1)$; $(2, 2, 1, 1)$; $(2, 1, 2, 1)$; $(2, 2, 2, 1)$; $(2, 2, 2, 2)$

