A121463 Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n, having k distinct valley levels (n>=1, k>=0).

1, 1, 1, 1, 4, 1, 11, 1, 1, 26, 7, 1, 57, 30, 1, 1, 120, 102, 10, 1, 247, 303, 58, 1, 1, 502, 825, 256, 13, 1, 1013, 2116, 955, 95, 1, 1, 2036, 5200, 3178, 515, 16, 1, 4083, 12381, 9740, 2310, 141, 1, 1, 8178, 28779, 28064, 9078, 906, 19, 1, 16369, 65658, 77093

Offset

1,5

Comments

Row n has 1+floor(n/2) terms.

Row sums are the odd-subscripted Fibonacci numbers (A001519).

Links

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

E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.

Emeric Deutsch and Helmut Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.

Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, J. Int. Seq. (2025) Vol. 28, Art. No. 25.1.6. See p. 19.

Formula

T(n,k) = Sum(binomial(n,2*k+j)*binomial(k-1+j,k-1),j=0..n-2*k) (k<=n/2).

T(n,0) = 1; T(n,1) = 2^n-n-1 = A000295(n) (the Eulerian numbers).

T(2n+1,n) = 3n+1 = A016777(n). T(2n,n) = 1.

G.f.: G(t,z)=(1-2z)/(1-3z+2z^2-tz^2)-1.

Example

T(5,2)=7 because we have UDUDUUDUDD, UDUUDUDUDD, UDUUDUUDDD, UDUUUDDUDD, UUDDUUDUDD with valleys at levels 0 and 2, UDUUUDUDDD with valleys at levels 0 and 2 and UUDUUDUDDD with valleys at levels 1 and 2.
Triangle starts:
  1;
  1,1;
  1,4;
  1,11,1;
  1,26,7;
  1,57,30,1;

Maple

T:=(n, k)->sum(binomial(n, 2*k+j)*binomial(k-1+j, k-1), j=0..n-2*k): for n from 1 to 16 do seq(T(n, k), k=0..floor(n/2)) od; # yields sequence in triangular form

Crossrefs

Cf. A001519, A000295, A016777.

Sequence in context: A296419 A301390 A283433 * A244608 A115022 A230534

Adjacent sequences: A121460 A121461 A121462 * A121464 A121465 A121466

Keyword

nonn,tabf

Author

Emeric Deutsch, Jul 31 2006

Status

approved