%I A103293
%S A103293 1,1,1,2,4,11,32,117,468,2152,10743,58487,340390,2110219,13830235,95475556,
%T A103293 691543094,5240285139,41432986588,341040317063,2916376237350,
%U A103293 25862097486758,237434959191057,2253358057283035
%N A103293 Number of ways to color n regions arranged in a line such that consecutive 
               regions do not have the same color.
%C A103293 Comments from David W. Wilson, Mar 10 2005: "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).
%C A103293 "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
%C A103293 "The number of colorings of M(n) that are equivalent to their reverse 
               is given by A080107(n). For example, M(4) has A080107(4) = 7 colorings 
               that are equivalent to their reversal: aaaa aabb abab abba abbc abca 
               abcd
%C A103293 "The number of distinct colorings when reversals are counted as equivalent 
               is given by ((A000110(n) + A080107(n))/2, which is essentially the 
               present sequence. M(4) has 11 colorings that are distinct up to reversal: 
               aaaa aaab aaba aabb aabc abab abac abba abbc abca abcd
%C A103293 "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."
%C A103293 Note that A056325 gives number of reversible string structures with n 
               beads using a maximum of six different colors. .. and of course, 
               any limit on the number of colors will be the same as this sequence 
               above up to that number.
%C A103293 If the two ends of the line are distinguishable, so that 'abcb' and 'abac' 
               are distinct, we get the Bell numbers, A000110(n - 1)
%C A103293 Comment from David Callan, Oct 10 2005: With a different offset, number 
               of set partitions of [n] up to reflection (i<->n+1-i). E.g. there 
               are 4 partitions of [3]: 123, 1-23, 13-2, 1-2-3 but not 12-3 because 
               it is the reflection of 1-23.
%e A103293 For n=4, possible arrangements are 'abab', 'abac', 'abca', 'abcd'; we 
               do not include 'abcb' since it is equivalent to 'abac' (if you reverse 
               and renormalize)
%p A103293 with (combinat): b:= n-> coeff (series (exp ((exp(2*x)-3)/2 +exp(x)), 
               x,n+1), x,n)*n!: a:= n-> `if`(n=0, 1, (bell(n-1) + `if`(modp(n,2)=1, 
               b((n-1)/2), add (binomial (n/2-1,k) *b(k), k=0..n/2-1)))/2): seq 
               (a(n), n=0..23); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), 
               Sep 05 2008]
%Y A103293 Cf. A000110, A056325.
%Y A103293 Sequence in context: A124504 A056324 A056325 this_sequence A123418 A123412 
               A074408
%Y A103293 Adjacent sequences: A103290 A103291 A103292 this_sequence A103294 A103295 
               A103296
%K A103293 nonn
%O A103293 0,4
%A A103293 hv(AT)crypt.org (Hugo van der Sanden), Mar 10 2005
%E A103293 More terms from David W. Wilson, Mar 10 2005