3
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ Hint: each such sequence has a period, the minimum number of cyclic shifts required to get back to the original sequence. This period divides $N$. Try counting the number of sequences of a given period and summing over the divisors of $N$. It will probably be helpful to assume $N$ is prime or a prime power to start out. $\endgroup$ – Vik78 Jan 15 '17 at 15:52
  • 3
    $\begingroup$ These are the famous $k$-ary necklaces of length N. See en.wikipedia.org/wiki/Necklace_%28combinatorics%29 $\endgroup$ – MathChat Jan 15 '17 at 15:59
  • $\begingroup$ More on necklaces at MSE meta. $\endgroup$ – Marko Riedel Jan 15 '17 at 22:29
1
$\begingroup$

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)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.