A202411 -id:A202411 - cp's OEIS frontend

A110236 Number of (1,0) steps in all peakless Motzkin paths of length n (can be easily translated into RNA secondary structure terminology).

1, 2, 4, 10, 24, 58, 143, 354, 881, 2204, 5534, 13940, 35213, 89162, 226238, 575114, 1464382, 3734150, 9534594, 24374230, 62377881, 159793932, 409717004, 1051405260, 2700168229, 6939388478, 17845927498, 45922416814, 118238842174

Offset: 1

Emeric Deutsch, Jul 17 2005

nonn

Number of UHD's in all peakless Motzkin paths of length n+2; here U=(1,1), H=(1,0), and D=(1,-1). Example: a(2)=2 because in HHHH, HUHD, UHDH, and UHHD we have a total of 0+1+1+0 UHD's.

			a(3)=4 because in the 2 (=A004148(3)) peakless Motzkin paths of length 3, namely HHH and UHD (where U=(1,1), H=(1,0) and D=(1,-1)), we have altogether 4 H steps.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Grand Dyck paths with air pockets, arXiv:2211.04914 [math.CO], 2022.
W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.

Cf. A004148, A110235, A089732, A190172, A203611, bisection of A202411.

T:=proc(n,k) if n+k mod 2 = 0 then 2*binomial((n+k)/2,k)*binomial((n+k)/2,k-1)/(n+k) else 0 fi end:seq(add(k*T(n,k),k=1..n),n=1..33);

Rest[CoefficientList[Series[((1-x+x^2)*((x^2+x+1)*(x^2-3*x+1))^(-1/2)-1) /(2*x), {x, 0, 20}], x]] (* Vaclav Kotesovec, Feb 13 2014 *)

x='x+O('x^66); Vec(((1-x+x^2)*((x^2+x+1)*(x^2-3*x+1))^(-1/2)-1)/(2*x)) /* Joerg Arndt, Mar 27 2013 */

a(n) = Sum_{k=1..n} k*T(n, k), where T(n, k) = floor(2/(n+k))*binomial((n+k)/2, k)*binomial((n+k)/2, k-1) for n+k mod 2 = 0 and T(n, k)=0 otherwise.
G.f.: (1-z+z^2-Q)/(2*z*Q), where Q = sqrt(1 - 2z - z^2 - 2z^3 + z^4).
a(n) = Sum_{k=1..n} k*A110235(n,k).
a(n) = Sum_{k>=0} k*A190172(n+2,k).
a(n+1) = Sum_{k=0..n} Sum_{j=0..n-k} C(k+j,n-k-j)*C(k,n-k-j). - Paul Barry, Oct 24 2006, index corrected Jul 13 2011
a(n+1) = Sum_{k=0..floor(n/2)} C(n-k+1,k+1)*C(n-k,k); a(n+1) := Sum_{k=0..n} C(k+1,n-k+1)*C(k,n-k). - Paul Barry, Aug 17 2009, indices corrected Jul 13 2011
G.f.: z*S^2/(1-z^2*S^2), where S = 1 + z*S + z^2*S*(S-1) (the g.f. of the RNA secondary structure numbers; A004148).
a(n) = -f_{n}(-n) with f_1(n)=n and f_{p}(n) = (n+p-1)*(n+p+1-1)^2 *(n+p+2-1)^2*...*(n+p+(p-1)-1)^2/(p!*(p-1)!) + f_{p-1}(n) for p > 1. - Alzhekeyev Ascar M, Jun 27 2011
Let A=floor(n/2), R=n-1, B=A-R/2+1, C=A+1, D=A-R and Z=1 if n mod 2 = 1, otherwise Z = n*(n+2)/4. Then a(n) = Z*Hypergeometric([1,C,C+1,D,D-1],[B,B,B-1/2,B-1/2],1/16). - Peter Luschny, Jan 14 2012
D-finite with recurrence (n+1)*a(n) -3*n*a(n-1) +2*(n-3)*a(n-2) +3*(-n+2)*a(n-3) +2*(n-1)*a(n-4) +3*(-n+4)*a(n-5) +(n-5)*a(n-6)=0. - R. J. Mathar, Nov 30 2012
G.f.: ((1-x+x^2)*((x^2+x+1)*(x^2-3*x+1))^(-1/2)-1)/(2*x). - Mark van Hoeij, Mar 27 2013
From Vaclav Kotesovec, Feb 13 2014: (Start)
Recurrence: (n-2)*(n-1)*(n+1)*a(n) = (n-2)*n*(2*n-1)*a(n-1) + (n-1)*(n^2 - 2*n - 2)*a(n-2) + (n-2)*n*(2*n-3)*a(n-3) - (n-3)*(n-1)*n*a(n-4).
a(n) ~ (sqrt(5)+3)^(n+1) / (5^(1/4) * sqrt(Pi*n) * 2^(n+2)). (End)

A203611 a(n) = Sum_{k=0..n} binomial(k-1,2k-1-n)binomial(k,2*k-n), with a(0) = 1.

Original entry on oeis.org

1, 1, 1, 3, 7, 16, 39, 95, 233, 577, 1436, 3590, 9011, 22691, 57299, 145043, 367931, 935078, 2380405, 6068745, 15492702, 39598631, 101323446, 259522398, 665332007, 1707137941, 4383662419, 11264675925, 28966161253, 74530441162, 191879611399, 494265165151

Offset: 0

Peter Luschny, Jan 14 2012

nonn

For the connection with Fibonacci meanders classified by maximal run length of 1s (see the link).

Apparently the number of grand Motzkin paths of length n+1 that avoid UU. - David Scambler, Jul 04 2013

Michael De Vlieger, Table of n, a(n) for n = 0..2397
Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Grand Dyck paths with air pockets, arXiv:2211.04914 [math.CO], 2022.
Jean-Luc Baril and José L. Ramírez, Fibonacci and Catalan paths in a wall, 2023.
Peter Luschny, Fibonacci meanders.

Cf. A110236, bisection of A202411.

A203611:= func< n | n eq 0 select 1 else (&+[Binomial(k-1,2*k-n-1)*Binomial(k,2*k-n): k in [0..n]]) >;
[A203611(n): n in [0..40]]; // G. C. Greubel, Mar 12 2025

a := n -> hypergeom([-n/2, 1 - n/2, (1-n)/2, (1-n)/2], [1, -n, 1 - n], 16):
seq(simplify(a(n)), n = 0..31); # Peter Luschny, Mar 24 2023

a[n_] := Module[{a, r, b, c, d, z}, If[n == 0, Return[1]]; a = Quotient[n, 2]; r = n-1; b = a-r/2+1; c = a+1; d = a-r; z = If[Mod[n, 2] == 1, (n+1)/2, n^2*(n+2)/16]; z*HypergeometricPFQ[{1, c, c+1, d, d}, {b, b, b-1/2, b+1/2}, 1/16] ]; Table[a[n], {n, 0, 31}] (* Jean-François Alcover, Jun 27 2013, translated from Maple *)
Table[Sum[Binomial[k-1,2k-1-n]Binomial[k,2k-n],{k,0,n}],{n,0,40}] (* Harvey P. Dale, May 25 2014 *)

my(x='x+O('x^66)); Vec( 2*x/((1+x-x^2) * sqrt((x^2+x+1) * (x^2-3*x+1)) -x^4 +2*x^3 +x^2 +2*x -1) ) \\ Joerg Arndt, May 06 2013

def A203611(n): return 1 if n==0 else sum(binomial(k-1,2*k-n-1)*binomial(k,2*k-n) for k in range(n+1))
print([A203611(n) for n in range(41)]) # G. C. Greubel, Mar 12 2025

For n>0 let A=floor(n/2), R = n-1, B = A - R/2 + 1, C = A+1, D = A-R and Z = (n+1)/2 if n mod 2 = 1, otherwise Z = n^2*(n+2)/16. Then a(n) = Z*Hypergeometric5F4([1,C,C+1,D,D],[B,B,B-1/2,B+1/2],1/16).
G.f.: 2*x/((1+x-x^2)*sqrt((1+x+x^2)*(1-3*x+x^2)) - (1-2*x-x^2-2*x^3+x^4)). - Mark van Hoeij, May 06 2013
a(n) ~ phi^(2*n + 1) / (2 * 5^(1/4) * sqrt(Pi*n)), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Jun 08 2019
a(n) = hypergeom([-n/2, 1 - n/2, (1-n)/2, (1-n)/2], [1, -n, 1 - n], 16). - Peter Luschny, Mar 24 2023
D-finite with recurrence n*a(n) -(n+1)*a(n-1) -2*(2*n-5)*a(n-2) -(n+3)*a(n-3) +3*(n-5)*a(n-5) -(n-6)*a(n-6) = 0. - R. J. Mathar, Nov 22 2024

A201631 a(n) is the number of Fibonacci meanders of length m*n and central angle 360/m degrees where m = 2.

Original entry on oeis.org

1, 3, 6, 13, 30, 70, 167, 405, 992, 2450, 6090, 15214, 38165, 96069, 242530, 613811, 1556856, 3956316, 10070871, 25674210, 65541142, 167517654, 428635032, 1097874434, 2814611701, 7221917871, 18544968768, 47655572191, 122544150258, 315313433594, 811792614547

Offset: 1

Peter Luschny, Jan 15 2012

nonn

Empirically the partial sums of A051291. - Sean A. Irvine, Jul 13 2022

The above conjecture was proved by Baril et al., which also give a formal definition of the Fibonacci meanders and describe a bijection with a certain class of peakless grand Motzkin paths of length n. - Peter Luschny, Mar 16 2023

			a(3) = 6 = card({100001, 100100, 110000, 111001, 111100, 111111}).

Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Enumeration of Dyck paths with air pockets, arXiv:2202.06893 [cs.DM], 2022-2023.
Peter Luschny, Fibonacci meanders.

Cf. A110236, A110198, A202411, A203611, A051291, A358734.

Cf. A361574 (case m=3).

A201631 := n -> add(A202411(k),k=0..2*n-1): seq(A201631(i),i=1..9);
# Alternative, using the g.f. of Baril et al.:
S := (x^2 - x + 1 - R)/((x - 1)*(x^2 - x - 1 + R)*R):
R := (((x - 3)*x + 1)*(x^2 + x + 1))^(1/2): ser := series(S, x, 33):
seq(coeff(ser, x, n), n = 1..31); # Peter Luschny, Mar 16 2023
# Using a recurrence:
a := proc(n) option remember; if n < 5 then return [0, 1, 3, 6, 13][n + 1] fi;
(n*(2*n - 1)*(2*n - 3)*(n - 5)*a(n - 5) - (n - 4)*(2*n - 1)^2*(3*n - 5)*a(n - 4) + (2*n - 5)*(n - 3)*(2*n^2 - 3*n + 2)*a(n - 3) - (2*n - 3)*(n - 2)*(2*n^2 - 3*n + 5)*a(n - 2) + (3*n - 4)*(2*n - 1)*(2*n - 5)*(n - 1)*a(n - 1))/(n*(2*n - 3)*(2*n - 5)*(n - 1)) end: seq(a(n), n = 1..31); # Peter Luschny, Mar 16 2023

a[n_] := Sum[A202411[k], {k, 0, 2 n - 1}];
Array[a, 31] (* Jean-François Alcover, Jun 29 2019 *)

a(n) = Sum_{k=0..2n-1} A202411(k).

a(n) = [x^n] (x^2 - x + 1 - R)/((x - 1)*(x^2 - x - 1 + R) * R), where R = (((x - 3)*x + 1)*(x^2 + x + 1))^(1/2). (This is Theorem 21 in Baril et al.) - Peter Luschny, Mar 16 2023

A110198 Antidiagonal sums of number triangle A110197.

Original entry on oeis.org

1, 2, 4, 9, 20, 46, 109, 262, 638, 1569, 3886, 9680, 24225, 60856, 153368, 387573, 981742, 2491934, 6336721, 16139616, 41166912, 105139773, 268841100, 688157430, 1763206441, 4521749642, 11605580290, 29809644693, 76621733444, 197074591420, 507193044993

Offset: 0

Paul Barry, Jul 15 2005

Partial sums of A051286.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A051286, A110197, A201631.

CoefficientList[Series[1/((1-x)*Sqrt[(1+x+x^2)*(1-3*x+x^2)]), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 08 2014 *)

G.f.: 1/((1-x)*sqrt((1+x+x^2)*(1-3x+x^2))); a(n) = sum{k=0..floor(n/2), sum{i=0..n-2k, binomial(i+k, k)^2}}.
a(n) = sum{i=0..2n, A202411(i)}. - Peter Luschny, Jan 16 2012
Conjecture: n*a(n) +(-3*n+1)*a(n-1) +n*a(n-2) +(-n+2)*a(n-3) +(3*n-5)*a(n-4) +(-n+2)*a(n-5)=0. - R. J. Mathar, Nov 15 2012
a(n) ~ sqrt(100+45*sqrt(5)) * ((sqrt(5)+3)/2)^n / (10*sqrt(Pi*n)). - Vaclav Kotesovec, Feb 08 2014
Equivalently, a(n) ~ phi^(2*n + 3) / (2 * 5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 07 2021

cp's OEIS Frontend

A110236 Number of (1,0) steps in all peakless Motzkin paths of length n (can be easily translated into RNA secondary structure terminology).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A203611 a(n) = Sum_{k=0..n} binomial(k-1,2*k-1-n)*binomial(k,2*k-n), with a(0) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A201631 a(n) is the number of Fibonacci meanders of length m*n and central angle 360/m degrees where m = 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A110198 Antidiagonal sums of number triangle A110197.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A203611 a(n) = Sum_{k=0..n} binomial(k-1,2k-1-n)binomial(k,2*k-n), with a(0) = 1.