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

Author

Emeric Deutsch, Mar 31 2007

Keywords

• nonn
• tabf

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

Examples

			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;
		

Links

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

Crossrefs

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

Programs

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

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.