A274115 -id:A274115 - cp's OEIS frontend

A274114 Number of equivalence classes of Dyck paths of semilength n for the string uuu.

1, 1, 1, 2, 4, 8, 17, 37, 81, 180, 405, 917, 2090, 4795, 11054, 25589, 59475, 138712, 324483, 761163, 1790028, 4219139, 9965328, 23582735, 55906518, 132751359, 315700152, 751837207, 1792853416, 4280568845, 10232005939, 24484563844, 58650123942, 140625967460, 337488663293, 810641635789

Offset: 0

N. J. A. Sloane, Jun 17 2016

Gheorghe Coserea, Table of n, a(n) for n = 0..301
K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.

Cf. A274110-A274115.

F[x_, y_] = x y^3 - (1 + 2x) y^2 + (1 + 3x) y - x;
Y[n_] := Module[{y0 = 1, y1 = 0}, For[k = 1, k <= n, k++, y1 = y0 - F[x, y0] / (D[F[x, y], y] /. y -> y0) + O[x]^n // Normal; If[y1 == y0, Break[]]; y0 = y1]; y0];
seq[n_] := Module[{y = Y[n]}, ((1 + x y)/(1 - x (y-1)^2)) + O[x]^n // CoefficientList[#, x]&];
seq[36] (* Jean-François Alcover, Jul 27 2018, after Gheorghe Coserea *)

x='x; y='y;
Fxy = x*y^3 - (1+2*x)*y^2 + (1+3*x)*y - x;
Y(N) = {
  my(y0 = 1 + O('x^N), y1=0);
  for (k = 1, N,
    y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);
    if (y1 == y0, break()); y0 = y1);
  y0;
};
seq(N) = my(y = Y(N)); Vec((1 + x*y)/(1 - x*(y-1)^2));
seq(35) \\ Gheorghe Coserea, Jan 05 2017

A(x) = (1 + x*y)/(1 - x*(y-1)^2), where 0 = x*y^3 - (1+2*x)*y^2 + (1+3*x)*y - x with y(0)=1. - Gheorghe Coserea, Jan 05 2017

a(n) ~ sqrt(51/4 + 577*sqrt(2)/64 + 19*sqrt(180250 + 127456*sqrt(2))/448) * (sqrt(13 + 16*sqrt(2))/2 - 1/2)^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Apr 25 2020

a(0)=1 prepended and more terms added by Gheorghe Coserea, Jan 05 2017

A274112 Number of equivalence classes of ballot paths of length n for the string ddu.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 5, 8, 12, 17, 23, 35, 52, 75, 105, 157, 232, 337, 480, 712, 1049, 1529, 2199, 3248, 4777, 6976, 10092, 14869, 21845, 31937, 46377, 68222, 100159, 146536, 213328, 313487, 460023, 673351, 981976, 1441999, 2115350, 3097326, 4522529, 6637879, 9735205, 14257734, 20836827, 30572032, 44829766, 65666593

Offset: 0

N. J. A. Sloane, Jun 17 2016

Gheorghe Coserea, Table of n, a(n) for n = 0..300
K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015, Section 3.4.

Cf. A274110-A274115, A263719.

A274112 := proc(n)
    add( (n-4*i+1)/(n-3*i+1)*binomial(n-2*i,i),i=0..n/4) ;
end proc:
seq(A274112(n),n=0..50) ; # R. J. Mathar, Jun 20 2016

a[n_] := Sum[(n - 4*i + 1)/(n - 3*i + 1)*Binomial[n - 2*i, i], {i, 0, n/4} ];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 27 2017, after R. J. Mathar *)

x='x; y='y;
Fxy = x*(x^3+x-1)*y^2 + (2*x-1)*y + 1;
seq(N) = {
  my(y0 = 1 + O('x^N), y1=0);
  for (k = 1, N,
    y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);
    if (y1 == y0, break()); y0 = y1);
  Vec(y0);
};
seq(51)  \\ Gheorghe Coserea, Jan 05 2017

G.f. y satisfies: 0 = x*(x^3+x-1)*y^2 + (2*x-1)*y + 1. - Gheorghe Coserea, Jan 05 2017
G.f.: 1/(1 - x - x^4/(1 - x^4/(1 - x^4/(1 - x^4/(1 - ...))))), a continued fraction. - Ilya Gutkovskiy, Jul 26 2017
a(n) ~ 3 * (1+r^2)^(n+1) / (7 + 4*r + 8*r^2), where r = A263719 = ((9+sqrt(93))/2)^(1/3)/3^(2/3) - (2/(3*(9+sqrt(93))))^(1/3) = 0.682327803828019327369483739711048256891188581898... is the real root of the equation r^3 + r = 1. - Vaclav Kotesovec, Nov 27 2017

a(0)=1 prepended by Gheorghe Coserea, Jan 05 2017

A191385 Number of dispersed Dyck paths of length n having no ascents of length 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 5, 7, 12, 18, 31, 47, 81, 125, 216, 337, 583, 918, 1590, 2522, 4372, 6977, 12104, 19415, 33703, 54297, 94306, 152507, 265005, 429974, 747450, 1216297, 2115118, 3450817, 6002813, 9816460, 17080924, 27991422, 48718380, 79989880, 139252802, 229034820, 398806718

Offset: 0

Emeric Deutsch, Jun 01 2011

Dispersed Dyck paths are Motzkin paths with no (1,0) steps at positive heights. An ascent is a maximal sequence of consecutive (1,1)-steps.

The number of UU-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are UU-equivalent iff the positions of pattern UU are identical in these paths. - Sergey Kirgizov, Apr 08 2018

			a(5)=3 because we have HHHHH, HUUDD, and UUDDH, where U=(1,1), D=(1,-1), and H=(1,0).

Gheorghe Coserea, Table of n, a(n) for n = 0..300
J.-L. Baril, R. Genestier, A. Giorgetti, and A. Petrossian, Rooted planar maps modulo some patternss, Preprint 2016.
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
J.-L. Baril and A. Petrossian, Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two, J. Int. Seq. 18 (2015) 15.7.1
K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.
Helmut Prodinger, Dispersed Dyck paths revisited, arXiv:2402.13026 [math.CO], 2024. See p. 3.

Cf. A191384, A274110-A274115.

g := (((1-z)^2-sqrt((1+z^2)*(1-3*z^2)))*1/2)/(z*(z^3-(1-z)^2)): gser := series(g, z = 0, 45): seq(coeff(gser, z, n), n = 0 .. 42);

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

seq(N) = {
  my(x='x+O('x^N), A001006 = (1 - x - sqrt(1-2*x-3*x^2))/(2*x^2),
     y=subst(A001006, 'x, 'x^2));
  Vec((1+x^2*y) / (1-x+x^2-x^3*y));
};
seq(43)  \\ Gheorghe Coserea, Jan 06 2017

a(n) = A191384(n,0).
G.f.: g(z) = ((1-z)^2 - sqrt((1+z^2)*(1-3*z^2)))/(2*z*(z^3-(1-z)^2)).
a(n-1) = Sum_{m=floor((n+1)/2)..n} ((2*m-n)*sum(j=2*m-n..m, binomial(n-2*m+2*j-1,j-1)*(-1)^(j-m)*binomial(m,j)))/m. - Vladimir Kruchinin, Mar 09 2013
Recurrence: (n+1)*a(n) = 2*(n+1)*a(n-1) + (n-5)*a(n-2) - 3*(n-3)*a(n-3) + (5*n-19)*a(n-4) - 2*(4*n-17)*a(n-5) + 3*(n-5)*a(n-6) - 3*(n-5)*a(n-7). - Vaclav Kotesovec, Mar 21 2014
a(n) ~ 3^(n/2+1) * (7*sqrt(3)+12 +(-1)^n*(7*sqrt(3)-12)) / (n^(3/2)*sqrt(2*Pi)). - Vaclav Kotesovec, Mar 21 2014
A(x) = (1 + x^2*A001006(x^2))/(1 - x + x^2 - x^3*A001006(x^2)). - Gheorghe Coserea, Jan 06 2017

A274111 Number of equivalence classes of ballot paths of length n for the string ddd.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 3, 5, 7, 10, 13, 20, 28, 45, 65, 101, 143, 222, 317, 500, 726, 1143, 1661, 2608, 3796, 5983, 8764, 13835, 20335, 32089, 47251, 74637, 110227, 174302, 258095, 408276, 605664, 958551, 1424659, 2256136, 3359446, 5322449, 7937666, 12580545

Offset: 0

N. J. A. Sloane, Jun 17 2016

Gheorghe Coserea, Table of n, a(n) for n = 0..300
K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015, proposition 3.2.

Cf. A274110-A274115.

terms = 45; A[]=0; Do[A[x] = (1-2(-1+x)^2 x A[x]^2 + x^2 (-1+2x-x^2+x^4) A[x]^3)/(1-3x+x^2) + O[x]^terms, terms]; CoefficientList[A[x], x] (* Jean-François Alcover, Oct 07 2018 *)

x='x; y='y;
Fxy = x^2*(1-2*x+x^2-x^4)*y^3 + 2*x*(1-x)^2*y^2 + (1-3*x+x^2)*y - 1;
seq(N) = {
  my(y0 = 1 + O('x^N), y1=0);
  for (k = 1, N,
    y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);
    if (y1 == y0, break()); y0 = y1);
  Vec(y0);
};
seq(45)  \\ Gheorghe Coserea, Jan 05 2017

The g.f. satisfies x^2*(1-2*x+x^2-x^4)*A(x)^3 + 2*x*(1-x)^2*A(x)^2 + (1-3*x+x^2)*A(x) - 1 = 0. - R. J. Mathar, Jun 20 2016

a(0)=1 prepended by Gheorghe Coserea, Jan 05 2017

A274113 Number of equivalence classes of ballot paths of length n for the string dud.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 5, 7, 11, 16, 26, 39, 63, 95, 154, 235, 381, 585, 948, 1464, 2373, 3682, 5967, 9293, 15060, 23531, 38131, 59741, 96801, 152020, 246310, 387611, 627985, 990027, 1603893, 2532609, 4102726, 6487600, 10509114, 16639214, 26952186, 42722941, 69199472

Offset: 0

N. J. A. Sloane, Jun 17 2016

Gheorghe Coserea, Table of n, a(n) for n = 0..300
K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015, proposition 3.6.

Cf. A274110, A274111, A274112, A274114, A274115.

terms = 43; y[] = 0; Do[y[x] = (-1+x^2-x^4+(2x-3x^2-2x^3+2x^4+2x^5-2x^6) y[x]^2 + (x^2-x^3-x^4) y[x]^3)/(-1+3x+x^2-3x^3-x^4+ x^5) + O[x]^terms, terms]; CoefficientList[y[x], x] (* Jean-François Alcover, Oct 07 2018 *)

x='x; y='y;
Fxy = x^2*(1-x-x^2)*y^3 + 2*x*(1-3/2*x-x^2+x^3+x^4-x^5)*y^2 + (1-3*x-x^2+3*x^3+x^4-3*x^5)*y - 1+x^2-x^4;
seq(N) = {
  my(y0 = 1 + O('x^N), y1=0);
  for (k = 1, N,
    y1 = y0 - subst(Fxy, y, y0)/subst(deriv(Fxy, y), y, y0);
    if (y1 == y0, break()); y0 = y1);
  Vec(y0);
};
seq(43)  \\ Gheorghe Coserea, Jan 05 2017

G.f. y satisfies: 0 = x^2*(1-x-x^2)*y^3 + 2*x*(1-3/2*x-x^2+x^3+x^4-x^5)*y^2 + (1-3*x-x^2+3*x^3+x^4-3*x^5)*y - 1+x^2-x^4. - Gheorghe Coserea, Jan 05 2017

a(0)=1 prepended by Gheorghe Coserea, Jan 05 2017

A317639 Number of equivalence classes of Dyck paths of semilength n for the consecutive pattern UDUDD, where U=(1,1) and D=(1,-1).

Original entry on oeis.org

1, 1, 1, 2, 4, 6, 10, 19, 32, 54, 98, 170, 292, 520, 909, 1577, 2787, 4883, 8515, 14998, 26299, 45984, 80863, 141844, 248381, 436406, 765649, 1341844, 2356500, 4134749, 7249981, 12728630, 22335110, 39174776, 68766785, 120670190, 211689586, 371558266, 652014636

Offset: 0

Alois P. Heinz, Aug 02 2018

nonn

Two Dyck paths of the same length are equivalent with respect to a given pattern if they have equal sets of occurrences of this pattern.

Alois P. Heinz, Table of n, a(n) for n = 0..4096
J.-L. Baril, A. Petrossian, Equivalence classes of Dyck paths modulo some statistics, 2014.
J.-L. Baril, A. Petrossian, Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two, J. Int. Seq. 18 (2015) 15.7.1
K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.
Wikipedia, Counting lattice paths

Cf. A000108, A001519, A177528, A244885, A244886, A274114, A274115, A274289.

b:= proc(x, y) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
     `if`(y=0, b(x-2, y)+b(x-6, y+2), b(x-1, y-1))+b(x-5, y+1)))
    end:
a:= n-> b(2*n, 0):
seq(a(n), n=0..42);

b[x_, y_] := b[x, y] = If[y < 0 || y > x, 0, If[x == 0, 1, If[y == 0, b[x - 2, y] + b[x - 6, y + 2], b[x - 1, y - 1]] + b[x - 5, y + 1]]];
a[n_] := b[2n, 0];
Table[a[n], {n, 0, 42}] (* Jean-François Alcover, Aug 20 2018, from Maple *)

A274289 Number of equivalence classes of Dyck paths of semilength n for the string udu.

Original entry on oeis.org

1, 1, 2, 4, 9, 22, 54, 134, 335, 843, 2132, 5409, 13761, 35088, 89638, 229361, 587678, 1507586, 3871589, 9952087, 25604573, 65927447, 169875992, 438016016, 1130103976, 2917412699, 7535482753, 19473430909, 50347508572, 130228143004, 336985674038

Offset: 0

N. J. A. Sloane, Jun 17 2016

nonn

K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.

Cf. A274114, A274115.

G := 1 ;
T := 1 ;
for t from 1 to 40 do
    G := x*(1+G)+x^2*(1+x*G)*(1+x*(1+x*G))*G ;
    G := taylor(G,x=0,t+1) ;
    G := convert(G,polynom) ;
    T := (-x^2-x^3*T^3-x^2*T^2)/(x-1) ;
    T := taylor(T,x=0,t+1) ;
    T := convert(T,polynom) ;
    F := (x*(1-x)^2*(1+G+x*G)+x^5*(1+x*G)*G^2)/(1-x)/((1-x)^2+(x-2)*x^2*G)
               -x^4*(1-x+x^3)*(1+x*G)*G*T/(1-x)^2/(1-x+x^3-x*T) ;
    F := taylor(F,x=0,t+1) ;
    F := convert(F,polynom) ;
    for i from 0 to t do
        printf("%d,",coeff(F,x,i)) ;
    od;
    print();
end do: # R. J. Mathar, Jun 21 2016

G = 1; T = 1;
For[ t = 1 , t <= 40, t++,
G = x*(1 + G) + x^2*(1 + x*G)*(1 + x*(1 + x*G))*G + O[x]^(t+1) // Normal;
T = (-x^2 - x^3*T^3 - x^2*T^2)/(x - 1) + O[x]^(t+1) // Normal;
F = 1 + (x*(1 - x)^2*(1 + G + x*G) + x^5*(1 + x*G)*G^2)/(1 - x)/((1 - x)^2 + (x - 2)*x^2*G) - x^4*(1 - x + x^3)*(1 + x*G)*G*T/(1 - x)^2/(1 - x + x^3 - x*T) + O[x]^(t+1) // Normal;
];
CoefficientList[F, x] (* Jean-François Alcover, Jul 27 2018, after R. J. Mathar *)

a(0)=1 prepended by Alois P. Heinz, Jul 27 2018

A306405 T(n,k) = kSum_{i=0..(n-k)/2} C(k,2k+2i-n)C(k+2*i-1,i)/(k+i), triangle read by rows for n >= 1 and 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 2, 4, 6, 4, 1, 2, 7, 10, 10, 5, 1, 5, 10, 18, 20, 15, 6, 1, 5, 19, 30, 39, 35, 21, 7, 1, 14, 28, 55, 72, 75, 56, 28, 8, 1, 14, 56, 93, 136, 151, 132, 84, 36, 9, 1, 42, 84, 174, 248, 300, 288, 217, 120, 45, 10, 1

Offset: 1

Vladimir Kruchinin, Feb 13 2019

			    1;
    1,  1;
    1,  2,  1;
    1,  3,  3,  1;
    2,  4,  6,  4,  1;
    2,  7, 10, 10,  5, 1;
    5, 10, 18, 20, 15, 6, 1;

Cf. A000108, A274115.

# Seen as a (0,0)-based triangle:
gf := (2*(x + 1))/(sqrt(1 - 4*x^2) - 2*x*(x + 1)*y + 1):
serx := series(gf, x, 20): sery := n -> series(coeff(serx, x, n), y, 20):
row := n -> seq(coeff(sery(n), y, j), j=0..n):
seq(lprint(row(n)), n=0..9); # Peter Luschny, Feb 14 2019

T(n,k):=k*sum((binomial(k,2*k+2*i-n)*binomial(k+2*i-1,i))/(k+i),i,0,(n-k)/2);

G.f.: 1/(1-y*(x*(1+x)*(1-sqrt(1-4*x^2))/(2*x^2)))-1.

A369436 Number of 2-Motzkin meanders with catastrophes of length n.

Original entry on oeis.org

1, 3, 10, 36, 136, 529, 2095, 8393, 33885, 137547, 560544, 2291181, 9386584, 38525224, 158350133, 651645511, 2684323326, 11066714500, 45656997415, 188475894929, 778444106703, 3216562337420, 13296099775859, 54979806370840, 227410731720624, 940875886301665

Offset: 0

Florian Schager, Jan 23 2024

A 2-Motzkin meander is a lattice path that does not go below the x-axis. with steps U = (1,1), D = (1,-1) and two copies R = (1,0) and B = (1,0), i.e. red and blue level steps.

A catastrophe is a step C = (1,-k) from altitude k to altitude 0 for k > 1.

			For n = 2 the a(2) = 10 solutions are UU, UR, UB, UD, RU, RR, RB, BU, BR, BB.
For n = 3 the a(3) = 36 solutions are UUU, UUR, UUB, UUD, UUC, URU, URR, URB, URD, UBU, UBR, UBB, UBD, UDU, UDR, UDB, RUU, RUR, RUB, RUD, RRU, RRR, RRB, RBU, RBR, RBB, BUU, BUR, BUB, BUD, BRU, BRR, BRB, BBU, BBR, BBB.

Cyril Banderier and Michael Wallner, Lattice paths with catastrophes, arXiv:1707.01931 [math.CO], 2017.

Cf. A274115 (Dyck meanders).

Cf. A054391 (Motzkin meanders).

K := 1 - z*(1/u + 2 + u);
u1 := solve(K, u)[2];
M := (1 - u1)/(1 - 4*z);
E := u1/z;
M1 := z*E^2;Q := z*(M - E - M1);
series(M/(1 - Q), z, 30);

my(N=44,z='z+O('z^N),S=sqrt(1-4*z)); Vec((1 - 4*z - S)*z/(5*S*z^2 + 12*z^3 - 5*z*S - 15*z^2 + S + 7*z - 1))

G.f.: (1 - 4*z - sqrt(1 - 4*z))*z/(5*sqrt(1 - 4*z)*z^2 + 12*z^3 - 5*z*sqrt(-4*z + 1) - 15*z^2 + sqrt(-4*z + 1) + 7*z - 1).

D-finite with recurrence n*a(n) +4*(-3*n+2)*a(n-1) +(53*n-70)*a(n-2) +(-107*n+210)*a(n-3) +(101*n-268)*a(n-4) +18*(-2*n+7)*a(n-5)=0. - R. J. Mathar, Jan 28 2024

cp's OEIS Frontend

A274114 Number of equivalence classes of Dyck paths of semilength n for the string uuu.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A274112 Number of equivalence classes of ballot paths of length n for the string ddu.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A191385 Number of dispersed Dyck paths of length n having no ascents of length 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A274111 Number of equivalence classes of ballot paths of length n for the string ddd.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A274113 Number of equivalence classes of ballot paths of length n for the string dud.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A317639 Number of equivalence classes of Dyck paths of semilength n for the consecutive pattern UDUDD, where U=(1,1) and D=(1,-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A274289 Number of equivalence classes of Dyck paths of semilength n for the string udu.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A306405 T(n,k) = k*Sum_{i=0..(n-k)/2} C(k,2*k+2*i-n)*C(k+2*i-1,i)/(k+i), triangle read by rows for n >= 1 and 1 <= k <= n.

A306405 T(n,k) = kSum_{i=0..(n-k)/2} C(k,2k+2i-n)C(k+2*i-1,i)/(k+i), triangle read by rows for n >= 1 and 1 <= k <= n.