The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A023431 Generalized Catalan Numbers. 8
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS 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 LINKS Reinhard Zumkeller, Table of n, a(n) for n = 0..1000 Andrei Asinowski, Cyril Banderier, 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. J. Cigler, Some nice Hankel determinants, arXiv preprint arXiv:1109.1449 [math.CO], 2011. INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 666 K. Park, G.-S. Cheon, Lattice path counting with a bounded strip restriction FORMULA 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 Contribution 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)} C(n-k,2k)*A000108(k). (End) Conjecture: (n+3)*a(n) +(-2*n-3)*a(n-1) +n*a(n-2) +2*(-2*n+3)*a(n-3)=0. - 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 EXAMPLE 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 + ... MATHEMATICA Clear[ a ]; a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-3-k ], {k, 0, n-3} ]; PROG (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 */ (Haskell) 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 CROSSREFS Cf. A000108, A001006, A004148, A006318, A025246. Sequence in context: A262267 A068031 A293314 * A025246 A256942 A112740 Adjacent sequences:  A023428 A023429 A023430 * A023432 A023433 A023434 KEYWORD nonn,easy AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 1 12:29 EDT 2020. Contains 334762 sequences. (Running on oeis4.)