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!)
A090981 Triangle read by rows: T(n,k) = number of Schroeder paths of length 2n and having k ascents. 2
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, 295, 36, 1, 1, 247, 1827, 3507, 2345, 581, 49, 1, 1, 502, 5164, 14224, 14518, 6076, 1036, 64, 1, 1, 1013, 13878, 52068, 75558, 48006, 13776, 1716, 81, 1, 1, 2036, 35905, 176430 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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).

Row sums give A006318 (the large Schroeder numbers). Column 1 gives A000295 (the Eulerian numbers).

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

Conjecture: The expected number of ascents in a Schroeder n-path is asymptotically (sqrt(2)-1)*n for large n. - David Callan, Jul 25 2008

LINKS

G. C. Greubel, Rows n=0..100 of triangle, flattened

L. Ferrari, E. Munarini, Enumeration of Edges in Some Lattices of Paths, J. Int. Seq. 17 (2014) #14.1.5

Zhicong Lin, Dongsu Kim, A sextuple equidistribution arising in Pattern Avoidance, arXiv:1612.02964 [math.CO], 2016.

FORMULA

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

G.f.: G=G(t, z) satisfies z*(1-z+t*z)G^2 - (1-t*z)G + 1 = 0.

EXAMPLE

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).

Triangle starts:

  1;

  1,   1;

  1,   4,   1;

  1,  11,   9,   1;

  1,  26,  46,  16,   1;

  1,  57, 180, 130,  25,  1;

  ...

MAPLE

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);

MATHEMATICA

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 *)

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 *)

PROG

(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))};

for(n=0, 12, for(k=0, n, print1(T(n, k), ", "))) \\ G. C. Greubel, Feb 02 2019

(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

(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

CROSSREFS

Cf. A000295, A006318.

Sequence in context: A331969 A203860 A147564 * A087903 A287532 A112500

Adjacent sequences:  A090978 A090979 A090980 * A090982 A090983 A090984

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Feb 29 2004

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 August 9 05:12 EDT 2020. Contains 336319 sequences. (Running on oeis4.)