|
%I #15 Feb 23 2015 21:34:46
%S 0,1,3,10,33,111,378,1303,4539,15961,56598,202214,727389,2632605,
%T 9581211,35047098,128791323,475281921,1760726808,6545921136,
%U 24415415001,91340016081,342658850427,1288774386909,4858753673655,18358309669651
%N a(n) = Catalan(n) - Motzkin(n-1).
%C 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.
%C 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
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; cf. p. 238.
%H Harry J. Smith, <a href="/A058987/b058987.txt">Table of n, a(n) for n = 1..100</a>
%F 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
%F a(n) = A000108(n) - A001006(n-1) if n>0.
%e x^2 + 3*x^3 + 10*x^4 + 33*x^5 + 111*x^6 + 378*x^7 + 1303*x^8 + 4539*x^9 + ...
%e 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
%o (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 */
%o (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 */
%o (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
%Y Cf. A000108, A001006.
%K nonn
%O 1,3
%A _Sen-Peng Eu_, Jan 17 2001
|
