map-colouring on a line

[David Wilson]

Let M(n) be a map of n regions in a row.  The number of ways
to color M(n) if same-color regions are allowed to touch is given
by A000110(n):

%S A000110 1,1,2,5,15,52,203,877,4140,21147,115975,678570,4213597,27644437,
%T A000110 190899322,1382958545,10480142147,82864869804,682076806159,
%U A000110 5832742205057,51724158235372,474869816156751,4506715738447323

For example, M(4) has A000110(4) = 15 such colorings:

aaaa aaab aaba aabb aabc
abaa abab abac abba abbb
abbc abca abcb abcc abcd

The number of colorings of M(n) that are equivalent to their reverse
is given by A080107(n):

%S A080107 
1,1,2,3,7,12,31,59,164,339,999,2210,6841,16033,51790,127643,428131,
%T A080107 1103372,3827967,10269643,36738144,102225363,376118747,1082190554,
%U A080107 4086419601,12126858113,46910207114,143268057587,566845074703

For example, M(4) has A080107(4) = 7 colorings that are equivalent
to their reversal:

aaaa aabb abab abba abbc
abca abcd

The number of distinct colorings when reversals are counted as
equivalent is given by ((A000110(n) + A080107(n))/2:

1,1,2,4,11,32,117,468,2152,10743,58487,340390,2110219,13830235,95475556,
691543094,5240285139,41432986588,341040317063,2916376237350,
25862097486758,237434959191057,2253358057283035

These are essentially your Baby Bells.  Thus M(4) has 11 colorings that
are distinct up to reversal:

aaaa aaab aaba aabb aabc
abab abac abba abbc abca
abcd

We can redo the whole analysis, this time forbidding same-color
regions to touch.  When we do, we get the same sequences, each
with an extra 1 at the beginning.


----- Original Message ----- 
From: <hv at crypt.org>
To: <ham>; <seqfan at ext.jussieu.fr>
Sent: Thursday, March 10, 2005 7:43 AM
Subject: map-colouring on a line


> 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? :)