|
%I #79 Oct 24 2023 12:39:45
%S 1,1,1,2,4,7,13,26,52,104,212,438,910,1903,4009,8494,18080,38656,
%T 82988,178802,386490,837928,1821664,3970282,8673258,18987930,41652382,
%U 91539466,201525238,444379907,981384125,2170416738,4806513660
%N Generalized Catalan Numbers.
%C Essentially the same as A025246.
%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=(2,-1). E.g. a(5)=7 because we have HHHHH, HHUD, HUDH, HUHD, UDHH, UHDH and UHHD. - _Emeric Deutsch_, Dec 25 2003
%C 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
%C Series reversion of g.f. A(x) is -A(-x) (if offset 1). - _Michael Somos_, Jul 13 2003
%C Hankel transform is A010892(n+1). [From _Paul Barry_, Sep 19 2008]
%C 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
%H Reinhard Zumkeller, <a href="/A023431/b023431.txt">Table of n, a(n) for n = 0..1000</a>
%H Andrei Asinowski, Cyril Banderier, and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).
%H Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, <a href="https://arxiv.org/abs/1804.01293">Enumeration of Łukasiewicz paths modulo some patterns</a>, arXiv:1804.01293 [math.CO], 2018.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Barry3/barry93.html">Continued fractions and transformations of integer sequences</a>, JIS 12 (2009) 09.7.6.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.
%H Paul Barry, <a href="https://arxiv.org/abs/1807.05794">Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences</a>, arXiv:1807.05794 [math.CO], 2018.
%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 J. Cigler, <a href="http://arxiv.org/abs/1109.1449">Some nice Hankel determinants</a>, arXiv preprint arXiv:1109.1449 [math.CO], 2011.
%H S. B. Ekhad and M. Yang, <a href="http://sites.math.rutgers.edu/~zeilberg/tokhniot/oMathar1maple12.txt">Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences</a>, (2017)
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=666">Encyclopedia of Combinatorial Structures 666</a>
%H K. Park and G.-S. Cheon, <a href="https://www.kms.or.kr/conference/abstract/search_view.html?num=5098&uid=32">Lattice path counting with a bounded strip restriction</a>
%H Helmut Prodinger, <a href="https://arxiv.org/abs/2310.12497">Motzkin paths of bounded height with two forbidden contiguous subwords of length two</a>, arXiv:2310.12497 [math.CO], 2023.
%F 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
%F 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
%F a(n) = A025246(n+3). - _Michael Somos_, Jan 20 2004
%F G.f.: (1/(1-x))*c(x^3/(1-x)^2), c(x) the g.f. of A000108. - From _Paul Barry_, Sep 19 2008
%F From _Paul Barry_, May 22 2009: (Start)
%F G.f.: 1/(1-x-x^3/(1-x-x^3/(1-x-x^3/(1-x-x^3/(1-... (continued fraction).
%F a(n) = Sum_{k=0..floor(n/3)} binomial(n-k, 2*k)*A000108(k). (End)
%F (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
%F 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
%F 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
%F a(n) = hypergeom([(1 - n)/3, (2 - n)/3, -n/3], [2, -n], 27). - _Peter Luschny_, Jun 15 2022
%e 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 + ...
%p a := n -> hypergeom([1/3 - n/3, 2/3 - n/3, -n/3], [2, -n], 27):
%p seq(simplify(a(n)), n = 0..32); # _Peter Luschny_, Jun 15 2022
%t a[0]=1; a[n_]:= a[n]= a[n-1] + Sum[a[k]*a[n-3-k], {k, 0, n-3}];
%t Table[a[n], {n,0,40}]
%o (PARI) {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 */
%o (Haskell)
%o a023431 n = a023431_list !! n
%o a023431_list = 1 : 1 : f [1,1] where
%o f xs'@(x:_:xs) = y : f (y : xs') where
%o y = x + sum (zipWith (*) xs $ reverse $ xs')
%o -- _Reinhard Zumkeller_, Nov 13 2012
%o (Magma) [(&+[Binomial(n-k, 2*k)*Catalan(k): k in [0..Floor(n/3)]]): n in [0..40]]; // _G. C. Greubel_, Jun 15 2022
%o (SageMath) [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
%Y Cf. A000108, A001006, A004148, A006318, A025246.
%Y Cf. A014137, A090344, A144700.
%K nonn,easy
%O 0,4
%A _Olivier Gérard_
|
