login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A128718 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k UU's (doublerises) (n >= 1; 0 <= k <= n-1). 2
1, 1, 2, 1, 5, 4, 1, 9, 18, 8, 1, 14, 50, 56, 16, 1, 20, 110, 220, 160, 32, 1, 27, 210, 645, 840, 432, 64, 1, 35, 364, 1575, 3150, 2912, 1120, 128, 1, 44, 588, 3388, 9534, 13552, 9408, 2816, 256, 1, 54, 900, 6636, 24822, 49644, 53088, 28800, 6912, 512, 1, 65, 1320, 12090, 57750, 153426, 231000, 193440, 84480, 16640, 1024 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,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 its steps.

Row sums yield A002212.

LINKS

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

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

FORMULA

T(n,0) = 1;

T(n,1) = (n-1)(n+2)/2 = A000096(n-1);

T(n,k) = A126182(n,n-k), i.e., triangle is mirror image of A126182.

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

T(n,k) = (binomial(n,k)/n)*Sum_{j=0..k} binomial(k,j)*binomial(n-k+j, j+1) (1 <= k <= n).

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

EXAMPLE

T(3,2)=4 because we have UUUDDD, UUUDLD, UUUDDL and UUUDLL.

Triangle starts:

  1;

  1,  2;

  1,  5,  4;

  1,  9, 18,  8;

  1, 14, 50, 56, 16;

MAPLE

T:=proc(n, k) if k=0 then 1 else binomial(n, k)*sum(binomial(k, j)*binomial(n-k+j, j+1), j=0..k)/n fi end: for n from 1 to 11 do seq(T(n, k), k=0..n-1) od; # yields sequence in triangular form

MATHEMATICA

m = 12; G[_] = 0;

Do[G[z_] = 1 + t z G[z]^2 + z G[z] - t z + O[z]^m, {m}];

CoefficientList[#, t]& /@ CoefficientList[G[z], z] // Rest // Flatten (* Jean-Fran├žois Alcover, Nov 15 2019 *)

CROSSREFS

Cf. A000096, A002212, A126182, A128743.

Sequence in context: A194682 A274105 A056242 * A112358 A126351 A157011

Adjacent sequences:  A128715 A128716 A128717 * A128719 A128720 A128721

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Mar 30 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 30 18:38 EDT 2020. Contains 334728 sequences. (Running on oeis4.)