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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A068875 Expansion of (1+x*C)*C, where C = (1-(1-4*x)^(1/2))/(2*x) is the g.f. for Catalan numbers, A000108. 16
1, 2, 4, 10, 28, 84, 264, 858, 2860, 9724, 33592, 117572, 416024, 1485800, 5348880, 19389690, 70715340, 259289580, 955277400, 3534526380, 13128240840, 48932534040, 182965127280, 686119227300, 2579808294648, 9723892802904 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

A Catalan transform of A040000 under the mapping g(x)->g(xc(x)). A040000 can be retrieved using the mapping g(x)->g(x(1-x)). A040000(n)=sum{k=0..floor(n/2), C(n-k,k)(-1)^k*a(n-k)}. a(n) and A040000 may be described as a Catalan pair. - Paul Barry, Nov 14 2004

a(n) = number of Dyck (n+1)-paths all of whose nonterminal descents to ground level are of odd length. For example, a(2) counts UUUDDD, UUDUDD, UDUUDD, UDUDUD. - David Callan, Jul 25 2005

For n>=1, a(n) is the number of binary trees with n+1 internal nodes in which one of the subtrees of the root is empty. Cf. A002057 [Sedgewick and Flajolet] - Geoffrey Critzer, Jan 05 2013

REFERENCES

R. Sedgewick and P Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 225.

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, Enumeration of polyene hydrocarbons: a complete mathematical solution, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751. [Annotated scanned copy]

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)

Guo-Niu Han, Enumeration of Standard Puzzles

Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]

FORMULA

Apart from initial term, twice Catalan numbers.

G.f.: (1 - x - sqrt(1 - 4*x)) / x. - Michael Somos, Apr 13 2012

G.f.: (1+x*c(x))/(1-x*c(x)), where c(x) is the g.f. of A000108; a(n)=C(n)*(2-0^n); C(n) as in A000108; a(n) = Sum{j=0..n, Sum{k=0..n, C(2*n, n-k)*((2*k+1)/(n+k+1))*C(k, j)(-1)^(j-k)*(2-0^j)}}. - Paul Barry, Nov 14 2004

Assuming offset 1, then series reversion of g.f. A(x) is -A(-x). - Michael Somos, Aug 17 2005

Assuming offset 2, then A(x) satisfies A(x - x^2) = x^2 - x^4 and so A(x)=C(x)^2-C(x)^4, A(A(x))=C(x)^4-C(x)^8, A(A(A(x)))=C(x)^8-C(x)^16, etc., where C(x) = (1-sqrt(1-4*x))/2 = x + x^2 + 2*x^3 + 5*x^4 + 14*x^5 + ... . - Paul D. Hanna, May 16 2008

Apart from initial term, INVERTi transform of A000984(n+1) = binomial(2*n+2,n+1), also, for n>=1, a(n)=(1/Pi)*int(x^(n-1)*sqrt(x*(4-x)),x=0..4). - Groux Roland, Mar 15 2011

a(n) = sum of top row terms in M^n, where M is the following infinite square production matrix:

1, 1, 0, 0, 0, 0, ...

0, 1, 1, 0, 0, 0, ...

1, 1, 1, 1, 0, 0, ...

0, 1, 1, 1, 1, 0, ...

1, 1, 1, 1, 1, 1, ...

...

For example, the top row of M^3 = (2, 4, 3, 1), sum = 10 = a(3). -_ Gary W. Adamson_, Jul 11 2011

(n+2)*a(n) - 2*(2*n+1)*a(n-1) = 0, n>1. - R. J. Mathar, Nov 14 2011

For n>0, a(n) = C(2n+2,n+1) mod 4*C(2n,n-1). - Robert G. Wilson v, May 02 2012

For n>0, a(n) = 2^(2*n+1)*Gamma(n+1/2)/(sqrt(Pi)*(n+1)!). - Vaclav Kotesovec, Sep 16 2013

G.f.: 1 + 2*x/(Q(0)-x), where Q(k) = 2*x + (k+1)/(2*k+1) - 2*x*(k+1)/(2*k+1)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 03 2013

G.f.: 3-4*x - 2*S(0), where S(k) = 2*k+1 - x*(2*k+3)/(1 - x*(2*k+1)/S(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 23 2013

0 = a(n)*(16*a(n+1) - 10*a(n+2)) + a(n+1)*(2*a(n+1) + a(n+2)) for all n in Z. - Michael Somos, Jun 18 2014

If A(x)^t = 1 + 2*t*x + Sum_{n >= 2} t*P(n,t)*x^n, then we conjecture that all the zeros of the polynomial P(n,t) lie on the vertical line Re(t) = -n/2 in the complex plane. - Peter Bala, Oct 05 2015

EXAMPLE

G.f. = 1 + 2*x + 4*x^2 + 10*x^3 + 28*x^4 + 84*x^5 + 264*x^6 + 858*x^7 + ...

MAPLE

Z:=(1-sqrt(1-4*x))/2/x: G:=(2-(1+x)*Z)/Z: Gser:=series(-G, x=0, 30): (1, seq(coeff(Gser, x, n), n=2..26)); # Zerinvary Lajos, Dec 23 2006

Z:=-(1-z-sqrt(1-z))/sqrt(1-z): Zser:=series(Z, z=0, 32): (1, seq(coeff(Zser*4^n, z, n), n=2..26)); # Zerinvary Lajos, Jan 01 2007

MATHEMATICA

nn=30; t=(1-(1-4x )^(1/2))/(2x); Prepend[Table[Coefficient[Series[1+x (y t -y+1)^2, {x, 0, nn}], x ^n y], {n, 2, nn}], 1]  (* Geoffrey Critzer, Jan 05 2013 *)

a[ n_] := If[ n < 1, Boole[ n == 0], 2 Binomial[ 2 n, n]/(n + 1)]; (* Michael Somos, Jun 18 2014 *)

a[ n_] := SeriesCoefficient[ -1 + 4 / (1 + Sqrt[ 1 - 4 x]), {x, 0, n}]; (* Michael Somos, Jun 18 2014 *)

Table[If[n==0, 1, 2 CatalanNumber[n]], {n, 0, 25}] (* Peter Luschny, Feb 27 2017 *)

PROG

(PARI) {a(n) = if( n<1, n==0, 2 * binomial( 2*n, n) / (n + 1))}; /* Michael Somos, Aug 17 2005 */

(PARI) {a(n) = if( n<0, 0, polcoeff( -1 + 4 / (1 + sqrt(1 - 4*x + x * O(x^n))), n))}; /* Michael Somos, Aug 17 2005 */

CROSSREFS

A002420 and A262543 are essentially the same sequence as this.

Cf. A000108, A000984, A002057, A040000, A068875.

Sequence in context: A192653 A149824 A202135 * A262543 A289709 A192574

Adjacent sequences:  A068872 A068873 A068874 * A068876 A068877 A068878

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Jun 06 2002

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 16 08:52 EDT 2017. Contains 290623 sequences.