A171792 - OEIS

%I #32 Sep 09 2020 18:15:09

%S 1,1,2,7,34,214,1652,15121,160110,1925442,25924260,386354366,

%T 6314171932,112286067892,2158562109096,44605949528355,986049177712850,

%U 23218586050641090,580198948211652348,15334750335623526670,427408226085246086676,12528910074528593086980

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

%H Alois P. Heinz, <a href="/A171792/b171792.txt">Table of n, a(n) for n = 1..425</a> (first 140 terms from Vaclav Kotesovec)

%H Magnus Aspenberg, Rodrigo Perez, <a href="https://arxiv.org/abs/1006.1340">Control of cancellations that restrain the growth of a binomial recursion</a>, arXiv:1006.1340 [math.CO], 2010; DOI:<a href="https://doi.org/10.1007/s12220-014-9489-y">10.1007/s12220-014-9489-y</a>, The Journal of Geometric Analysis, Vol. 25, No. 3 (2015), 1666-1700.

%H Olivier Bodini, Antoine Genitrini, Bernhard Gittenberger, <a href="https://arxiv.org/abs/1809.04314">On the number of increasing trees with label repetitions</a>, arXiv:1809.04314 [math.CO], 2018.

%H Olivier Bodini, Antoine Genitrini, Cécile Mailler, Mehdi Naima, <a href="https://hal.archives-ouvertes.fr/hal-02865198">Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study</a>, hal-02865198 [math.CO] / [math.PR] / [cs.DS] / [cs.DM], 2020.

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

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

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

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

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

%e A(x+x^2) = x + 2*x^2 + 4*x^3 + 14*x^4 + 68*x^5 + 428*x^6 + ...

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

%o (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))}

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

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

%Y Cf. A122888.

%K nonn

%O 1,3

%A _Paul D. Hanna_, Jan 25 2010