map-colouring on a line

[Karol PENSON]

       Both of these formulas below ( for a(n) and for a(n+1) ) are correct
        abe are known as Dobinski's relations.
       The formula for  a(n+1) also implies that
         a(n+1) = sum( binomial(n,k)*a(k),k=0..n), which is the 
recurrence rel. for the Bell numbers.

                                 Karol
 


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


-- 
_________________________________________________________________________
Karol A. PENSON
Universite Paris 6              |  Internet : penson at lptl.jussieu.fr.
Lab. Physique Theorique des     |
Liquides                        | http://www.lptl.jussieu.fr/users/penson
Boite courrier 121              |
4, place Jussieu, Tour 24, Et.4 |      Tel : (33 1) 44 27 72 33
75252 Paris Cedex 05, France    |      Fax : (33 1) 44 27 51 00