A128727 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n having k DDU and LDU's.

1, 1, 3, 9, 1, 27, 9, 81, 54, 2, 243, 270, 30, 729, 1215, 270, 5, 2187, 5103, 1890, 105, 6561, 20412, 11340, 1260, 14, 19683, 78732, 61236, 11340, 378, 59049, 295245, 306180, 85050, 5670, 42, 177147, 1082565, 1443420, 561330, 62370, 1386, 531441

Offset

0,3

Comments

A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of a path is defined to be the number of steps in it.

Row n has ceiling(n/2) terms (n >= 1).

Row sums yield A002212.

Apparently a(n) = A126177(n-1). - Georg Fischer, Oct 28 2018

Links

Table of n, a(n) for n=0..43.

E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203

Formula

T(n,0) = 3^(n-1).

T(2k+1,k) = binomial(2k,k)/(k+1) (the Catalan numbers, A000108).

T(2k,k-1) = 3binomial(2k-1,k) = A003409(k).

Sum_{k>=0} k*T(n,k) = A026377(n-1).

T(n,k) = (1/n)*3^(n-1-2k)*binomial(n,k)*binomial(n-k,k+1).

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

Example

T(5,2)=2 because we have UU(DDU)U(DDU)D and UUU(DDU)(DDU)D (the 2 subwords are shown between parentheses).
Triangle starts:
    1;
    1;
    3;
    9,    1;
   27,    9;
   81,   54,    2;
  243,  270,   30;
  729, 1215,  270,    5;

Maple

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

Crossrefs

Cf. A000108, A002212, A003409, A026377, A126177.

Sequence in context: A080322 A126179 A304249 * A126177 A158483 A128733

Adjacent sequences: A128724 A128725 A128726 * A128728 A128729 A128730

Keyword

nonn,tabf

Author

Emeric Deutsch, Mar 31 2007

Status

approved