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

Author

Hartmut F. W. Hoft, Jul 17 2014

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A237270, A237593, A244145.

Programs

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