|
%I #16 Nov 15 2019 21:33:58
%S 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,
%T 840,432,64,1,35,364,1575,3150,2912,1120,128,1,44,588,3388,9534,13552,
%U 9408,2816,256,1,54,900,6636,24822,49644,53088,28800,6912,512,1,65,1320,12090,57750,153426,231000,193440,84480,16640,1024
%N 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).
%C 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.
%C Row sums yield A002212.
%H E. Deutsch, E. Munarini, S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.jspi.2010.01.015">Skew Dyck paths</a>, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.
%F T(n,0) = 1;
%F T(n,1) = (n-1)(n+2)/2 = A000096(n-1);
%F T(n,k) = A126182(n,n-k), i.e., triangle is mirror image of A126182.
%F Sum_{k=0..n-1} k*T(n,k) = A128743(n).
%F T(n,k) = (binomial(n,k)/n)*Sum_{j=0..k} binomial(k,j)*binomial(n-k+j, j+1) (1 <= k <= n).
%F G.f.: G - 1, where G = G(t,z) satisfies G = 1 + tzG^2 + zG - tz.
%e T(3,2)=4 because we have UUUDDD, UUUDLD, UUUDDL and UUUDLL.
%e Triangle starts:
%e 1;
%e 1, 2;
%e 1, 5, 4;
%e 1, 9, 18, 8;
%e 1, 14, 50, 56, 16;
%p 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
%t m = 12; G[_] = 0;
%t Do[G[z_] = 1 + t z G[z]^2 + z G[z] - t z + O[z]^m, {m}];
%t CoefficientList[#, t]& /@ CoefficientList[G[z], z] // Rest // Flatten (* _Jean-François Alcover_, Nov 15 2019 *)
%Y Cf. A000096, A002212, A126182, A128743.
%K nonn,tabl
%O 1,3
%A _Emeric Deutsch_, Mar 30 2007
|
