%I #93 Jun 07 2023 09:45:51
%S 1,1,3,7,21,61,191,603,1961,6457,21595,72975,249085,857013,2970007,
%T 10356323,36311633,127937649,452738867,1608426647,5734534629,
%U 20511509549,73583105007,264687136235,954482676217,3449853902761,12495597328011,45349353908383
%N a(n) = (1/2)*s(n+2), where s = A014431.
%C 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
%C Equals inverse binomial transform of A071356: (1, 2, 6, 20, 72, ...). - _Gary W. Adamson_, Sep 03 2010
%C 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
%H G. C. Greubel, <a href="/A025235/b025235.txt">Table of n, a(n) for n = 0..1000</a>
%H Paul Barry, <a href="https://arxiv.org/abs/1910.00875">Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials</a>, arXiv:1910.00875 [math.CO], 2019.
%H Paul Barry, <a href="https://arxiv.org/abs/2001.08799">Characterizations of the Borel triangle and Borel polynomials</a>, arXiv:2001.08799 [math.CO], 2020.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Barry/barry601.html">On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
%H S. Capparelli and A. Del Fra, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Capparelli/cap3.html">Dyck Paths, Motzkin Paths, and the Binomial Transform</a>, Journal of Integer Sequences, 18 (2015), #15.8.5.
%H Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p8">Combinatorial proofs of addition formulas</a>, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
%H M. Dziemianczuk, <a href="http://dx.doi.org/10.1007/s00373-013-1357-1">Counting Lattice Paths With Four Types of Steps</a>, Graphs and Combinatorics, September 2013, DOI 10.1007/s00373-013-1357-1.
%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H L. W. Shapiro and C. J. Wang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Shapiro/shapiro7.html">A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height</a>, JIS 12 (2009) 09.3.2.
%F a(n) = Sum_{k=0..n} 2^(k-1)*binomial(n+1, k)*binomial(n-k+1, k-1)/(n+1 ). - _Len Smiley_
%F G.f.: (1 - x - sqrt(1 - 2*x - 7*x^2)) / (4*x^2). - _Michael Somos_, Jun 08 2000
%F G.f. (for offset 1) is series reversion of x / (1 + x + 2*x^2). - _Michael Somos_, Jul 12 2003
%F 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
%F E.g.f.: exp(x)*BesselI(1, 2*sqrt(2)*x)/(sqrt(2)*x). - _Vladeta Jovovic_, Mar 31 2004
%F From _Gary W. Adamson_, Feb 21 2012: (Start)
%F a(n) is the leftmost term in the top row of M^n, M is an infinite square production matrix as follows:
%F 1, 1, 0, 0, 0, 0, ...
%F 2, 0, 1, 0, 0, 0, ...
%F 2, 2, 0, 1, 0, 0, ...
%F 2, 2, 2, 0, 1, 0, ...
%F 2, 2, 2, 2, 0, 1, ...
%F 2, 2, 2, 2, 2, 0, ...
%F 2, 2, 2, 2, 2, 2, ...
%F ... (End)
%F a(n) ~ (1+2*sqrt(2))^(n+3/2)/(2*sqrt(Pi)*2^(3/4)*n^(3/2)). - _Vaclav Kotesovec_, Sep 29 2012
%F Recurrence: (n+2)*a(n) = (2*n+1)*a(n-1) + 7*(n-1)*a(n-2). - _Vaclav Kotesovec_, Sep 29 2012
%F a(n) = hypergeom([-n/2, (1-n)/2], [2], 8). - _Peter Luschny_, May 28 2014
%F 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
%e x + x^2 + 3*x^3 + 7*x^4 + 21*x^5 + 61*x^6 + 191*x^7 + 603*x^8 + 1961*x^9 + ...
%e a(4) = 21 since the top row of M^4 = (21, 11, 7, 1, 1)
%t 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 *)
%t a[n_] := Hypergeometric2F1[1/2 - n/2, -n/2, 2, 8];
%t Table[a[n], {n, 0, 27}] (* _Peter Luschny_, Mar 18 2018 *)
%o (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 */
%o (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 */
%o (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 */
%Y Cf. A071356, A001003, A068764, A217275.
%K nonn
%O 0,3
%A _Clark Kimberling_