login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A023431 Generalized Catalan Numbers. 8

%I

%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 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 J. Cigler, <a href="http://arxiv.org/abs/1109.1449">Some nice Hankel determinants</a>, arXiv preprint arXiv:1109.1449, 2011.

%H S. B. Ekhad, 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, G.-S. Cheon, <a href="http://www.kms.or.kr/conference/abstract/search_view.html?num=5098&amp;uid=32&amp;start=0&amp;sort=sortDate&amp;period=32&amp;cate=&amp;etitle=&amp;key_word=&amp;au_name=&amp;au_ename=&amp;au_office=&amp;au_eoffice=&amp;mode=search&amp;section=">Lattice path counting with a bounded strip restriction</a>

%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 Contribution 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)} C(n-k,2k)*A000108(k). (End)

%F 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

%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

%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 + ...

%t Clear[ a ]; a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-3-k ], {k, 0, n-3} ];

%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

%Y Cf. A000108, A001006, A004148, A006318, A025246.

%K nonn,easy

%O 0,4

%A _Olivier Gérard_

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 17:21 EST 2019. Contains 329287 sequences. (Running on oeis4.)