map-colouring on a line

[hv at crypt.org]

hv at crypt.org wrote:
:Consider two strings the same if the letters of one can be remapped to
:the other, so that (eg) 'abbac' is the same as 'deeds'.
[...]
:If the ends are indistinguishable, we get the sequence:
:  1, 1, 1, 2, 4, 11, 32, 117, 468, 2152, 10743, 58487, 340390, 2110219, ...
:(if my code is correct) which is not in the OEIS.
:
:%I A000001
:%S A000001 1 1 1 2 4 11 32 117 468 2152 10743 58487 340390 2110219
:%N A000001 Number of ways to colour n regions arranged in a line such that consecutive regions do not have the same colour
:%e A000001 For n=4, possible arrangements are 'abab', 'abac', 'abca', 'abcd'; we don't include 'abcb' since it is equivalent to 'abac' (if you reverse and renormalize)
:%C A000001 If the two ends of the line are distinguishable, so that 'abcb' and 'abac' are distinct, we get the Bell numbers, A000110(n - 1)
:%Y A000001 Cf. A000110
:%K A000001 nonn,more
:%O A000001 0,4
:%A A000001 hv at crypt.org (Hugo van der Sanden)

Now that's interesting, I just went back to check whether this had been
added, and put in few enough terms to find A056325:
  Number of reversible string structures with n beads using a maximum of
  six different colors.
.. and of course, any limit on the number of colours will be the same
as the sequence above up to that number.

Neil, do you want versions of the sequence constrained to other numbers
of colours?

Hugo