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

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.

J. Cigler, Some nice Hankel determinants, arXiv preprint arXiv:1109.1449, 2011.

S. B. Ekhad, M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017)

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

Olivier Gérard

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 11:48 EDT 2019. Contains 328345 sequences. (Running on oeis4.)