A025246 -id:A025246 - cp's OEIS frontend

A023431 Generalized Catalan Numbers x^3A(x)^2 + (x-1)A(x) + 1 =0.

1, 1, 1, 2, 4, 7, 13, 26, 52, 104, 212, 438, 910, 1903, 4009, 8494, 18080, 38656, 82988, 178802, 386490, 837928, 1821664, 3970282, 8673258, 18987930, 41652382, 91539466, 201525238, 444379907, 981384125, 2170416738, 4806513660

Offset: 0

Olivier Gérard

Essentially the same as A025246.
Number of lattice paths in the first quadrant from (0,0) to (n,0) using only steps H=(1,0), U=(1,1) and D=(2,-1). E.g. a(5)=7 because we have HHHHH, HHUD, HUDH, HUHD, UDHH, UHDH and UHHD. - Emeric Deutsch, Dec 25 2003
Also number of peakless Motzkin paths of length n with no double rises; in other words, Motzkin paths of length n with no UD's and no UU's, where U=(1,1) and D=(1,-1). E.g. a(5)=7 because we have HHHHH, HHUHD, HUHDH, HUHHD, UHDHH, UHHDH and UHHHD, where H=(1,0). - Emeric Deutsch, Jan 09 2004
Series reversion of g.f. A(x) is -A(-x) (if offset 1). - Michael Somos, Jul 13 2003
Hankel transform is A010892(n+1). [From Paul Barry, Sep 19 2008]
Number of FU_{k}-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths. This also works for U_{k}F-equivalence classes. - Sergey Kirgizov, Apr 08 2018

			G.f. = 1 + x + x^2 + 2*x^3 + 4*x^4 + 7*x^5 + 13*x^6 + 26*x^7 + 52*x^8 + 104*x^9 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.
Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.
Paul Barry, Elliptic Curves, Riordan arrays and Lattice Paths, arXiv:2507.16765 [math.CO], 2025. See p. 16.
Johann Cigler, Some nice Hankel determinants, arXiv preprint arXiv:1109.1449 [math.CO], 2011.
Shalosh B. Ekhad and Mingjia Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 666
Feihu Liu, Ying Wang, Yingrui Zhang, and Zihao Zhang, Hankel Determinants for Convolution of Power Series: An Extension of Cigler's Results, arXiv:2503.17187 [math.CO], 2025. See p. 9.
K. Park and G.-S. Cheon, Lattice path counting with a bounded strip restriction
Helmut Prodinger, Motzkin paths of bounded height with two forbidden contiguous subwords of length two, arXiv:2310.12497 [math.CO], 2023.

Cf. A000108, A001006, A004148, A006318, A025246.

Cf. A014137, A090344, A144700.

a023431 n = a023431_list !! n
a023431_list = 1 : 1 : f [1,1] where
   f xs'@(x:_:xs) = y : f (y : xs') where
     y = x + sum (zipWith (*) xs $ reverse $ xs')
-- Reinhard Zumkeller, Nov 13 2012

[(&+[Binomial(n-k, 2*k)*Catalan(k): k in [0..Floor(n/3)]]): n in [0..40]]; // G. C. Greubel, Jun 15 2022

a := n -> hypergeom([1/3 - n/3, 2/3 - n/3, -n/3], [2, -n], 27):
seq(simplify(a(n)), n = 0..32); # Peter Luschny, Jun 15 2022

a[0]=1; a[n_]:= a[n]= a[n-1] + Sum[a[k]*a[n-3-k], {k, 0, n-3}];
Table[a[n], {n,0,40}]

{a(n) = polcoeff( (1 - x - sqrt((1-x)^2 - 4*x^3 + x^4 * O(x^n))) / 2, n+3)}; /* Michael Somos, Jul 13 2003 */

[sum(binomial(n-k,2*k)*catalan_number(k) for k in (0..(n//3))) for n in (0..40)] # G. C. Greubel, Jun 15 2022

G.f.: (1 - x - sqrt((1-x)^2 - 4*x^3)) / (2*x^3) = A(x). y = x * A(x) satisfies 0 = x - y + x*y + (x*y)^2. - Michael Somos, Jul 13 2003
a(n+1) = a(n) + a(0)*a(n-2) + a(1)*a(n-3) + ... + a(n-2)*a(0). - Michael Somos, Jul 13 2003
a(n) = A025246(n+3). - Michael Somos, Jan 20 2004
G.f.: (1/(1-x))*c(x^3/(1-x)^2), c(x) the g.f. of A000108. - From Paul Barry, Sep 19 2008
From Paul Barry, May 22 2009: (Start)
G.f.: 1/(1-x-x^3/(1-x-x^3/(1-x-x^3/(1-x-x^3/(1-... (continued fraction).
a(n) = Sum_{k=0..floor(n/3)} binomial(n-k, 2*k)*A000108(k). (End)
(n+3)*a(n) = (2*n+3)*a(n-1) - n*a(n-2) + 2*(2*n-3)*a(n-3). - R. J. Mathar, Nov 26 2012
0 = a(n)*(16*a(n+1) - 10*a(n+2) + 32*a(n+3) - 22*a(n+4)) + a(n+1)*(2*a(n+1) - 15*a(n+2) + 9*a(n+3) + 4*a(n+4)) + a(n+2)*(a(n+2) + 2*a(n+3) - 5*a(n+4)) + a(n+3)*(a(n+3) + a(n+4)) if n>=0. - Michael Somos, Jan 30 2014
a(n) ~ (8 + 12*r^2 + 5*r) * sqrt(r^2 - 4*r + 3) / (4 * sqrt(Pi) * n^(3/2) * r^n), where r = 0.432040800333095789... is the real root of the equation -1 + 2*r - r^2 + 4*r^3 = 0. - Vaclav Kotesovec, Jun 15 2022
a(n) = hypergeom([(1 - n)/3, (2 - n)/3, -n/3], [2, -n], 27). - Peter Luschny, Jun 15 2022

A357308 a(0) = a(1) = 0, a(2) = 1; a(n) = a(n-1) + Sum_{k=0..n-3} a(k) * a(n-k-3).

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 1, 2, 4, 7, 11, 16, 24, 39, 67, 116, 196, 324, 534, 892, 1516, 2601, 4463, 7630, 13022, 22276, 38286, 66084, 114328, 197929, 342783, 594218, 1031794, 1794944, 3127450, 5455272, 9523812, 16640542, 29102938, 50951070, 89289998, 156616648, 274923328, 482945930, 848972814

Offset: 0

Ilya Gutkovskiy, Sep 23 2022

nonn

Cf. A006318, A023426, A023431, A025246, A346503, A346504, A357307.

a[0] = a[1] = 0; a[2] = 1; a[n_] := a[n] = a[n - 1] + Sum[a[k] a[n - k - 3], {k, 0, n - 3}]; Table[a[n], {n, 0, 44}]
nmax = 44; A[] = 0; Do[A[x] = x^2 (1 + x A[x]^2)/(1 - x) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

G.f. A(x) satisfies: A(x) = x^2 * (1 + x * A(x)^2) / (1 - x).

A365698 G.f. satisfies A(x) = 1 + x^5 / (1 - x*A(x)).

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 4, 7, 11, 16, 22, 31, 47, 76, 126, 207, 331, 517, 801, 1251, 1987, 3206, 5212, 8465, 13677, 21997, 35341, 56937, 92169, 149860, 244274, 398383, 649379, 1058055, 1724575, 2814475, 4600923, 7533150, 12347908, 20252837, 33230545

Offset: 0

Seiichi Manyama, Sep 16 2023

nonn

Cf. A212364, A365699, A365700, A365701, A365702.

Cf. A001006, A023426, A025246, A357308.

a(n) = sum(k=0, n\5, binomial(n-4*k-1, n-5*k)*binomial(n-5*k+1, k)/(n-5*k+1));

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

a(n) = Sum_{k=0..floor(n/5)} binomial(n-4*k-1,n-5*k) * binomial(n-5*k+1,k) / (n-5*k+1).

A365690 G.f. satisfies A(x) = 1 + x^2A(x)^4 / (1 - xA(x)).

Original entry on oeis.org

1, 0, 1, 1, 5, 10, 38, 101, 353, 1070, 3659, 11843, 40505, 135873, 468104, 1604375, 5576315, 19386656, 67950717, 238676813, 842797959, 2983745508, 10603445402, 37777263153, 134985354179, 483438728094, 1735527037388, 6243193190117, 22503637842423

Offset: 0

Seiichi Manyama, Sep 16 2023

nonn

Cf. A004148, A005043, A025246, A046736, A365691.

Cf. A365692.

a(n) = sum(k=0, n\2, binomial(n-k-1, n-2*k)*binomial(n+2*k+1, k)/(n+2*k+1));

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

A365691 G.f. satisfies A(x) = 1 + x^2A(x)^5 / (1 - xA(x)).

Original entry on oeis.org

1, 0, 1, 1, 6, 12, 54, 147, 593, 1886, 7292, 25204, 96153, 348304, 1327716, 4946471, 18936366, 71827598, 276612103, 1062220253, 4115807184, 15947902376, 62148513732, 242485933208, 949828266722, 3726623622402, 14663689944397, 57798199213989

Offset: 0

Seiichi Manyama, Sep 16 2023

nonn

Cf. A004148, A005043, A025246, A046736, A365690.

Cf. A365693.

a(n) = sum(k=0, n\2, binomial(n-k-1, n-2*k)*binomial(n+3*k+1, k)/(n+3*k+1));

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

A276066 Triangle read by rows: T(n,k) is the number of bargraphs of semiperimeter n having a total of k double rises and double falls (n>=2,k>=0). A double rise (fall) in a bargraph is any pair of adjacent up (down) steps.

Original entry on oeis.org

1, 1, 0, 1, 1, 2, 1, 0, 1, 2, 4, 1, 4, 1, 0, 1, 4, 6, 8, 8, 1, 6, 1, 0, 1, 7, 14, 22, 12, 19, 12, 1, 8, 1, 0, 1, 13, 34, 43, 48, 55, 18, 35, 16, 1, 10, 1, 0, 1, 26, 72, 105, 148, 109, 116, 103, 24, 56, 20, 1, 12, 1, 0, 1, 52, 154, 276, 344, 347, 398, 205, 232, 166, 30, 82, 24, 1, 14, 1, 0, 1

Offset: 2

Emeric Deutsch and Sergi Elizalde, Aug 25 2016

Number of entries in row n is 2n-3.
Sum of entries in row n = A082582(n).
T(n,0) = A023431(n-2) = A025246(n+1).
Sum(k*T(n,k),k>=0) = 2*A273714(n).

			Row 4 is 1,2,1,0,1 because the 5 (=A082582(4)) bargraphs of semiperimeter 4 correspond to the compositions [1,1,1], [1,2], [2,1], [2,2], [3] and the corresponding drawings show that they have a total of  0, 1, 1, 2, 4 double rises and double falls, respectively.
Triangle starts:
1;
1,0,1;
1,2,1,0,1;
2,4,1,4,1,0,1;
4,6,8,8,1,6,1,0,1.

Alois P. Heinz, Rows n = 2..140, flattened
M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.
Emeric Deutsch, S Elizalde, Statistics on bargraphs viewed as cornerless Motzkin paths, arXiv preprint arXiv:1609.00088, 2016

Cf. A023431, A025246, A082582, A273714.

eq := z*G^2-(1-z-t^2*z-2*t*z^2+t^2*z^2)*G+z^2 = 0: G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 22)): for n from 2 to 20 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 2 to 20 do seq(coeff(P[n], t, j), j = 0 .. 2*n-4) end do; # yields sequence in triangular form.
# second Maple program:
b:= proc(n, y, t) option remember; expand(`if`(n=0, (1-t)*
      z^(y-1), `if`(t<0, 0, b(n-1, y+1, 1)*`if`(t=1, z, 1))+
     `if`(t>0 or y<2, 0, b(n, y-1, -1)*`if`(t=-1, z, 1))+
     `if`(y<1, 0, b(n-1, y, 0))))
    end:
T:= n->(p->seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=2..12);  # Alois P. Heinz, Aug 25 2016

b[n_, y_, t_] := b[n, y, t] = Expand[If[n == 0, (1 - t)*z^(y - 1), If[t < 0, 0, b[n - 1, y + 1, 1]*If[t == 1, z, 1]] + If[t > 0 || y < 2, 0, b[n, y - 1, -1]*If[t == -1, z, 1]] + If[y < 1, 0, b[n - 1, y, 0]]]]; T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[n, 0, 0]]; Table[T[n], {n, 2, 12}] // Flatten (* Jean-François Alcover, Dec 02 2016 after Alois P. Heinz *)

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

The g.f. B(t,s,z) of bargraphs, where t(s) marks double rises (falls) and z marks semiperimeter, satisfies zB^2 - (1-(1+ts)z +(ts- t-s)z^2)B + z^2 = 0.

cp's OEIS Frontend

A023431 Generalized Catalan Numbers x^3*A(x)^2 + (x-1)*A(x) + 1 =0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

A357308 a(0) = a(1) = 0, a(2) = 1; a(n) = a(n-1) + Sum_{k=0..n-3} a(k) * a(n-k-3).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A365698 G.f. satisfies A(x) = 1 + x^5 / (1 - x*A(x)).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A365690 G.f. satisfies A(x) = 1 + x^2*A(x)^4 / (1 - x*A(x)).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A365691 G.f. satisfies A(x) = 1 + x^2*A(x)^5 / (1 - x*A(x)).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A276066 Triangle read by rows: T(n,k) is the number of bargraphs of semiperimeter n having a total of k double rises and double falls (n>=2,k>=0). A double rise (fall) in a bargraph is any pair of adjacent up (down) steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A023431 Generalized Catalan Numbers x^3A(x)^2 + (x-1)A(x) + 1 =0.

A365690 G.f. satisfies A(x) = 1 + x^2A(x)^4 / (1 - xA(x)).

A365691 G.f. satisfies A(x) = 1 + x^2A(x)^5 / (1 - xA(x)).