A155069 -id:A155069 - cp's OEIS frontend

A132372 T(n, k) counts Schroeder n-paths whose ascent starting at the initial vertex has length k. Triangle T(n,k), read by rows.

1, 1, 1, 2, 3, 1, 6, 10, 5, 1, 22, 38, 22, 7, 1, 90, 158, 98, 38, 9, 1, 394, 698, 450, 194, 58, 11, 1, 1806, 3218, 2126, 978, 334, 82, 13, 1, 8558, 15310, 10286, 4942, 1838, 526, 110, 15, 1, 41586, 74614, 50746, 25150, 9922, 3142, 778, 142, 17, 1

Offset: 0

Philippe Deléham, Nov 20 2007

Triangle T(n,k), 0<=k<=n, read by rows given by [1,1,2,1,2,1,2,1,2,...] DELTA [1,0,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938 .
Transpose of triangular array A033878. - Michel Marcus, May 02 2015
The triangle is the Riordan square (A321620) of A155069. - Peter Luschny, Feb 01 2020

			Triangle begins:
      1;
      1,     1;
      2,     3,     1;
      6,    10,     5,     1;
     22,    38,    22,     7,    1;
     90,   158,    98,    38,    9,    1;
    394,   698,   450,   194,   58,   11,   1;
   1806,  3218,  2126,   978,  334,   82,  13,   1;
   8558, 15310, 10286,  4942, 1838,  526, 110,  15,  1;
  41586, 74614, 50746, 25150, 9922, 3142, 778, 142, 17, 1 ; ...
...
The production matrix M begins:
  1, 1
  1, 2, 1
  1, 2, 2, 1
  1, 2, 2, 2, 1
  1, 2, 2, 2, 2, 1
  ...

Lili Mu and Sai-nan Zheng, On the Total Positivity of Delannoy-Like Triangles, Journal of Integer Sequences, Vol. 20 (2017), Article 17.1.6.
E. Pergola and R. A. Sulanke, Schroeder Triangles, Paths and Parallelogram Polyominoes, Journal of Integer Sequences, Vol. 1 (1998), #98.1.7.

Cf. A006318, A103136 (signed version), A033878 (transpose).

Cf. A155069, A321620.

# The function RiordanSquare is defined in A321620.
RiordanSquare((3-x-sqrt(1-6*x+x^2))/2, 10); # Peter Luschny, Feb 01 2020
# Alternative:
A132372 := proc(dim) # dim is the number of rows requested.
local T, j, A, k, C, m; m := 1;
T := [seq([seq(0, j = 0..k)], k = 0..dim-1)];
A := [seq(ifelse(k = 0, 1 + x, 2 - irem(k, 2)), k = 0..dim-2)];
C := [seq(1, k = 1..dim+1)]; C[1] := 0;
for k from 0 to dim - 1 do
    for j from k + 1 by -1 to 2 do
        C[j] := C[j-1] + C[j+1] * A[j-1] od;
    T[m] := [seq(coeff(C[2], x, j), j = 0..k)];
    m := m + 1
od; ListTools:-Flatten(T) end:
A132372(10);  # Peter Luschny, Nov 16 2023

Sum_{k, 0<=k<=n} T(n,k) = A006318(n) .

T(n,0) = A155069(n). - Philippe Deléham, Nov 03 2009

A224071 Number of Schroeder paths of semilength n in which there are no (2,0)-steps at level 1.

Original entry on oeis.org

1, 2, 5, 15, 52, 201, 841, 3726, 17213, 82047, 400600, 1993377, 10071777, 51532938, 266462229, 1390174911, 7308741084, 38682855225, 205940368441, 1102091393574, 5925177392573, 31987877317887, 173337754977904

Offset: 0

José Luis Ramírez Ramírez, Mar 30 2013

nonn

Hankel transform is A006215. Invert transform of A155069. - Michael Somos, Apr 02 2013

			a(2) = 5 because we have HH, UDH, HUD, UDUD and UUDD.
G.f. = 1 + 2*x + 5*x^2 + 15*x^3 + 52*x^4 + 201*x^5 + 841*x^6 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..200
J. Bloom and S. Elizalde, Pattern avoidance in matchings and partitions, arXiv:1211.3442 [math.CO], 2012; Theorem 6.1.
Paul Barry, A study of Integer Sequences, Riordan Arrays, Pascal-like Arrays and Hankel Transforms, Ph.D Thesis, University College, Cork, Republic of Ireland, 2009.
Arnauld Mesinga Mwafise, Computational and Combinatorial Enumeration of Poset Matrices, 2024. See p. 8.

Cf. A001003, A007564, A010892, A059231.

CoefficientList[Series[4/(3-5*x+Sqrt[x^2-6*x+1]), {x, 0, 20}], x] (* Vaclav Kotesovec, May 23 2013 *)
a[ n_] := SeriesCoefficient[ (3 - 5 x - Sqrt[ 1 - 6 x + x^2]) / (2 - 6 x + 6 x^2), {x, 0, n}]; (* Michael Somos, Mar 28 2014 *)

a(n):=sum((k+1)*((-1)^floor((k+2)/3)+(-1)^floor((k+1)/3))*sum(binomial(n+1,n-k-i)*binomial(n+i,n),i,0,n-k),k,0,n)/(2*(n+1)); /* Vladimir Kruchinin, Mar 08 2016*/

z='z+O('z^66); Vec(4/(3-5*z+sqrt(1-6*z+z^2))) /* Joerg Arndt, Mar 30 2013 */

G.f.: 4/(3-5*x+sqrt(1-6*x+x^2)).
Recurrence: n*a(n) = 9*(n-1)*a(n-1) - 2*(11*n-15)*a(n-2) + 3*(7*n-12)*a(n-3) - 3*(n-3)*a(n-4). - Vaclav Kotesovec, May 23 2013
a(n) ~ sqrt(884+627*sqrt(2)) * (3+2*sqrt(2))^n / (98*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, May 23 2013
0 = +a(n)*(+9*a(n+1) - 144*a(n+2) + 174*a(n+3) - 81*a(n+4) + 12*a(n+5)) + a(n+1)*(+18*a(n+1) + 399*a(n+2) - 597*a(n+3) + 318*a(n+4) - 57*a(n+5)) + a(n+2)*(-300*a(n+2) + 538*a(n+3) - 255*a(n+4) + 52*a(n+5)) + a(n+3)*(-126*a(n+3) + 73*a(n+4) - 18*a(n+5)) + a(n+4)*(+a(n+5)) if n>=0. - Michael Somos, Mar 28 2014
a(n) = Sum_{k=0..n}((k+1)*((-1)^floor((k+2)/3)+(-1)^floor((k+1)/3))*Sum_{i=0..n-k}(binomial(n+1,n-k-i)*binomial(n+i,n)))/(2*(n+1)). - Vladimir Kruchinin, Mar 08 2016

A167656 Triangle T(n,k), 0<=k<=n, read by rows given by [1,1,2,1,2,1,2,1,2,1,2,...] DELTA [1,1,0,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 1, 1, 2, 4, 2, 6, 16, 14, 4, 22, 68, 78, 40, 8, 90, 304, 410, 284, 104, 16, 394, 1412, 2122, 1776, 896, 256, 32, 1806, 6752, 10966, 10468, 6496, 2592, 608, 64, 8558, 33028, 56870, 59832, 43016, 21376, 7072, 1408, 128, 41586, 164512, 296498, 336252

Offset: 0

Philippe Deléham, Nov 08 2009

			Triangle begins:
1 ;
1,1 ;
2,4,2 ;
6,16,14,4 ;
22,68,78,40,8 ;
90,304,410,284,104,16 ;
...

Cf. A132372, A155069, A006319, A011782.

T(n,0) = T(n-1,0) + T(n-1,1).
T(n,1) = T(n-1,0) + 3*T(n-1,1) + T(n-1,2).
T(n,k) = 2*T(n-1,k-1) + 3*T(n-1,k) + T(n-1,k+1) for k>1.

A176006 The number of branching configurations of RNA (see Sankoff, 1985) with n or fewer hairpins.

Original entry on oeis.org

1, 2, 4, 10, 32, 122, 516, 2322, 10880, 52466, 258564, 1296282, 6589728, 33887466, 175966212, 921353250, 4858956288, 25786112994, 137604139012, 737922992938, 3974647310112, 21493266631002, 116642921832964, 635074797251890

Offset: 0

Lee A. Newberg, Apr 05 2010

a(n) is the number of dissections of a convex (n+2)-sided polygon by non-intersecting diagonals such that selected least two consecutive sides of the polygon will be in the same sub-polygon. - Muhammed Sefa Saydam, Jul 02 2025

			For n = 3, the a(3) = 10 branching configurations with 3 or fewer hairpins are: unfolded, (), ()(), (()()), ()()(), (()())(), ()(()()), (()()()), ((()())()), and (()(()())).

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
David Sankoff, Simultaneous solution of the RNA folding, alignment and protosequence problems, SIAM J. Appl. Math 45(5) (1985), 810-825.
David Sankoff, Simultaneous solution of the RNA folding, alignment and protosequence problems, SIAM J. Appl. Math 45(5) (1985), 810-825.

The cumulative sums of A155069.

CoefficientList[Series[(3-x-Sqrt[1-6*x+x^2])/(2*(1-x)), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 20 2012 *)

my(x='x+O('x^50)); Vec((3-x-sqrt(1-6*x+x^2))/(2*(1-x))) \\ G. C. Greubel, Mar 22 2017

G.f.: (3 - x - sqrt(1 - 6*x + x^2))/(2*(1 - x)).
Conjecture : n*a(n) +(9-7*n)*a(n-1) +(7*n-12)*a(n-2) +(3-n)*a(n-3)=0. - R. J. Mathar, Jul 24 2012
a(n) ~ 2^(1/4)*(3 + 2*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 20 2012
a(n) = Sum_{x+y=n+1} A006318(x), for y >= 2, x >= -1 and A006318(-1) = 1. - Muhammed Sefa Saydam, Jul 02 2025

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

Original entry on oeis.org

1, 3, 11, 47, 219, 1075, 5459, 28383, 150131, 804515, 4355163, 23768079, 130572363, 721247571, 4002344355, 22296869823, 124633584099, 698707769923, 3927060020651, 22121780745711, 124865811262139, 706065855417203, 3998950848888051

Offset: 0

Vladimir Kruchinin, Sep 26 2015

nonn

D. Drake, Bijections from Weighted Dyck Paths to Schröder Paths, J. Int. Seq. 13 (2010) # 10.9.2, Table 1.

Cf. A155069.

Table[Sum[(k + 1) Binomial[n + 1, k] Binomial[2 n - k, n]/(n + 1), {k,
0, n}], {n, 0, 22}] (* Michael De Vlieger, Sep 26 2015 *)

A(x):=x*(3-x-sqrt(1-6*x+x^2))/2;
taylor(-diff(A(x),x)/A(x)+diff(A(x),x,1)/x,x,0,27);

G.f.: (-2*x^2+7*x-1)/(2*x*sqrt(x^2-6*x+1))+1/(2*x)-1.
G.f. satisfies -A'(x)/A(x)+A'(x)/x, where A(x)/x is g.f. of A155069
-(n+1)*(2*n^2+5*n-6)*a(n) +6*(2*n^3+6*n^2-11*n+4)*a(n-1) -(n-2)*(2*n^2+9*n+1)*a(n-2)=0. - R. J. Mathar, Jul 21 2017
a(n) ~ (1 + sqrt(2))^(2*n) / (2^(5/4) * sqrt(Pi*n)). - Vaclav Kotesovec, Jul 10 2021

A341695 Regular triangle read by rows, T(n,k) = T(n,k-1)+2*T(n-1,k)-T(n-1,k-1) for 1<=k<=n-2 with T(n,n)=T(n,n-1)=T(n,n-2) for n>=3 and T(1,1)=T(2,1)=T(2,2)=1.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 4, 6, 6, 6, 8, 16, 22, 22, 22, 16, 40, 68, 90, 90, 90, 32, 96, 192, 304, 394, 394, 394, 64, 224, 512, 928, 1412, 1806, 1806, 1806, 128, 512, 1312, 2656, 4552, 6752, 8558, 8558, 8558, 256, 1152, 3264, 7264, 13712, 22664, 33028, 41586, 41586, 41586

Offset: 1

Michel Marcus, Apr 12 2021

			Triangle begins:
   1;
   1,  1;
   2,  2,  2;
   4,  6,  6,  6;
   8, 16, 22, 22, 22;
  16, 40, 68, 90, 90, 90;
  ...

Dongsu Kim and Zhicong Lin, Refined restricted inversion sequences, arXiv:1706.07208 [math.CO], 2017-2020.
Toufik Mansour and Mark Shattuck, On a conjecture of Lin and Kim concerning a refinement of Schröder numbers, arXiv:2104.04491 [math.CO], 2021.

Cf. A011782 (1st column), A155069 (right diagonal).

T(n,k) = if (k>=1, if (n<=2, 1, if (k<=n-2, T(n,k-1)+2*T(n-1,k)-T(n-1,k-1), T(n,n-2))));
tabl(nn) = {for (n=1, nn, for (k=1, n, print1(T(n,k), ", ");); print;);}

cp's OEIS Frontend

A132372 T(n, k) counts Schroeder n-paths whose ascent starting at the initial vertex has length k. Triangle T(n,k), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A224071 Number of Schroeder paths of semilength n in which there are no (2,0)-steps at level 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

A167656 Triangle T(n,k), 0<=k<=n, read by rows given by [1,1,2,1,2,1,2,1,2,1,2,...] DELTA [1,1,0,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Examples

Crossrefs

Formula

A176006 The number of branching configurations of RNA (see Sankoff, 1985) with n or fewer hairpins.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Maxima

Formula

A341695 Regular triangle read by rows, T(n,k) = T(n,k-1)+2*T(n-1,k)-T(n-1,k-1) for 1<=k<=n-2 with T(n,n)=T(n,n-1)=T(n,n-2) for n>=3 and T(1,1)=T(2,1)=T(2,2)=1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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