|
%I #49 Feb 25 2024 15:53:25
%S 1,1,1,2,4,11,32,117,468,2152,10743,58487,340390,2110219,13830235,
%T 95475556,691543094,5240285139,41432986588,341040317063,2916376237350,
%U 25862097486758,237434959191057,2253358057283035,22076003468637450,222979436690612445
%N Number of ways to color n regions arranged in a line such that consecutive regions do not have the same color.
%C From _David W. Wilson_, Mar 10 2005: (Start)
%C 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 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 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 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 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)
%C 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.
%C 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 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
%H Alois P. Heinz, <a href="/A103293/b103293.txt">Table of n, a(n) for n = 0..400</a>
%H Allan Bickle, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Bickle/bickle5.html">How to Count k-Paths</a>, J. Integer Sequences, 25 (2022) Article 22.5.6.
%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.
%F 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
%e 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 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
%t 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_ *)
%t Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0],
%t k Ach[n-2, k] + Ach[n-2, k-1] + Ach[n-2, k-2]] (* achiral *)
%t Table[Sum[(StirlingS2[n-1, k] + Ach[n-1, k])/2, {k, 0, n-1}], {n, 1, 30}]
%t (* with a(0) omitted - _Robert A. Russell_, May 19 2018 *)
%Y The numbers of unlabeled k-paths for k = 2..7 are given in A005418, A001998, A056323, A056324, A056325, and A345207, respectively (these are also columns of the array in A320750). The sequences counting the unlabeled k-paths converge to this sequence when k goes to infinity.
%Y Cf. A000110, A056325.
%K nonn
%O 0,4
%A _Hugo van der Sanden_, Mar 10 2005
%E More terms from _David W. Wilson_, Mar 10 2005
|
