0,4

FromDavid 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 byA000110(n).

For example, M(4) hasA000110(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 byA080107(n). For example, M(4) hasA080107(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 thatA056325gives 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

Alois P. Heinz,Table of n, a(n) for n = 0..400

Allan Bickle,How to Count k-Paths,J. Integer Sequences, 25 (2022) Article 22.5.6.

Allan Bickle,A Survey of Maximal k-degenerate Graphs and k-Trees,Theory and Applications of Graphs 0 1 (2024) Article 5.

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

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).

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

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, afterAlois 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 *)

(Python)

from functools import lru_cache

from sympy.functions.combinatorial.numbers import stirling

defA103293(n):

if n == 0: return 1

@lru_cache(maxsize=None)

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)

return sum(stirling(n-1, k, kind=2)+ach(n-1, k)>>1 for k in range(n)) #Chai Wah Wu,Oct 15 2024

The numbers of unlabeled k-paths for k = 2..7 are given inA005418,A001998,A056323,A056324,A056325,andA345207,respectively (these are also columns of the array inA320750). The sequences counting the unlabeled k-paths converge to this sequence when k goes to infinity.

Row sums ofA284949.

Cf.A000110,A056325.

Sequence in context:A056324A056325A345207*A123418A123412A074408

Adjacent sequences:A103290A103291A103292*A103294A103295A103296

Hugo van der Sanden,Mar 10 2005

More terms fromDavid W. Wilson,Mar 10 2005

approved