cp's OEIS Frontend

A103293 Number of ways to color n regions arranged in a line such that consecutive regions do not have the same color.

%I A103293 #65 Dec 26 2024 12:34:32
%S A103293 1,1,1,2,4,11,32,117,468,2152,10743,58487,340390,2110219,13830235,
%T A103293 95475556,691543094,5240285139,41432986588,341040317063,2916376237350,
%U A103293 25862097486758,237434959191057,2253358057283035,22076003468637450,222979436690612445
%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 From _David W. Wilson_, Mar 10 2005: (Start)
%C A103293 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. (End)
%C A103293 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 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 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 A103293 Alois P. Heinz, <a href="/A103293/b103293.txt">Table of n, a(n) for n = 0..400</a>
%H A103293 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 A103293 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.
%H A103293 Matthew Bolan, Jose Brox, Mario Carneiro, Martin Dvořák, Andrés Goens, Harald Husum, Zoltan Kocsis, Alex Meiburg, Pietro Monticone, David Renshaw, Jérémy Scanvic, Shreyas Srinivas, Terence Tao, Anand Rao Tadipatri, Vlad Tsyrklevich, Daniel Weber, and Fan Zheng, <a href="https://teorth.github.io/equational_theories/paper.pdf">The equational theories project: using Lean and Github to complete an implication graph in universal algebra</a>, Equational Theories Project 2024. See p. 41.
%F A103293 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 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..30); # _Alois P. Heinz_, Sep 05 2008
%t A103293 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 A103293 Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0],
%t A103293    k Ach[n-2, k] + Ach[n-2, k-1] + Ach[n-2, k-2]] (* achiral *)
%t A103293 Table[Sum[(StirlingS2[n-1, k] + Ach[n-1, k])/2, {k, 0, n-1}], {n, 1, 30}]
%t A103293 (* with a(0) omitted - _Robert A. Russell_, May 19 2018 *)
%o A103293 (Python)
%o A103293 from functools import lru_cache
%o A103293 from sympy.functions.combinatorial.numbers import stirling
%o A103293 def A103293(n):
%o A103293     if n == 0: return 1
%o A103293     @lru_cache(maxsize=None)
%o A103293     def ach(n,k): return (n==k) if n<2 else k*ach(n-2,k)+ach(n-2,k-1)+ach(n-2,k-2)
%o A103293     return sum(stirling(n-1,k,kind=2)+ach(n-1,k)>>1 for k in range(n)) # _Chai Wah Wu_, Oct 15 2024
%Y A103293 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 A103293 Row sums of A284949.
%Y A103293 Cf. A000110, A056325.
%K A103293 nonn
%O A103293 0,4
%A A103293 _Hugo van der Sanden_, Mar 10 2005
%E A103293 More terms from _David W. Wilson_, Mar 10 2005