cp's OEIS Frontend

A025235 a(n) = (1/2)*s(n+2), where s = A014431.

%I A025235 #100 Jun 12 2025 14:11:49
%S A025235 1,1,3,7,21,61,191,603,1961,6457,21595,72975,249085,857013,2970007,
%T A025235 10356323,36311633,127937649,452738867,1608426647,5734534629,
%U A025235 20511509549,73583105007,264687136235,954482676217,3449853902761,12495597328011,45349353908383
%N A025235 a(n) = (1/2)*s(n+2), where s = A014431.
%C A025235 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 A025235 Equals inverse binomial transform of A071356: (1, 2, 6, 20, 72, ...). - _Gary W. Adamson_, Sep 03 2010
%C A025235 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 A025235 G. C. Greubel, <a href="/A025235/b025235.txt">Table of n, a(n) for n = 0..1000</a>
%H A025235 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 A025235 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 A025235 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 A025235 Stefano Capparelli and Alberto 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 A025235 Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, <a href="https://doi.org/10.37236/4793">Combinatorial proofs of addition formulas</a>, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
%H A025235 Serkan Demiriz, Adem Şahin, and Sezer Erdem, <a href="https://doi.org/10.1007/s12215-025-01243-3">Some topological and geometric properties of novel generalized Motzkin sequence spaces</a>, Rendiconti Circ. Mat. Palermo Ser. 2 (2025) Vol. 74, No. 136. See p. 4.
%H A025235 Maciej Dziemiańczuk, <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 A025235 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 A025235 Louis W. Shapiro and Carol 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 A025235 a(n) = Sum_{k=0..n} 2^(k-1)*binomial(n+1, k)*binomial(n-k+1, k-1)/(n+1 ). - _Len Smiley_
%F A025235 G.f.: (1 - x - sqrt(1 - 2*x - 7*x^2)) / (4*x^2). - _Michael Somos_, Jun 08 2000
%F A025235 G.f. (for offset 1) is series reversion of x / (1 + x + 2*x^2). - _Michael Somos_, Jul 12 2003
%F A025235 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 A025235 E.g.f.: exp(x)*BesselI(1, 2*sqrt(2)*x)/(sqrt(2)*x). - _Vladeta Jovovic_, Mar 31 2004
%F A025235 From _Gary W. Adamson_, Feb 21 2012: (Start)
%F A025235 a(n) is the leftmost term in the top row of M^n, M is an infinite square production matrix as follows:
%F A025235   1, 1, 0, 0, 0, 0, ...
%F A025235   2, 0, 1, 0, 0, 0, ...
%F A025235   2, 2, 0, 1, 0, 0, ...
%F A025235   2, 2, 2, 0, 1, 0, ...
%F A025235   2, 2, 2, 2, 0, 1, ...
%F A025235   2, 2, 2, 2, 2, 0, ...
%F A025235   2, 2, 2, 2, 2, 2, ...
%F A025235   ... (End)
%F A025235 From _Vaclav Kotesovec_, Sep 29 2012: (Start)
%F A025235 a(n) ~ (1+2*sqrt(2))^(n+3/2)/(2*sqrt(Pi)*2^(3/4)*n^(3/2)).
%F A025235 Recurrence: (n+2)*a(n) = (2*n+1)*a(n-1) + 7*(n-1)*a(n-2). (End)
%F A025235 a(n) = hypergeom([-n/2, (1-n)/2], [2], 8). - _Peter Luschny_, May 28 2014
%F A025235 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 A025235 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 A025235 a(4) = 21 since the top row of M^4 = (21, 11, 7, 1, 1)
%t A025235 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 A025235 a[n_] := Hypergeometric2F1[1/2 - n/2, -n/2, 2, 8];
%t A025235 Table[a[n], {n, 0, 27}] (* _Peter Luschny_, Mar 18 2018 *)
%o A025235 (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 A025235 (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 A025235 (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 A025235 Cf. A071356, A001003, A068764, A217275.
%K A025235 nonn
%O A025235 0,3
%A A025235 _Clark Kimberling_