|
%I #14 Jun 02 2014 18:22:17
%S 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,
%T 808,376,156,60,20,8,1,1,2742,1276,532,204,74,23,9,1,1,9458,4402,1840,
%U 712,257,89,26,10,1,1,33062,15390,6448,2507,917,315,105,29,11,1,1,116868
%N Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having exactly k UDU's at low level.
%C T(n,0) = A000958(n-1). - _Emeric Deutsch_, Dec 23 2006
%H Yidong Sun, <a href="http://dx.doi.org/10.1016/j.disc.2004.07.002">The statistic "number of udu's" in Dyck paths</a>, Discrete Math., 287 (2004), 177-186.
%F See Mathematica line.
%F G.f.=zC/(1+z-tz-zC), where C=(1-sqrt(1-4z))/(2z) is the Catalan function. - _Emeric Deutsch_, Dec 23 2006
%F 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
%e Triangle begins:
%e 1
%e 1 1
%e 3 1 1
%e 8 4 1 1
%e 24 11 5 1 1
%e 75 35 14 6 1 1
%e T(4,2)=1 because we have UDUDUUDD.
%p 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
%t 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 *)
%Y Cf. A091869, A092107.
%Y Cf. A000958.
%K nonn,tabl
%O 1,4
%A _N. J. A. Sloane_, Oct 30 2004
|
