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

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058987 a(n) = Catalan(n) - Motzkin(n-1). 3
0, 1, 3, 10, 33, 111, 378, 1303, 4539, 15961, 56598, 202214, 727389, 2632605, 9581211, 35047098, 128791323, 475281921, 1760726808, 6545921136, 24415415001, 91340016081, 342658850427, 1288774386909, 4858753673655, 18358309669651 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Number of Dyck paths with a "small Capital N" (a rise then a fall then a rise) - this follows from the exercise on p. 238 of Stanley stating that Motzkin numbers equal to the ballot number without (1,-1,1). Since Ballot numbers are Catalan numbers, the result follows from the well-known bijection with Dyck paths.

a(n + 2) = p(n + 2) where p(x) is the unique degree-n polynomial such that p(k) = Catalan(k) for k = 1, 2, ..., n+1. - Michael Somos, Oct 07 2003

REFERENCES

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; cf. p. 238.

LINKS

Harry J. Smith, Table of n, a(n) for n = 1..100

FORMULA

G.f.: (sqrt( 1 - 2*x - 3*x^2 ) - sqrt( 1 - 4*x ) - x) / (2*x) = (4*x^2) / ( (1 - 2*x + sqrt( 1 - 4*x )) * (1 - x + sqrt( 1 - 2*x - 3*x^2 )) - 4*x^2). - Michael Somos, Jan 05 2012

a(n) = A000108(n) - A001006(n-1) if n>0.

EXAMPLE

x^2 + 3*x^3 + 10*x^4 + 33*x^5 + 111*x^6 + 378*x^7 + 1303*x^8 + 4539*x^9 + ...

a(4) = 10 since p(x) = x^2 - 2*x + 2 interpolates p(1) = 1, p(2) = 2, p(3) = 5, and p(4) = 10. - Michael Somos, Jan 05 2012

PROG

(PARI) {a(n) = if( n<2, 0, n--; subst( polinterpolate( vector(n, k, binomial( 2*k, k) / (k + 1))), x, n + 1))} /* Michael Somos, Jan 05 2012 */

(PARI) {a(n) = local(A); if( n<2, 0, n -= 2; A = x * O(x^n); polcoeff( 4 / ( (1 - 2*x + sqrt( 1 - 4*x + A )) * (1 - x + sqrt( 1 - 2*x - 3*x^2 + A)) - 4*x^2 ), n))} /* Michael Somos, Jan 05 2012 */

(PARI) { allocatemem(932245000); for (n = 1, 100, a=if(n<=1, 0, subst(polinterpolate(vector(n-1, k, binomial(2*k, k)/(k+1))), x, n)); write("b058987.txt", n, " ", a); ) } \\ Harry J. Smith, Jun 24 2009

CROSSREFS

Cf. A000108, A001006.

Sequence in context: A257178 A257363 A071722 * A001558 A304824 A111639

Adjacent sequences:  A058984 A058985 A058986 * A058988 A058989 A058990

KEYWORD

nonn

AUTHOR

Sen-Peng Eu, Jan 17 2001

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 December 15 09:08 EST 2018. Contains 318148 sequences. (Running on oeis4.)