A245192 The number of Dyck paths p(m) for m<=n, as defined by the rows of A237593, that have common subpaths of positive length with the Dyck path p(n) for the symmetric representation of sigma(n).

0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 2, 3, 1, 2, 3, 3, 1, 2, 1, 2, 1, 2, 3, 3, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, 2, 3, 1, 2, 3, 2, 3, 4, 1, 2, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, 2, 3, 1, 2, 3, 4, 5, 2, 1, 2, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 1

Offset

1,6

Comments

This sequence counts Dyck paths that have common stretches while sequence A244145 counts adjacent areas of the symmetric representation of sigma(). Their first three differences occur at positions 23, 47 and 53.

A244145 counts adjacent sections rather than common boundaries.

See A237270 for Mathematica function used here.

Links

Table of n, a(n) for n=1..91.

Hartmut F. W. Hoft, Image of overlapping Dyck paths

Example

Path a(6) has two colors since it shares steps 5 and 6 with path a(5) which has a single color.
See also the link for a color image of paths.

Mathematica

(* path[n] computing the n-th Dyck path is defined in A237270 *)
(* coloredPathRange[] assigns the color of the first path sharing a line *)
(* colorLists[] computes the lists of colors in each path in the list *)
defaultPath[n_] := Module[{p=path[n]}, Transpose[{Transpose[{Most[p], Rest[p]}], Table[n, {Length[p]-1}]}]
switchIf[x_, yList_] := Module[{pos=Position[Map[First, yList], First[x]]}, If[pos == {}, x, yList[[First[First[pos]]]]]]
nextColoredPath[p_, n_] := Module[{u=defaultPath[n], meet12, common1}, meet12 = Intersection[Map[First, p], Map[First, u]]; common1=Select[p, MemberQ[meet12, First[#]]&]; Map[switchIf[#, common1]&, u]]
coloredPathRange[n_] := FoldList[nextColoredPath, {{{{0, 0}, {0, 0}}, 0}}, Range[n]]
colorLists[pathList_] := Map[Union[Last[Transpose[#]]]&, pathList]
a[colors_] := Prepend[Map[Last[#] - First[#] + 1&, Rest[colors]], 0]
a[colorLists[coloredPathRange[90]]] (* computes the first 90 values *)

Crossrefs

Cf. A237270, A237593, A244145.

Sequence in context: A161287 A214069 A167969 * A235431 A354599 A303536

Adjacent sequences: A245189 A245190 A245191 * A245193 A245194 A245195

Keyword

nonn

Author

Hartmut F. W. Hoft, Jul 17 2014

Status

approved