cp's OEIS Frontend

A090981 Triangle read by rows: T(n,k) = number of Schroeder paths of length 2n and having k ascents.

%I A090981 #39 Aug 25 2024 20:24:10
%S A090981 1,1,1,1,4,1,1,11,9,1,1,26,46,16,1,1,57,180,130,25,1,1,120,603,750,
%T A090981 295,36,1,1,247,1827,3507,2345,581,49,1,1,502,5164,14224,14518,6076,
%U A090981 1036,64,1,1,1013,13878,52068,75558,48006,13776,1716,81,1,1,2036,35905,176430
%N A090981 Triangle read by rows: T(n,k) = number of Schroeder paths of length 2n and having k ascents.
%C A090981 A Schroeder path is a lattice path in the first quadrant, from the origin to a point on the x-axis and consisting of steps U=(1,1), D=(1,-1) and H=(2,0) of length 2n and having k ascents (i.e., maximal strings of (1,1) steps).
%C A090981 Row sums give A006318 (the large Schroeder numbers). Column 1 gives A000295 (the Eulerian numbers).
%C A090981 Another version of the triangle T(n,k), 0<=k<=n, read by rows; given by [1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, ...] DELTA [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] = 1; 1, 0; 1, 1, 0; 1, 4, 1, 0; 1, 11, 9, 1, 0; ..., where DELTA is the operator defined in A084938. - _Philippe Deléham_, Jun 14 2004
%C A090981 The expected number of ascents in a Schroeder n-path is asymptotically (sqrt(2)-1)*n for large n. (Previously formulated as conjecture by _David Callan_, Jul 25 2008, now proven.) - _Valerie Roitner_, Aug 06 2020
%H A090981 G. C. Greubel, <a href="/A090981/b090981.txt">Rows n=0..100 of triangle, flattened</a>
%H A090981 L. Ferrari, E. Munarini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Ferrari/ferrari.html">Enumeration of Edges in Some Lattices of Paths</a>, J. Int. Seq. 17 (2014) #14.1.5.
%H A090981 Zhicong Lin, Dongsu Kim, <a href="https://arxiv.org/abs/1612.02964">A sextuple equidistribution arising in Pattern Avoidance</a>, arXiv:1612.02964 [math.CO], 2016.
%H A090981 Valerie Roitner, <a href="https://arxiv.org/abs/2008.02240">The vectorial kernel method for walks wíth longer steps</a>, arXiv:2008.02240 [math.CO], 2020.
%F A090981 T(n, k) = binomial(n+1, k)*Sum_{j=0..n-k} binomial(n+1, j)*binomial(n-j-1, k-1)/(n+1).
%F A090981 G.f.: G=G(t, z) satisfies z*(1-z+t*z)G^2 - (1-t*z)G + 1 = 0.
%e A090981 T(2,1)=4 because we have the following four Schroeder paths of length 4 with one ascent: (U)HD, (UU)DD, H(U)D and (U)DH (ascents shown between parentheses).
%e A090981 Triangle starts:
%e A090981   1;
%e A090981   1,   1;
%e A090981   1,   4,   1;
%e A090981   1,  11,   9,   1;
%e A090981   1,  26,  46,  16,   1;
%e A090981   1,  57, 180, 130,  25,  1;
%e A090981   ...
%p A090981 T := (n,k)->binomial(n+1,k)*add(binomial(n+1,j)*binomial(n-j-1,k-1),j=0..n-k)/(n+1): seq(seq(T(n,k),k=0..n),n=0..12);
%t A090981 m = 11(*rows*); G = 0; Do[G = Series[(1+G^2 z(1+(t-1)z))/(1-t z), {t, 0, m-1}, {z, 0, m-1}] // Normal // Expand, {m}]; CoefficientList[#, t]& /@ CoefficientList[G, z]//Flatten (* _Jean-François Alcover_, Jan 22 2019 *)
%t A090981 Table[Binomial[n+1,k]*Sum[Binomial[n+1,j]*Binomial[n-j-1,k-1], {j,0,n-k}]/(n+1), {n,0,12}, {k,0,n}]//Flatten (* _G. C. Greubel_, Feb 02 2019 *)
%o A090981 (PARI) {T(n,k) = if(k==0, 1, binomial(n+1,k)*sum(j=0,n-k, binomial(n+1,j) *binomial(n- j-1, k-1))/(n+1))};
%o A090981 for(n=0,12, for(k=0,n, print1(T(n,k), ", "))) \\ _G. C. Greubel_, Feb 02 2019
%o A090981 (Magma) [[k le 0 select 1 else Binomial(n+1,k)*(&+[Binomial(n+1,j)* Binomial(n-j-1,k-1): j in [0..n-k]])/(n+1): k in [0..n]]: n in [0..12]]; // _G. C. Greubel_, Feb 02 2019
%o A090981 (Sage) [[1] + [binomial(n+1,k)*sum(binomial(n+1,j)*binomial(n-j-1,k-1) for j in (0..n-k))/(n+1) for k in (1..n)] for n in (0..12)] # _G. C. Greubel_, Feb 02 2019
%Y A090981 Cf. A000295, A006318.
%K A090981 nonn,tabl
%O A090981 0,5
%A A090981 _Emeric Deutsch_, Feb 29 2004