|
| |
|
|
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.
|
|
23
|
|
|
|
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(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
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
a(n) is the sum of the 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) with sum = 10 = a(3). (End)
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
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
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
|
|
|
REFERENCES
|
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, p. 225.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Apart from initial term, twice Catalan numbers.
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), where C(n) = A000108(n).
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)
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)*Integral_{x=0..4} x^(n-1)*sqrt(x*(4 - x)). - Groux Roland, Mar 15 2011
D-finite with recurrence (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) = 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
a(n+1) = a(n) + (1/2)*(Sum_{k=0..n} a(k)*a(n-k)) if n > 0. - Michael Somos, Apr 22 2022
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
|
|
|
EXAMPLE
|
G.f. = 1 + 2*x + 4*x^2 + 10*x^3 + 28*x^4 + 84*x^5 + 264*x^6 + 858*x^7 + ...
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.
|
|
|
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
A068875List := proc(m) local A, P, n; A := [1, 2]; P := [2];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-1]]);
A := [op(A), P[-1]] od; A end: A068875List(26); # Peter Luschny, Mar 24 2022
|
|
|
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 */
(Magma) [1] cat [2*Binomial( 2*n, n)/(n+1): n in [1..30]]; // Vincenzo Librandi, Oct 17 2017
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
