A125644 Table with T(n,k) = the number of Dyck paths whose ascent lengths, in order, are the k-th composition of n, for the standard composition order.

1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 3, 1, 2, 1, 1, 1, 4, 3, 6, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1, 1, 5, 4, 10, 3, 9, 6, 10, 2, 7, 5, 9, 3, 7, 4, 5, 1, 4, 3, 6, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1, 1, 6, 5, 15, 4, 14, 10, 20, 3, 12, 9, 19, 6, 16, 10, 15, 2, 9, 7, 16, 5, 14, 9, 14, 3, 10, 7, 12, 4, 9, 5, 6, 1, 5

Offset

0,6

Comments

The standard composition order is specified in A066099. Also, the number of ordered, rooted trees for which the out-degrees of the non-leaf nodes, in preorder, form the specified composition.

Links

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

Jon Maiga, Computer-generated formulas for A125644, Sequence Machine.

Formula

For a composition [b_1,...,b_m], we have a([b_1]) = 1, a([b_1,b_2,...,b_m]) = Sum_{i=0}^{b_1-1} a([b_2+i,b_3,...,b_m]).

Conjecture: a(n) = A347205(A035327(n)) for n >= 0 (noticed by Sequence Machine). - Mikhail Kurkov, Dec 15 2021 [verification needed]

Example

Composition number 11 is 2,1,1; there are 3 Dyck paths with this pattern: UUDDUDUD, UUDUDDUD and UUDUDUDD, so a(11) = 3. The corresponding trees are:
      O         O
      |         |
      O  O   O  O
      |  |   |  |
  O   O  O   O  O   O
   \ /    \ /    \ /
    O      O      O
The table starts:
  1;
  1;
  1,1;
  1,2,1,1;
  1,3,2,3,1,2,1,1;
  1,4,3,6,2,5,3,4,1,3,2,3,1,2,1,1;
  ...

Maple

a:= proc(l) option remember; `if`(nops(l)<=1, 1,
      add(a(subsop(1=NULL, 2=l[2]+i, l)), i=0..l[1]-1))
    end:
b:= proc(n, l) option remember; `if`(n=0, [a(l)],
      [seq(b(n-i, [i, l[]])[], i=1..n)])
    end:
T:= n-> b(n, [])[]:
seq(T(n), n=0..8);  # Alois P. Heinz, May 25 2013

Mathematica

a[l_] := a[l] = If[Length[l] <= 1, 1, Sum[a[ReplacePart[l,
     {1 -> Nothing, 2 -> l[[2]]+i}]], {i, 0, l[[1]]-1}]];
b[n_, l_] := b[n, l] = If[n == 0, {a[l]},
     Flatten @ Table[b[n - i, Join[{i}, l]], {i, 1, n}]];
T[n_] := b[n, {}];
T /@ Range[0, 8] // Flatten (* Jean-François Alcover, Feb 14 2021, after Alois P. Heinz *)

Crossrefs

Cf. A125181, A011782 (row lengths), A000108 (row sums), A066099.

Sequence in context: A134431 A211098 A070879 * A048821 A120221 A300655

Adjacent sequences: A125641 A125642 A125643 * A125645 A125646 A125647

Keyword

nonn,look,tabf,changed

Author

Franklin T. Adams-Watters, Nov 29 2006

Status

approved