A090344 -id:A090344 - 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

A098474 Triangle read by rows, T(n,k) = C(n,k)C(2k,k)/(k+1), n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 6, 5, 1, 4, 12, 20, 14, 1, 5, 20, 50, 70, 42, 1, 6, 30, 100, 210, 252, 132, 1, 7, 42, 175, 490, 882, 924, 429, 1, 8, 56, 280, 980, 2352, 3696, 3432, 1430, 1, 9, 72, 420, 1764, 5292, 11088, 15444, 12870, 4862, 1, 10, 90, 600, 2940, 10584, 27720

Offset: 0

Paul Barry, Sep 09 2004

A Catalan scaled binomial matrix.
From Philippe Deléham, Sep 01 2005: (Start)
Table U(n,k), k >= 0, n >= 0, read by antidiagonals, begins:
  row k = 0: 1, 1,  2,   5,   14, ... is A000108
  row k = 1: 1, 2,  6,  20,   70, ... is A000984
  row k = 2: 1, 3, 12,  50,  280, ... is A007854
  row k = 3: 1, 4, 20, 104,  548, ... is A076035
  row k = 4: 1, 5, 30, 185, 1150, ... is A076036
G.f. for row k: 1/(1-(k+1)*x*C(x)) where C(x) is the g.f. = for Catalan numbers A000108.
U(n,k) = Sum_{j=0..n} A106566(n,j)*(k+1)^j. (End)
This sequence gives the coefficients (increasing powers of x) of the Jensen polynomials for the Catalan sequence A000108 of degree n and shift 0. For the definition of Jensen polynomials for a sequence see a comment in A094436. - Wolfdieter Lang, Jun 25 2019

			Rows begin:
  1;
  1, 1;
  1, 2,  2;
  1, 3,  6,   5;
  1, 4, 12,  20,  14;
  1, 5, 20,  50,  70,  42;
  1, 6, 30, 100, 210, 252, 132;
  ...
Row 3: t*(1 - 3*t + 6*t^2 - 5*t^3)/(1 - 4*t)^(9/2) = 1/2*Sum_{k >= 1} k*(k+1)*(k+2)*(k+3)/4!*binomial(2*k,k)*t^k. - _Peter Bala_, Jun 13 2016

Indranil Ghosh, Rows 0..125, flattened

Row sums are A007317.
Antidiagonal sums are A090344.
Principal diagonal is A000108.
Mirror image of A124644.
Cf. A000984, A007854, A011973, A076035, A076036, A098443, A098473, A106566, A267633.

p := proc(n) option remember; if n = 0 then 1 else normal((x*(1 + 4*x)*diff(p(n-1, x), x) + (2*x + n + 1)*p(n-1, x))/(n + 1)) fi end:
row := n -> local k; seq(coeff(p(n), x, k), k = 0..n):
for n from 0 to 6 do row(n) od;  # Peter Luschny, Jun 21 2023

Table[Binomial[n, k] Binomial[2 k, k]/(k + 1), {n, 0, 10}, {k, 0, n}] // Flatten (* or *)
Table[(-1)^k*CatalanNumber[k] Pochhammer[-n, k]/k!, {n, 0, 10}, {k, 0, n}] // Flatten (* Michael De Vlieger, Feb 17 2017 *)

from functools import cache
@cache
def A098474row(n: int) -> list[int]:
    if n == 0: return [1]
    a = A098474row(n - 1) + [0]
    row = [0] * (n + 1)
    row[0] = 1; row[1] = n
    for k in range(2, n + 1):
        row[k] = (a[k] * (n + k + 1) + a[k - 1] * (4 * k - 2)) // (n + 1)
    return row  # Peter Luschny, Jun 22 2023

def A098474(n,k):
    return (-1)^k*catalan_number(k)*rising_factorial(-n,k)/factorial(k)
for n in range(7): [A098474(n,k) for k in (0..n)] # Peter Luschny, Feb 05 2015

G.f.: 2/(1-x+(1-x-4*x*y)^(1/2)). - Vladeta Jovovic, Sep 11 2004
E.g.f.: exp(x*(1+2*y))*(BesselI(0, 2*x*y)-BesselI(1, 2*x*y)). - Vladeta Jovovic, Sep 11 2004
G.f.: 1/(1-x-xy/(1-xy/(1-x-xy/(1-xy/(1-x-xy/(1-xy/(1-x-xy/(1-xy/(1-... (continued fraction). - Paul Barry, Feb 11 2009
Sum_{k=0..n} T(n,k)*x^(n-k) = A126930(n), A005043(n), A000108(n), A007317(n+1), A064613(n), A104455(n) for x = -2, -1, 0, 1, 2, 3 respectively. - Philippe Deléham, Dec 12 2009
T(n,k) = (-1)^k*Catalan(k)*Pochhammer(-n,k)/k!. - Peter Luschny, Feb 05 2015
O.g.f.: [1 - sqrt(1-4tx/(1-x))]/(2tx) = 1 + (1+t) x + (1+2t+2t^2) x^2 + (1+3t+6t^2+5t^3) x^3 + ... , generating the polynomials of this entry, reverse of A124644. See A011973 for a derivation and the inverse o.g.f., connected to the Fibonacci, Chebyshev, and Motzkin polynomials. See also A267633. - Tom Copeland, Jan 25 2016
From Peter Bala, Jun 13 2016: (Start)
The o.g.f. F(x,t) = ( 1 - sqrt(1 - 4*t*x/(1 - x)) )/(2*t*x) satisfies the partial differential equation d/dx(x*(1 - x)*F) - x*t*(1 + 4*t)*dF/dt - 2*x*t*F = 1. This gives a recurrence for the row polynomials: (n + 2)*R(n+1,t) = t*(1 + 4*t)*R'(n,t) + (2*t + n + 2)*R(n,t), where the prime ' indicates differentiation with respect to t.
Equivalently, setting Q(n,t) = t^(n+2)*R(n,-t)/(1 - 4*t)^(n + 3/2) we have t^2*d/dt(Q(n,t)) = (n + 2)*Q(n+1,t).
This leads to the following expansions:
Q(0,t) = (1/2)*Sum_{k >= 1} k*binomial(2*k,k)*t^(k+1)
Q(1,t) = (1/2)*Sum_{k >= 1} k*(k+1)/2!*binomial(2*k,k)*t^(k+2)
Q(2,t) = (1/2)*Sum_{k >= 1} k*(k+1)*(k+2)/3!*binomial(2*k,k) *t^(k+3) and so on. (End)
Sum_{k=0..n} T(n,k)*x^k = A007317(n+1), A162326(n+1), A337167(n) for x = 1, 2, 3 respectively. - Sergii Voloshyn, Mar 31 2022

New name using a formula of Paul Barry by Peter Luschny, Feb 05 2015

A090345 Number of Motzkin paths of length n with no level steps at even level.

Original entry on oeis.org

1, 0, 1, 1, 3, 5, 12, 24, 55, 119, 272, 612, 1411, 3247, 7565, 17667, 41561, 98099, 232696, 553784, 1322813, 3169065, 7614583, 18342921, 44294991, 107200829, 259983346, 631718606, 1537737567, 3749440151, 9156561590, 22394270034, 54845701243, 134497468359

Offset: 0

Emeric Deutsch, Jan 28 2004

nonn

Hankel transform of a(n) is A000012. Hankel transform of a(n+1) is 0,-1,0,1,0,-1,0,... or -[x^n](x/(1+x^2)). Hankel transform of a(n+2) is A008619(n+1). - Paul Barry, Mar 23 2011

Number of lattice paths, never going below the x-axis, from (0,0) to (n,0) consisting of up steps U(k) = (k,1) for every positive integer k and down steps D = (1,-1). For instance, for n=5, we have the 5 paths: U(4)D, U(2)U(1)DD, U(1)U(2)DD, U(2)DU(1)D, U(1)DU(2)D. - José Luis Ramírez Ramírez, Apr 19 2015

			a(5)=5 because we have UHDUD, UDUHD, UHUDD, UUDHD and UHHHD, where U=(1,1), D=(1,-1) and H=(1,0).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
David Callan, Some bijections for lattice paths, arXiv:2112.05241 [math.CO], 2021.
Emeric Deutsch, Emanuele Munarini and Simone Rinaldi, Skew Dyck paths, area, and superdiagonal bargraphs, Journal of Statistical Planning and Inference, Vol. 140, Issue 6, June 2010, pp. 1550-1562.

Cf. A001006.

First differences of A090344.

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

G.f.: (1 - z - sqrt(1 - 2*z - 3*z^2 + 4*z^3))/(2*z^2).
G.f. A(x) satisfies A(x) = A(x/(x-1)). - Vladeta Jovovic, Jul 07 2004
Also (x*A)^2 = (1-x)*(A-1). - Vladeta Jovovic, Jul 07 2004
G.f.: 1/(1-x^2/(1-x-x^2/(1-x^2/(1-x-x^2/(1-x^2/(1-x-x^2/(1-... (continued fraction). - Paul Barry, Apr 08 2009
G.f.: 1/(1-z/(1-z/(1-z/(...)))) where z=x^2/(1-x) (continued fraction); in other words, g.f.: C(x^2/(1-x)) where C(x) is the g.f. for the Catalan numbers (A000108). - Joerg Arndt, Mar 18 2011
a(0) = 1, a(n) = Sum_{k=0..floor(n/2)} (k/(n-k))*binomial(n-k,k)*A000108(k). - Paul Barry, Jul 01 2009
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k-1, n-2k)*A000108(k). - Paul Barry, Mar 23 2011
The sequence starting with offset 1 = iterates of M*V, leftmost column. M = an infinite tridiagonal matrix with all 1's in the sub and superdiagonals and [0,1,0,1,0,1,0,1,...] as the main diagonal; and the rest zeros. V = vector [1,0,0,0,...]. - Gary W. Adamson, Jun 08 2011
D-finite with recurrence (n+2)*a(n) + (-2*n-1)*a(n-1) + 3*(-n+1)*a(n-2) + 2*(2*n-5)*a(n-3) = 0. - R. J. Mathar, Nov 24 2012
a(n) ~ sqrt(34+2*sqrt(17)) * ((1+sqrt(17))/2)^n / (4 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 12 2014
a(0) = 1, a(1) = 0; a(n) = a(n-1) + Sum_{k=0..n-2} a(k) * a(n-k-2). - Ilya Gutkovskiy, Jul 20 2021

A332602 Tridiagonal matrix M read by antidiagonals: main diagonal is 1,2,2,2,2,..., two adjacent diagonals are 1,1,1,1,1,...

Original entry on oeis.org

1, 1, 1, 0, 2, 0, 0, 1, 1, 0, 0, 0, 2, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane, Mar 06 2020, following a suggestion from Gary W. Adamson

From Gary W. Adamson, Mar 11 2020: (Start)
The upper left entry of M^n gives the Catalan numbers A000108. Extracting 2 X 2, 3 X 3, and 4 X 4 submatrices from M; then generating sequences from the upper left entries of M^n, we obtain the following sequences:
1, 1, 2, 5, 13, ... = A001519 and the convergent is 2.61803... = 2 + 2*cos(2*Pi/5) = (2*cos(Pi/5))^2.
1, 1, 2, 5, 14, 42, 131, ... = A080937 and the convergent is 3.24697... = 2 + 2*cos(2*Pi/7) = (2*cos(Pi/7))^2.
1, 1, 2, 5, 14, 42, 132, 429, 1429, ... = A080938 and the convergent is 3.53208... = 2 + 2*cos(2*Pi/9) = (2*cos(Pi/9))^2. (End)
The characteristic polynomial for the N X N main submatrix M_N is Phi(N, x) = S(N, 2-x) - S(N-1, 2-x), with Chebyshev's S polynomial (see A049310) evaluated at 2-x. Proof by determinant expansion, to obtain the recurrence Phi(N, x) - (x-2)*Phi(N-1, x) - Phi(N-2, x), for N >= 2, and Phi(0, x) = 1 and Phi(1, x) = 1 - x, that is Phi(-1, x) = 1. The trace is tr(M_N) = 1 + 2^(N-1) = A000051(N-1), and Det(M_N) = 1. - Wolfdieter Lang, Mar 13 2020
The explicit form of the characteristic polynomial for the N X N main submatrix M_N is Phi(N, x) := Det(M_N - x*1_N) = Sum_{k=0..N} binomial(N+k, 2*k)*(-x)^k = Sum_{k=0..N} A085478(N, k)*(-x)^k, for N >= 0, with Phi(0, x) := 1. Proof from the recurrence given in the preceding comment. - Wolfdieter Lang, Mar 25 2020
For the proofs of the 2 X 2, 3 X 3 and 4 X 4 conjectures, see the comments in the respective A-numbers A001519, A080937 and A080938. - Wolfdieter Lang, Mar 30 2020
Replace the main diagonal 1,2,2,2,... of the matrix M with 1,0,0,0,...; 1,1,1,1,...; 1,3,3,3,...; 1,2,1,2,...; 1,2,3,4,...; 1,0,1,0...; and 1,1,0,0,1,1,0,0,.... Take powers of M and extract the upper left terms, resulting in respectively: A001405, A001006, A033321, A176677, A006789, A090344, and A007902. - Gary W. Adamson, Apr 12 2022
The statement that the upper left entry of M^n is a Catalan number is equivalent to Exercise 41 of R. Stanley, "Catalan Numbers." - Richard Stanley, Feb 28 2023
If the upper left 1 in matrix M is replaced with 3, taking powers of the resulting matrix and extracting the upper left terms apparently results in sequence A001700. - Gary W. Adamson, Apr 03 2023

			The matrix begins:
  1, 1, 0, 0, 0, ...
  1, 2, 1, 0, 0, ...
  0, 1, 2, 1, 0, ...
  0, 0, 1, 2, 1, ...
  0, 0, 0, 1, 2, ...
  ...
The first few antidiagonals are:
  1;
  1, 1;
  0, 2, 0;
  0, 1, 1, 0;
  0, 0, 2, 0, 0;
  0, 0, 1, 1, 0, 0;
  0, 0, 0, 2, 0, 0, 0;
  0, 0, 0, 1, 1, 0, 0, 0;
  0, 0, 0, 0, 2, 0, 0, 0, 0;
  0, 0, 0, 0, 1, 1, 0, 0, 0, 0;
  ...
Characteristic polynomial of the 3 X 3 matrix M_3: Phi(3, x) = 1 - 6*x + 5*x^2 - x^3, from {A085478(3, k)}_{k=0..3} = {1, 6, 5, 1}. - _Wolfdieter Lang_, Mar 25 2020

Richard P. Stanley, "Catalan Numbers", Cambridge University Press, 2015.

Cf. A000108, A000051, A001519, A049310, A080937, A080938, A085478.
Cf. A001006, A001405, A006789, A033321, A176677, A090344, A007902.
Cf. A001333 (permanent of the matrix M).
Cf. A054142, A053123, A011973 (characteristic polynomials of submatrices of M).
Cf. A001700.

A039982 Let phi denote the morphism 0 -> 11, 1 -> 10. This sequence is the limit S(oo) where S(0) = 1; S(n+1) = 1.phi(S(n)).

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0

Offset: 0

N. J. A. Sloane

An example of a d-perfect sequence.
Concatenation of the bit sequences 1, 10, 1011, 10111010, 1011101010111011, ... used in a construction of A035263 (see Comment there by Benoit Cloitre). - David Callan, Oct 08 2005
Image, under the coding a,b,d -> 1, c -> 0, of the fixed point, starting with a, of the morphism a -> ab, b -> cd, c -> cd, d -> bb. - Jeffrey Shallit, May 15 2016

			The first few S(i) are:
S(0) = 1
S(1) = 1.10 = 110
S(2) = 1.101011 = 1101011
S(3) = 1.10101110111010 = 110101110111010
...

Antti Karttunen, Table of n, a(n) for n = 0..65537
Martin Klazar and Florian Luca, On integrality and periodicity of the Motzkin numbers.
Martin Klazar and Florian Luca, On integrality and periodicity of the Motzkin numbers, Aequationes Math. 69 (2005), no. 1-2, 68-75.
D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions
D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions, Sequences and their Applications, Discrete Mathematics and Theoretical Computer Science 1999, pp 308-317.
Index entries for characteristic functions

Cf. A001006, A035263, A090344, A091090.

b:=[1,1,2];; for n in [4..120] do b[n]:=(1/(n+1))* (2*n*b[n-1]+(3*n-7)*b[n-2]-(4*n-10)*b[n-3]);; od; a:=b mod 2; # Muniru A Asiru, Sep 28 2018

substitutionRule={1->{1, 0}, 0->{1, 1}}; makeSubstitution[seq_]:=Flatten[seq/.substitutionRule]; Flatten[NestList[makeSubstitution, {1}, 5]]
NestList[Flatten[ # /. {0 -> {1, 1}, 1 -> {1, 0}}] &, {1}, 6] // Flatten (* Robert G. Wilson v, Mar 29 2006 *)

a(n)=my(A=1+x); for(i=1, n, A=1/(1-x+x*O(x^n))+x^2*A^2+x*O(x^n)); polcoeff(A, n)%2 \\ Charles R Greathouse IV, Feb 04 2013

up_to = 16384;
A090344list(up_to) = { my(v=vector(up_to)); v[1] = 1; v[2] = 2; v[3] = 3; for(n=4,up_to,v[n] = ((2*n+2)*v[n-1] -(4*n-6)*v[n-3] +(3*n-4)*v[n-2])/(n+2)); (v); };
v090344 = A090344list(up_to);
A090344(n) = if(!n,1,v090344[n]);
A039982(n) = (A090344(n)%2); \\ Antti Karttunen, Sep 27 2018

a(n) = A090344(n) mod 2. - Christian G. Bower, Jun 12 2005

a(n) = A091090(n+1) mod 2. - Alan Michael Gómez Calderón, Jul 05 2025

More terms from Christian G. Bower, Jun 12 2005
Offset corrected from 1 to 0 by Antti Karttunen, Sep 27 2018
Entry revised by N. J. A. Sloane, Feb 23 2019

A346073 a(n) = 1 + Sum_{k=0..n-4} a(k) * a(n-k-4).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 5, 8, 13, 20, 29, 45, 73, 118, 185, 293, 475, 778, 1263, 2047, 3345, 5512, 9085, 14957, 24683, 40918, 67987, 113016, 188053, 313608, 524041, 876657, 1467797, 2460644, 4130893, 6942726, 11678687, 19663068, 33139295, 55904339, 94384167, 159470488

Offset: 0

Ilya Gutkovskiy, Jul 04 2021

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A000108, A007317, A090344, A216604, A307971, A346074.

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

a(n) = sum(k=0, n\4, binomial(n-3*k, k)*binomial(2*k, k)/(k+1)); \\ Seiichi Manyama, Jan 22 2023

@CachedFunction
def a(n): # a = A346073
    if (n<4): return 1
    else: return 1 + sum(a(k)*a(n-k-4) for k in range(n-3))
[a(n) for n in range(51)] # G. C. Greubel, Nov 26 2022

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

a(n) = Sum_{k=0..floor(n/4)} binomial(n-3*k,k) * Catalan(k). - Seiichi Manyama, Jan 22 2023

A124497 Number of 1-2-3 trees with n edges and with thinning limbs.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 48, 116, 288, 724, 1849, 4768, 12423, 32628, 86342, 229952, 616042, 1659012, 4489101, 12199521, 33284546, 91140797, 250396629, 690043032, 1907022197, 5284167884, 14677681554, 40862469713, 114001697975

Offset: 0

Emeric Deutsch and Louis Shapiro, Nov 04 2006

nonn

A 1-2-3 tree is an ordered tree with vertices of outdegree at most 3. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.

Vaclav Kotesovec, Recurrence (of order 11)

Cf. A090344, A124344.

C:=x->(1-sqrt(1-4*x))/2/x: T:=x->2/sqrt(3*x)*sin((1/3)*arcsin(sqrt(27*x/4))): M2:=C(z^2/(1-z))/(1-z): G:=M2*T(M2^2*z^3): Gser:=series(G,z=0,40): seq(coeff(Gser,z,n),n=0..33);

Table[(Sum[Binomial[3*m, m] * Sum[(Binomial[2*m + 2*k, k]*Binomial[n - m - k, 2*m + k])/(2*m + k + 1), {k, 0, n - m}], {m, 1, n + 2}]) + Sum[(Binomial[2*k, k]*Binomial[n - k, k])/(k + 1), {k, 0, n/2}], {n, 0, 40}] (* Vaclav Kotesovec, Apr 22 2016, after Vladimir Kruchinin *)

a(n):=(sum(binomial(3*m,m)*sum((binomial(2*m+2*k,k)*binomial(n-m-k,2*m+k))/(2*m+k+1),k,0,n-m),m,1,n+2))+sum((binomial(2*k,k)*binomial(n-k,k))/(k+1),k,0,n/2); /* Vladimir Kruchinin, Apr 22 2016 */

G.f.: H*T(H^2*z^3), where T=2/sqrt(3*x)*sin((1/3)*arcsin(sqrt(27*x/4))) (solution of T=1+zT^3, T(0)=1), H=C(z^2/(1-z))/(1-z) and C(x)=[1-sqrt(1-4x)]/(2x) is the Catalan function.
More generally, if M[k](z) is the g.f. of the 1-2-...-k trees with thinning limbs and C[k](z)=1+z*{C[k](z)}^k is the g.f. of the k-ary trees, then M[k](z)=M[k-1](z)C[k](M[k-1]^(k-1)*z^k).
a(n) = Sum_{m=1..n+2} (binomial(3*m,m)*Sum_{k=0..n-m}((binomial(2*m+2*k,k)* binomial(n-m-k,2*m+k))/(2*m+k+1))) + Sum_{k=0..n/2}((binomial(2*k,k)*binomial(n-k,k))/(k+1)). - Vladimir Kruchinin, Apr 24 2016
a(n) ~ c * d^n / n^(3/2), where d = (116 + (13044347 - 19683*sqrt(419729))^(1/3) + (13044347 + 19683*sqrt(419729))^(1/3)) / 162 = 2.949682448495588889993... and c = sqrt((9801741469 + 2*(101206884976506223911903300479 - 12725091747254383734308121 * sqrt(419729))^(1/3) + 2*(101206884976506223911903300479 + 12725091747254383734308121 * sqrt(419729))^(1/3)) / (773*Pi)) / 2916 = 1.1733468012519971025510728494463... . - Vaclav Kotesovec, Apr 22 2016

A257178 Number of 3-Motzkin paths of length n with no level steps at odd level.

Original entry on oeis.org

1, 3, 10, 33, 110, 369, 1247, 4245, 14558, 50295, 175029, 613467, 2165100, 7692345, 27504600, 98941185, 357952580, 1301960925, 4759282415, 17478557925, 64468072820, 238736987535, 887359113700, 3309489922743, 12381998910700, 46460457776739

Offset: 0

José Luis Ramírez Ramírez, Apr 20 2015

nonn

			For n=2 we have 10 paths: H(1)H(1), H(1)H(2), H(1)H(3), H(2)H(1), H(2)H(2), H(2)H(3), H(3)H(1), H(3)H(2), H(3)H(3) and UD.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A090344, A086622.

CoefficientList[Series[(1-3*x-Sqrt[(1-3*x)*(1-3*x-4x^2)])/(2*x^2*(1-3*x)), {x, 0, 20}], x] (* Vaclav Kotesovec, Apr 21 2015 *)

Vec((1-3*x-sqrt((1-3*x)*(1-3*x-4*x^2)))/(2*x^2*(1-3*x)) + O(x^50)) \\ G. C. Greubel, Feb 05 2017

a(n)= Sum_{i=0..floor(n/2)}3^(n-2i)*C(i)*binomial(n-i,i), where C(n) is the n-th Catalan number A000108.
G.f.: (1-3*z-sqrt((1-3*z)*(1-3*z-4*z^2)))/(2*z^2*(1-3*z)).
a(n) ~ sqrt(5) * 4^(n+1) / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Apr 21 2015
Conjecture: (n+2)*a(n) +6*(-n-1)*a(n-1) +(5*n+4)*a(n-2) +6*(2*n-3)*a(n-3)=0. - R. J. Mathar, Sep 24 2016
G.f. A(x) satisfies: A(x) = 1/(1 - 3*x) + x^2 * A(x)^2. - Ilya Gutkovskiy, Jun 30 2020

A346074 a(n) = 1 + Sum_{k=0..n-5} a(k) * a(n-k-5).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 9, 14, 21, 30, 41, 59, 89, 136, 205, 301, 443, 664, 1011, 1545, 2341, 3530, 5341, 8143, 12487, 19148, 29299, 44817, 68721, 105742, 163025, 251392, 387595, 597988, 924047, 1430167, 2215595, 3433788, 5323915, 8260652, 12829849

Offset: 0

Ilya Gutkovskiy, Jul 04 2021

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A007317, A090344, A216604, A307972, A346073.

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

a(n) = sum(k=0, n\5, binomial(n-4*k, k)*binomial(2*k, k)/(k+1)); \\ Seiichi Manyama, Jan 22 2023

G.f. A(x) satisfies: A(x) = 1 / (1 - x) + x^5 * A(x)^2.
Conjecture D-finite with recurrence (n+5)*a(n) +2*(-n-4)*a(n-1) +(n+3)*a(n-2) +2*(-2*n+5)*a(n-5) +4*(n-3)*a(n-6)=0. - R. J. Mathar, Feb 17 2022
a(n) = Sum_{k=0..floor(n/5)} binomial(n-4*k,k) * Catalan(k). - Seiichi Manyama, Jan 22 2023

A124499 Number of 1-2-3-4 trees with n edges and with thinning limbs. A 1-2-3-4 tree is an ordered tree with vertices of outdegree at most 4. A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.

Original entry on oeis.org

1, 1, 2, 4, 10, 24, 62, 160, 425, 1140, 3105, 8528, 23643, 66008, 185526, 524384, 1489810, 4251852, 12184745, 35048405, 101156752, 292865417, 850314803, 2475327088, 7223400899, 21126670372, 61920289652, 181838859665

Offset: 0

Emeric Deutsch and Louis Shapiro, Nov 06 2006

nonn

The sequences corresponding to k=2 (A090344), k=3 (A124497), k=4 (this A124499), k=5 (A124500), etc. approach sequence A124344, corresponding to ordered trees with thinning limbs.

Cf. A090344, A124497, A124500, A124501, A124344.

{a(n)=local(k=4,M=1+x*O(x^n)); for(i=1,k,M=M*sum(j=0,n,binomial(i*j,j)/((i-1)*j+1)*(x^i*M^(i-1))^j)); polcoeff(M,n)} \\ Paul D. Hanna

In general, if M[k](z) is the g.f. of the 1-2-...-k trees with thinning limbs and C[k](z)=1+z*{C[k](z)}^k is the g.f. of the k-ary trees, then M[k](z)=M[k-1](z)*C[k](M[k-1]^(k-1)*z^k), M[1](z)=1/(1-z).

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

A098474 Triangle read by rows, T(n,k) = C(n,k)*C(2*k,k)/(k+1), n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Sage

Formula

Extensions

A090345 Number of Motzkin paths of length n with no level steps at even level.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A332602 Tridiagonal matrix M read by antidiagonals: main diagonal is 1,2,2,2,2,..., two adjacent diagonals are 1,1,1,1,1,...

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A039982 Let phi denote the morphism 0 -> 11, 1 -> 10. This sequence is the limit S(oo) where S(0) = 1; S(n+1) = 1.phi(S(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Mathematica

PARI

PARI

Formula

Extensions

A346073 a(n) = 1 + Sum_{k=0..n-4} a(k) * a(n-k-4).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

A124497 Number of 1-2-3 trees with n edges and with thinning limbs.

Views

Author

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

A098474 Triangle read by rows, T(n,k) = C(n,k)C(2k,k)/(k+1), n >= 0, 0 <= k <= n.