A098747 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having exactly k UDU's at low level.

1, 1, 1, 3, 1, 1, 8, 4, 1, 1, 24, 11, 5, 1, 1, 75, 35, 14, 6, 1, 1, 243, 113, 47, 17, 7, 1, 1, 808, 376, 156, 60, 20, 8, 1, 1, 2742, 1276, 532, 204, 74, 23, 9, 1, 1, 9458, 4402, 1840, 712, 257, 89, 26, 10, 1, 1, 33062, 15390, 6448, 2507, 917, 315, 105, 29, 11, 1, 1, 116868

Offset

1,4

Comments

T(n,0) = A000958(n-1). - Emeric Deutsch, Dec 23 2006

Links

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

Yidong Sun, The statistic "number of udu's" in Dyck paths, Discrete Math., 287 (2004), 177-186.

Formula

See Mathematica line.

G.f.=zC/(1+z-tz-zC), where C=(1-sqrt(1-4z))/(2z) is the Catalan function. - Emeric Deutsch, Dec 23 2006

With offset 0 (0<=k<=n), T(n,k)=A065600(n,k)+A065600(n+1,k)-A065600(n,k-1). - Philippe Deléham, Apr 01 2007

Example

Triangle begins:
1
1 1
3 1 1
8 4 1 1
24 11 5 1 1
75 35 14 6 1 1
T(4,2)=1 because we have UDUDUUDD.

Maple

c:=(1-sqrt(1-4*z))/2/z: G:=z*c/(1-t*z+z-z*c): Gser:=simplify(series(G, z=0, 15)): for n from 1 to 13 do P[n]:=sort(coeff(Gser, z, n)) od: for n from 1 to 12 do seq(coeff(P[n], t, k), k=0..n-1) od; # yields sequence in triangular form - Emeric Deutsch, Dec 23 2006

Mathematica

u[n_, k_, i_]:=(2i+1)/(n-k)Binomial[k+i, i]Binomial[2n-2k-2i-2, n-k-1] u[n_, k_]/; k<=n-1 := Sum[u[n, k, i], {i, 0, n-k-1}] Table[u[n, k], {n, 10}, {k, 0, n-1}] (* u[n, k, i] is the number of Dyck n-paths with k low UDUs and k+i+1 returns altogether. For example, with n=4, k=1 and i=1, u[n, k, i] counts UDUUDDUD, UUDDUDUD because each has size n=4, k=1 low UDUs and k+i+1=3 returns to ground level. *) (* David Callan, Nov 03 2005 *)

Crossrefs

Cf. A091869, A092107.

Cf. A000958.

Sequence in context: A143953 A114276 A152879 * A122897 A117425 A287215

Adjacent sequences: A098744 A098745 A098746 * A098748 A098749 A098750

Keyword

nonn,tabl

Author

N. J. A. Sloane, Oct 30 2004

Status

approved