A171792 G.f. A(x) satisfies: A(x) = (x + A(x+x^2))/2 with A(0)=0.

1, 1, 2, 7, 34, 214, 1652, 15121, 160110, 1925442, 25924260, 386354366, 6314171932, 112286067892, 2158562109096, 44605949528355, 986049177712850, 23218586050641090, 580198948211652348, 15334750335623526670, 427408226085246086676, 12528910074528593086980

Offset: 1

Author

Paul D. Hanna, Jan 25 2010

Keywords

• nonn

Examples

			G.f.: A(x) = x + x^2 + 2*x^3 + 7*x^4 + 34*x^5 + 214*x^6 +...
A(x+x^2) = x + 2*x^2 + 4*x^3 + 14*x^4 + 68*x^5 + 428*x^6 + ...
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..425 (first 140 terms from Vaclav Kotesovec)
• Magnus Aspenberg, Rodrigo Perez, Control of cancellations that restrain the growth of a binomial recursion, arXiv:1006.1340 [math.CO], 2010; DOI:10.1007/s12220-014-9489-y, The Journal of Geometric Analysis, Vol. 25, No. 3 (2015), 1666-1700.
• Olivier Bodini, Antoine Genitrini, Bernhard Gittenberger, On the number of increasing trees with label repetitions, arXiv:1809.04314 [math.CO], 2018.
• Olivier Bodini, Antoine Genitrini, Cécile Mailler, Mehdi Naima, Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study, hal-02865198 [math.CO] / [math.PR] / [cs.DS] / [cs.DM], 2020.

Crossrefs

Cf. A122888.

Programs

Mathematica

Nest[Append[#1, Sum[Binomial[k, #2 - k] #[[k]], {k, Floor[#2/2], #2 - 1}]] & @@ {#, Length@ # + 1} &, {1}, 19] (* Michael De Vlieger, Dec 06 2018 *)

Maxima

a(n):=if n=1 then 1 else sum(binomial(k,n-k)*a(k),k,floor(n/2),n-1); /* Vladimir Kruchinin, Jun 25 2011 */

PARI

{a(n)=local(A=x+x^2);for(i=1,n*(n+1)/2,A=(x+subst(A,x,x+x^2+x*O(x^n)))/2);ceil(polcoeff(A,n))}

PARI

{a(n)=if(n==1,1,polcoeff(sum(m=1,n-1,a(m)*(x+x^2+x*O(x^n))^m),n))} \\ Paul D. Hanna, Jan 30 2010

Formula

G.f.: A(x) = Sum_{n>=0} G_{n}(x)/2^(n+1) where G_{n}(x) is the n-th iteration of (x+x^2) defined by G_{n}(x) = G_{n-1}(x+x^2) with G_0(x)=x.

a(k) = Sum_{n>=0} A122888(n,k)/2^(n+1).

a(k) is odd iff k is a power of 2: a(2^n) == 1 (mod 2) for n>=0.

Conjecture: a(n) = Sum_{r=ceiling(n/2)..n-1} binomial(r, n-r)*a(r) with a(1) = 1. See [Aspenberg, Perez]. - Michel Marcus, Jun 26 2019