0,3

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=(1,-1), where the U steps come in two colors: red (R) and green (G) (i.e., Motzkin paths with the up steps in two colors). E.g., a(3)=7 because we have HHH, HRD, HGD, RDH, GDH, RHD and GHD. - Emeric Deutsch, Dec 25 2003

Equals inverse binomial transform of A071356: (1, 2, 6, 20, 72, ...). - Gary W. Adamson, Sep 03 2010

a(n) is the number of increasing unary-binary trees with associated permutation that avoids 231. For more information about increasing unary-binary trees with an associated permutation, see A245888. - Manda Riehl, Aug 07 2014

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

Paul Barry, Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials, arXiv:1910.00875 [math.CO], 2019.

Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.

Paul Barry, On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.

Stefano Capparelli and Alberto Del Fra, Dyck Paths, Motzkin Paths, and the Binomial Transform, Journal of Integer Sequences, 18 (2015), #15.8.5.

Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.

Serkan Demiriz, Adem Şahin, and Sezer Erdem, Some topological and geometric properties of novel generalized Motzkin sequence spaces, Rendiconti Circ. Mat. Palermo Ser. 2 (2025) Vol. 74, No. 136. See p. 4.

Maciej Dziemiańczuk, Counting Lattice Paths With Four Types of Steps, Graphs and Combinatorics, September 2013.

Sezer Erdem, Adem Şahin, and Serkan Demiriz, On the convergent and null generalized Motzkin sequence spaces, J. Class. Analysis 27(1) (2026) 21-34. See p. 22.

Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

Louis W. Shapiro and Carol J. Wang, A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height, JIS 12 (2009) 09.3.2.

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

G.f.: (1 - x - sqrt(1 - 2*x - 7*x^2)) / (4*x^2). - Michael Somos, Jun 08 2000

G.f. (for offset 1) is series reversion of x / (1 + x + 2*x^2). - Michael Somos, Jul 12 2003

a(n) = Sum_{k=0..n} binomial(n, k)*2^(k/2)*C(k/2)*(1+(-1)^k)/2, where C(n)=A000108(n). - Paul Barry, Dec 22 2003

E.g.f.: exp(x)*BesselI(1, 2*sqrt(2)*x)/(sqrt(2)*x). - Vladeta Jovovic, Mar 31 2004

From Gary W. Adamson, Feb 21 2012: (Start)

a(n) is the leftmost term in the top row of M^n, M is an infinite square production matrix as follows:

1, 1, 0, 0, 0, 0, ...

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

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

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

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

2, 2, 2, 2, 2, 0, ...

2, 2, 2, 2, 2, 2, ...

... (End)

From Vaclav Kotesovec, Sep 29 2012: (Start)

a(n) ~ (1+2*sqrt(2))^(n+3/2)/(2*sqrt(Pi)*2^(3/4)*n^(3/2)).

Recurrence: (n+2)*a(n) = (2*n+1)*a(n-1) + 7*(n-1)*a(n-2). (End)

a(n) = hypergeom([-n/2, (1-n)/2], [2], 8). - Peter Luschny, May 28 2014

G.f.: 1/(1 - x - 2*x^2/(1 - x - 2*x^2/(1 - x - 2*x^2/(1 - x - 2*x^2/(1 - ....))))), a continued fraction. - Ilya Gutkovskiy, May 26 2017

x + x^2 + 3*x^3 + 7*x^4 + 21*x^5 + 61*x^6 + 191*x^7 + 603*x^8 + 1961*x^9 + ...

a(4) = 21 since the top row of M^4 = (21, 11, 7, 1, 1)

Join[{1}, Table[Sum[2^(k - 1)*Binomial[n + 1, k]*Binomial[n - k + 1, k - 1]/(n + 1), {k, 0, n}], {n, 0, 50}]] (* G. C. Greubel, Jan 27 2017 *)

a[n_] := Hypergeometric2F1[1/2 - n/2, -n/2, 2, 8];

Table[a[n], {n, 0, 27}] (* Peter Luschny, Mar 18 2018 *)

(PARI) {a(n) = if( n<0, 0, polcoeff( serreverse( x / (1 + x + 2*x^2 + x * O(x^n))), n+1))} /* Michael Somos, Jul 12 2003 */

(PARI) {a(n) = if( n<0, 0, polcoeff( (1 - x - sqrt(1 - 2*x -7*x^2 + x^3 * O(x^n)) ) / 4, n+2))} /* Michael Somos, Mar 31 2007 */

(PARI) {a(n) = local(A); if( n<0, 0, A = x * O(x^n); n! * simplify( polcoeff( exp(x + A) * besseli(1, 2*x * quadgen(8) + A), n)))} /* Michael Somos, Mar 31 2007 */

Cf. A071356, A001003, A068764, A217275.

Sequence in context: A351822 A005355 A182399 * A129366 A270049 A166358

Adjacent sequences: A025232 A025233 A025234 * A025236 A025237 A025238

nonn,easy

approved