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

%I

%S 1,2,4,10,28,84,264,858,2860,9724,33592,117572,416024,1485800,5348880,

%T 19389690,70715340,259289580,955277400,3534526380,13128240840,

%U 48932534040,182965127280,686119227300,2579808294648,9723892802904

%N Expansion of (1+x*C)*C, where C = (1-(1-4*x)^(1/2))/(2*x) is the g.f. for Catalan numbers, A000108.

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

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

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

%C Empirical: a(n) is the number of entries of absolute value 1 that appear among all partitions in the canonical basis of the Temperley-Lieb algebra of order n. - _John M. Campbell_, Oct 17 2017

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

%H G. C. Greubel, <a href="/A068875/b068875.txt">Table of n, a(n) for n = 0..1000</a>

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

%H S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin and E. K. Lloyd, <a href="/A002057/a002057.pdf">Enumeration of polyene hydrocarbons: a complete mathematical solution</a>, J. Chem. Inf. Comput. Sci., 35 (1995) 743-751. [Annotated scanned copy]

%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 Guo-Niu Han, <a href="http://www-irma.u-strasbg.fr/~guoniu/papers/p77puzzle.pdf">Enumeration of Standard Puzzles</a>

%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a> [Cached copy]

%F Apart from initial term, twice Catalan numbers.

%F G.f.: (1 - x - sqrt(1 - 4*x)) / x. - _Michael Somos_, Apr 13 2012

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

%F Assuming offset 1, then series reversion of g.f. A(x) is -A(-x). - _Michael Somos_, Aug 17 2005

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

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

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

%F 1, 1, 0, 0, 0, 0, ...

%F 0, 1, 1, 0, 0, 0, ...

%F 1, 1, 1, 1, 0, 0, ...

%F 0, 1, 1, 1, 1, 0, ...

%F 1, 1, 1, 1, 1, 1, ...

%F ...

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

%F (n+2)*a(n) - 2*(2*n+1)*a(n-1) = 0, n>1. - _R. J. Mathar_, Nov 14 2011

%F For n>0, a(n) = C(2n+2,n+1) mod 4*C(2n,n-1). - _Robert G. Wilson v_, May 02 2012

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

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

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

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

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

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

%e For example, the canonical basis of the Temperley-Lieb algebra of order 3 is {{{-3, 1}, {-2, -1}, {2, 3}}, {{-3, 3}, {-2, 2}, {-1, 1}}, {{-3, 3}, {-2, -1}, {1, 2}}, {{-3, -2}, {-1, 1}, {2, 3}}, {{-3, -2}, {-1, 3}, {1, 2}}}, and we see that the total number of entries of absolute value 1 that appear among the partitions in this basis is a(3) = 10.

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

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

%t 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 *)

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

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

%t Table[If[n==0, 1, 2 CatalanNumber[n]], {n,0,25}] (* _Peter Luschny_, Feb 27 2017 *)

%o (PARI) {a(n) = if( n<1, n==0, 2 * binomial( 2*n, n) / (n + 1))}; /* _Michael Somos_, Aug 17 2005 */

%o (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 */

%o (MAGMA) [1] cat [2*Binomial( 2*n, n)/(n+1): n in [1..30]]; // Vincenzo Librandi, Oct 17 2017

%Y A002420 and A262543 are essentially the same sequence as this.

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

%K nonn

%O 0,2

%A _N. J. A. Sloane_, Jun 06 2002

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 February 17 21:12 EST 2018. Contains 299297 sequences. (Running on oeis4.)