map-colouring on a line

[hv at crypt.org]

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'.

Then the number of distinct strings of length n is A000110(n):
  Name:  Bell or exponential numbers: ways of placing n labeled balls into n
         indistinguishable boxes.

In A000110 among the many formulae I notice a near-duplication:
           a(n) = EXP(-1)*sum(k=>0,k^n/k!) - Benoit Cloitre
              (abcloitre(AT)wanadoo.fr), May 19 2002
and:
           a(n+1) = exp(-1)*sum(k=>0,(k+1)^(n)/k!) - Gerald McGarvey
              (Gerald.McGarvey(AT)comcast.net), Jun 03 2004
.. and I'm guessing only one of those is correct.

I was looking at this because I was considering a simplified version of 
the map-colouring problem, looking at a line of n regions each connected 
only to its immediate neightbours, and with an infinite number of colours. 
If the two ends of the line can be distinguished (so that we do not throw 
out symmetric pairs), we have a(n) = A000110(n - 1).

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.

Perl code is below, and took about 10 minutes to calculate up to a(13).
I'd like to find a more efficient way to extend the sequence.

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

It would also be useful to add a reference to this sequence on A000110.
Should these be called the 'Baby Bell' numbers, or would that be just
too cheesy? :)

Hugo
---
#!/usr/bin/perl -w
use strict;

# $| = 1;
for (my $n = 0; 1; ++$n) {
    my $count = 0;
    my $s = 'a' x $n;
    while (1) {
# print(reverse($s).' '),
        ++$count unless $s =~ /(.)\1/ || $s gt normalise(scalar reverse($s));
        $s =~ s{(.*)(.)(?=\2)}{('a' x length($1)) . chr(1+ord($2))}e
        or $s =~ s{(.*?)(.)(?=.*\2)}{('a' x length($1)) . chr(1+ord($2))}e
        or last;
    }
# print "\n";
    print "a($n) = $count\n";
}

sub normalise {
    my $str = shift;
    my $dest = 'a';
    my %map;
    $map{$_} ||= $dest++ for reverse split //, $str;
    $str =~ s/(.)/$map{$1}/ge;
    $str;
}