|
%I #138 Jan 10 2024 23:54:15
%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(x*c(x)), where c(x) is the g.f. of A000108. Sequence A040000 can be retrieved using the mapping g(x) -> g(x*(1-x)). A040000(n) = Sum_{k=0..floor(n/2)} binomial(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) is the 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 From _Gary W. Adamson_, Jul 11 2011: (Start)
%C a(n) is the sum of the top row terms in M^n, where M is the following infinite square production matrix:
%C 1, 1, 0, 0, 0, 0, ...
%C 0, 1, 1, 0, 0, 0, ...
%C 1, 1, 1, 1, 0, 0, ...
%C 0, 1, 1, 1, 1, 0, ...
%C 1, 1, 1, 1, 1, 1, ...
%C ...
%C For example, the top row of M^3 = (2, 4, 3, 1) with sum = 10 = a(3). (End)
%C For n >= 1, a(n) is the number of binary trees with n+1 internal node 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
%C For n >= 1, a(n) is the number of Dyck paths of size n+2, whose corresponding unit interval graph has P3-hull number equal to 2. This result is due to Alrik Sandberg. - _Per W. Alexandersson_, Jan 09 2024
%D R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, p. 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 Paul Barry, <a href="https://arxiv.org/abs/1807.05794">Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences</a>, arXiv:1807.05794 [math.CO], 2018.
%H Alexander Burstein and Louis W. Shapiro, <a href="https://arxiv.org/abs/2112.11595">Pseudo-involutions in the Riordan group</a>, arXiv:2112.11595 [math.CO], 2021.
%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 and 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="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a>, 2011. [Cached copy]
%H Guo-Niu Han, <a href="https://arxiv.org/abs/2006.14070">Enumeration of Standard Puzzles</a>, arXiv:2006.14070 [math.CO], 2020.
%F Apart from initial term, twice Catalan numbers.
%F G.f.: (1 - x - sqrt(1 - 4*x)) / x. - _Michael Somos_, Apr 13 2012
%F From _Paul Barry_, Nov 14 2004: (Start)
%F G.f.: (1 + x*c(x))/(1 - x*c(x)), where c(x) is the g.f. of A000108.
%F a(n) = C(n)*(2-0^n), where C(n) = A000108(n).
%F a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(2*n, n-k) *((2*k + 1)/(n + k + 1)) * binomial(k, j) * (-1)^(j-k) * (2 - 0^j). (End)
%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)*Integral_{x=0..4} x^(n-1)*sqrt(x*(4 - x)). - _Groux Roland_, Mar 15 2011
%F D-finite with recurrence (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(2*n+2, n+1) mod 4*C(2*n, 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
%F a(n+1) = a(n) + (1/2)*(Sum_{k=0..n} a(k)*a(n-k)) if n > 0. - _Michael Somos_, Apr 22 2022
%F b(n) = a(n+1) - a(n) for all n in Z if b(0) = 2, a(-1) = -1, a(0) = 0, a(-1) = 3, a(-2) = -1 where b = A071721. - _Michael Somos_, Apr 23 2022
%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
%p A068875List := proc(m) local A, P, n; A := [1, 2]; P := [2];
%p for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-1]]);
%p A := [op(A), P[-1]] od; A end: A068875List(26); # _Peter Luschny_, Mar 24 2022
%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, A071721.
%K nonn
%O 0,2
%A _N. J. A. Sloane_, Jun 06 2002
|
