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,3

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.

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

Example

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

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

Prog

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

Crossrefs

Cf. A122888.

Sequence in context: A337000 A074059 A177401 * A185324 A135882 A143740

Adjacent sequences: A171789 A171790 A171791 * A171793 A171794 A171795

Keyword

nonn

Author

Paul D. Hanna, Jan 25 2010

Status

approved