The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A103293 Number of ways to color n regions arranged in a line such that consecutive regions do not have the same color. 8
 1, 1, 1, 2, 4, 11, 32, 117, 468, 2152, 10743, 58487, 340390, 2110219, 13830235, 95475556, 691543094, 5240285139, 41432986588, 341040317063, 2916376237350, 25862097486758, 237434959191057, 2253358057283035, 22076003468637450, 222979436690612445 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS From David W. Wilson, Mar 10 2005: (Start) 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). 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). 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, 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. 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. (End) Note that A056325 gives the 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. If the two ends of the line are distinguishable, so that 'abcb' and 'abac' are distinct, we get the Bell numbers, A000110(n - 1). 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. - David Callan, Oct 10 2005 LINKS Alois P. Heinz, Table of n, a(n) for n = 0..400 FORMULA a(n) = Sum_{k=0..n-1} (Stirling2(n-1,k) + Ach(n-1,k))/2 for n>0, where Ach(n,k) = [n>1] * (k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)) + [n<2 & n>=0 & n==k]. - Robert A. Russell, May 19 2018 EXAMPLE 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). MAPLE 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..30); # Alois P. Heinz, Sep 05 2008 MATHEMATICA b[n_] := SeriesCoefficient[Exp[(Exp[2*x] - 3)/2 + Exp[x]], {x, 0, n}]*n!; a[n_] := If[n == 0, 1, (BellB[n - 1] + If[Mod[n, 2] == 1, b[(n - 1)/2], Sum[Binomial[n/2 - 1, k] *b[k], {k, 0, n/2 - 1}]])/2]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 17 2016, after Alois P. Heinz *) Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0],    k Ach[n-2, k] + Ach[n-2, k-1] + Ach[n-2, k-2]] (* achiral *) Table[Sum[(StirlingS2[n-1, k] + Ach[n-1, k])/2, {k, 0, n-1}], {n, 1, 30}] (* with a(0) omitted - Robert A. Russell, May 19 2018 *) CROSSREFS Cf. A000110, A056325. Sequence in context: A124504 A056324 A056325 * A123418 A123412 A074408 Adjacent sequences:  A103290 A103291 A103292 * A103294 A103295 A103296 KEYWORD nonn AUTHOR Hugo van der Sanden, Mar 10 2005 EXTENSIONS More terms from David W. Wilson, Mar 10 2005 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 17 23:03 EDT 2021. Contains 343071 sequences. (Running on oeis4.)