A212363 Number A(n,k) of Dyck n-paths all of whose ascents and descents have lengths equal to 1+k*m (m>=0); square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 5, 1, 1, 1, 1, 2, 14, 1, 1, 1, 1, 1, 4, 42, 1, 1, 1, 1, 1, 2, 8, 132, 1, 1, 1, 1, 1, 1, 4, 17, 429, 1, 1, 1, 1, 1, 1, 2, 7, 37, 1430, 1, 1, 1, 1, 1, 1, 1, 4, 12, 82, 4862, 1, 1, 1, 1, 1, 1, 1, 2, 7, 22, 185, 16796, 1

Offset

0,9

Links

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Formula

G.f. of column k>0 satisfies: A_k(x) = 1+A_k(x)*(x-x^k*(1-A_k(x))), g.f. of column k=0: A_0(x) = 1/(1-x).

A(n,k) = A(n-1,k) + Sum_{j=1..n-k} A(j,k)*A(n-k-j,k) for n,k>0; A(n,0) = A(0,k) = 1.

G.f. of column k > 0: (1 - x + x^k - sqrt((1 - x + x^k)^2 - 4*x^k)) / (2*x^k). - Vaclav Kotesovec, Sep 02 2014

Example

A(3,0) = 1: UDUDUD.
A(3,1) = 5: UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD.
A(4,2) = 4: UDUDUDUD, UDUUUDDD, UUUDDDUD, UUUDUDDD.
A(5,2) = 8: UDUDUDUDUD, UDUDUUUDDD, UDUUUDDDUD, UDUUUDUDDD, UUUDDDUDUD, UUUDUDDDUD, UUUDUDUDDD, UUUUUDDDDD.
A(5,3) = 4: UDUDUDUDUD, UDUUUUDDDD, UUUUDDDDUD, UUUUDUDDDD.
Square array A(n,k) begins:
  1,   1,  1,  1,  1,  1,  1,  1, ...
  1,   1,  1,  1,  1,  1,  1,  1, ...
  1,   2,  1,  1,  1,  1,  1,  1, ...
  1,   5,  2,  1,  1,  1,  1,  1, ...
  1,  14,  4,  2,  1,  1,  1,  1, ...
  1,  42,  8,  4,  2,  1,  1,  1, ...
  1, 132, 17,  7,  4,  2,  1,  1, ...
  1, 429, 37, 12,  7,  4,  2,  1, ...

Maple

A:= proc(n, k) option remember;
      `if`(k=0, 1, `if`(n=0, 1, A(n-1, k)
                   +add(A(j, k)*A(n-k-j, k), j=1..n-k)))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);
# second Maple program:
A:= (n, k)-> `if`(k=0, 1, coeff(series(RootOf(
              A||k=1+A||k*(x-x^k*(1-A||k)), A||k), x, n+1), x, n)):
seq(seq(A(n, d-n), n=0..d), d=0..15);

Mathematica

A[n_, k_] := A[n, k] = If[k == 0, 1, If[n == 0, 1, A[n-1, k] + Sum[A[j, k]*A[n-k-j, k], {j, 1, n-k}]]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Jan 15 2014, translated from first Maple program *)

Crossrefs

Columns k=0-10 give: A000012, A000108, A004148, A023432, A023427, A212364, A212365, A212366, A212367, A212368, A212369.

Sequence in context: A119326 A219866 A333418 * A212382 A274835 A275069

Adjacent sequences: A212360 A212361 A212362 * A212364 A212365 A212366

Keyword

nonn,tabl

Author

Alois P. Heinz, May 10 2012

Status

approved