[State networks for] shift rules
The pictures below show networks obtained with rule 170, which just shifts every configuration one position to the left at each step. With any such shift rule, all states lie on cycles, and the lengths of these cycles are the divisors of the size n. Every cycle corresponds in effect to a distinct necklace with n beads; with k colors the total number of these is
Apply[Plus, (EulerPhi[n/#] k# &)[Divisors[n]]]/n
The number of cycles of length exactly m is s[m, k]/m, where s[m, k] is defined on page 950. For prime k, each cycle (except all 0's) corresponds to a term in the product Factor[xkn - 1 - 1, Modulus k]. (See page 975.)