# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a103293 Showing 1-1 of 1 %I A103293 #61 Oct 15 2024 15:42:50 %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, Table of n, a(n) for n = 0..400 %H A103293 Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6. %H A103293 Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5. %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 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE