cp's OEIS Frontend

A007858 G.f. is 1 - 1/f(x), where f(x) = 1+x+3*x^2+9*x^3+32*x^4+... is 1/x times g.f. for A063020.

%I A007858 #47 Mar 26 2025 13:26:34
%S A007858 1,2,4,13,44,164,636,2559,10556,44440,190112,824135,3612244,15981632,
%T A007858 71277736,320121747,1446537564,6571858168,30000766128,137544893940,
%U A007858 633051803120,2923867281660,13547594977500,62955434735505,293336372858724,1370149533359784,6414423856436816
%N A007858 G.f. is 1 - 1/f(x), where f(x) = 1+x+3*x^2+9*x^3+32*x^4+... is 1/x times g.f. for A063020.
%C A007858 Number of maximal independent sets in rooted plane trees on n nodes. - _Olivier Gérard_, Jul 05 2001
%H A007858 G. C. Greubel, <a href="/A007858/b007858.txt">Table of n, a(n) for n = 1..1000</a>
%H A007858 Martin Klazar, <a href="http://dx.doi.org/10.1006/eujc.1995.0095">Twelve countings with rooted plane trees</a>, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
%H A007858 A. Mironov and A. Morozov, <a href="https://arxiv.org/abs/2009.11641">Algebra of quantum C-polynomials</a>, arXiv:2009.11641 [hep-th], 2020.
%H A007858 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A007858 a(n+1) = Sum_{k = 1..n} ( binomial(n+k,k)/(n+k)*Sum_{j = 0..k} ( binomial(j,n-k-j+1)*binomial(k,j)*(-1)^(n+k-j+1) ) ) + C(n), where C(n) is a Catalan number. - _Vladimir Kruchinin_, Nov 13 2014
%F A007858 Recurrence: 16*(n-1)*n*(2*n-3)*(17*n^2 - 81*n + 96)*a(n) = (n-1)*(1819*n^4 - 14124*n^3 + 40377*n^2 - 50320*n + 23040)*a(n-1) + 8*(2*n-5)*(4*n-11)*(4*n-9)*(17*n^2 - 47*n + 32)*a(n-2). - _Vaclav Kotesovec_, Nov 14 2014
%F A007858 Asymptotics (Klazar, 1997): a(n) ~ sqrt(5731-4635/sqrt(17)) * ((107+51*sqrt(17))/64)^n / (256 * sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Nov 14 2014
%p A007858 series(1-x/RootOf(_Z-_Z^2-_Z^3+_Z^4-x), x=0,20); # _Mark van Hoeij_, May 28 2013
%t A007858 Rest[CoefficientList[1-x/InverseSeries[Series[x-x^2-x^3+x^4, {x, 0, 20}], x],x]] (* _Vaclav Kotesovec_, Nov 14 2014 *)
%t A007858 Table[Sum[Binomial[n + k, k]/(n + k)*Sum[(Binomial[j, n - k - j + 1]*Binomial[k, j]*(-1)^(n + k - j + 1)), {j, 0, k}], {k, 1, n}] + CatalanNumber[n], {n, 0, 50}] (* _G. C. Greubel_, Feb 15 2017 *)
%o A007858 (PARI) my(x='x+O('x^66)); Vec(1-x/serreverse(x-x^2-x^3+x^4)) \\ _Joerg Arndt_, May 28 2013
%o A007858 (Maxima)
%o A007858 a(n):=sum(binomial(n+k,k)/(n+k)*sum(binomial(j,n-k-j+1)*binomial(k,j)*(-1)^(n+k-j+1),j,0,k),k,1,n)+1/(n+1)*binomial(2*n,n); /* _Vladimir Kruchinin_, Nov 13 2014 */
%Y A007858 Cf. A000108.
%K A007858 nonn
%O A007858 1,2
%A A007858 _Martin Klazar_, Mar 15 1996