login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A193536 Triangle T(n,k), n>=0, 0<=k<=C(n,2), read by rows: T(n,k) = number of k-length saturated chains in the poset of Dyck paths of semilength n ordered by inclusion. 3
1, 1, 2, 1, 5, 5, 4, 2, 14, 21, 30, 38, 40, 32, 16, 42, 84, 168, 322, 578, 952, 1408, 1808, 1920, 1536, 768, 132, 330, 840, 2112, 5168, 12172, 27352, 58126, 115636, 212762, 356352, 532224, 687104, 732160, 585728, 292864, 429, 1287, 3960 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

Alois P. Heinz, Rows n = 0..13, flattened

J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion

EXAMPLE

Poset of Dyck paths of semilength n=3:

.

.      A       A:/\      B:

.      |        /  \      /\/\

.      B       /    \    /    \

.     / \

.    C   D     C:        D:        E:

.     \ /         /\      /\

.      E       /\/  \    /  \/\    /\/\/\

.

Saturated chains of length k=0: A, B, C, D, E (5); k=1: A-B, B-C, B-D, C-E, D-E (5); k=2: A-B-C, A-B-D, B-C-E, B-D-E (4), k=3: A-B-C-E, A-B-D-E (2) => [5,5,4,2].

Triangle begins:

    1;

    1;

    2,   1;

    5,   5,   4,    2;

   14,  21,  30,   38,   40,    32,    16;

   42,  84, 168,  322,  578,   952,  1408,  1808,   1920,   1536,    768;

  132, 330, 840, 2112, 5168, 12172, 27352, 58126, 115636, 212762, 356352, ...

MAPLE

d:= proc(x, y, l) option remember;

      `if`(x<=1, [[y, l[]]], [seq(d(x-1, i, [y, l[]])[], i=x-1..y)])

    end:

T:= proc(n) option remember; local g, r, j;

      g:= proc(l) option remember; local r, i;

            r:= [1];

            for i to n-1 do if l[i]>i and (i=1 or l[i-1]<l[i]) then

              r:= zip((x, y)->x+y, r, [0, g(subsop(i=l[i]-1, l))[]], 0)

            fi od; r

          end;

      r:= [];

      for j in d(n, n, []) do

        r:= zip((x, y)->x+y, r, g(j), 0)

      od; r[]

    end:

seq(T(n), n=0..7);

MATHEMATICA

zip = With[{m = Max[Length[#1], Length[#2]]}, PadRight[#1, m] + PadRight[#2, m]]&; d[x_, y_, l_] := d[x, y, l] = If[x <= 1, {Prepend[l, y]}, Flatten[t = Table [d[x-1, i, Prepend[l, y]], {i, x-1, y}], 1]];

T[n_] := T[n] = Module[{g, r0}, g[l_] := g[l] = Module[{r, i}, r = {1}; For[i = 1, i <= n-1 , i++, If [l[[i]]>i && (i == 1 || l[[i-1]] < l[[i]]), r = zip[r, Join[{0}, g[ReplacePart[l, i -> l[[i]]-1]]]]]]; r]; r0 = {}; Do[r0 = zip[r0, g[j]], {j, d[n, n, {}]}]; r0]; Table[T[n], {n, 0, 7}] // Flatten (* Jean-Fran├žois Alcover, Feb 13 2017, translated from Maple *)

CROSSREFS

Row sums give: A166860. Columns k=0,1 give: A000108, A002054(n-1). Last elements of rows give: A005118.  Row lengths give: A000124(n-1).

Sequence in context: A058118 A124226 A248797 * A152290 A248699 A032006

Adjacent sequences:  A193533 A193534 A193535 * A193537 A193538 A193539

KEYWORD

nonn,tabf

AUTHOR

Alois P. Heinz, Jul 29 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 20 05:25 EDT 2019. Contains 326139 sequences. (Running on oeis4.)