A032188 - OEIS

%I #89 Sep 20 2018 00:32:47

%S 1,1,5,41,469,6889,123605,2620169,64074901,1775623081,54989743445,

%T 1882140936521,70552399533589,2874543652787689,126484802362553045,

%U 5977683917752887689,301983995802099667861,16239818347465293071401,926248570498763547197525,55847464116157184894240201

%N Number of labeled series-reduced mobiles (circular rooted trees) with n leaves (root has degree 0 or >= 2).

%C With offset 0, a(n) = number of partitions of the multiset {1,1,2,2,...,n,n} into lists of strictly decreasing lists, called blocks, such that the concatenation of all blocks in a list has the Stirling property: all entries between the two occurrences of i exceed i, 1<=i<=n. For example, with slashes separating blocks, a(2) = 5  counts 1/1/2/2; 1/2/2/1; 2/2/1/1; 1/2/2 1; 2/2 1/1, but not, for instance, 2 1/2/1 because it fails the Stirling test for i=2. - _David Callan_, Nov 21 2011

%H Andrew Howroyd, <a href="/A032188/b032188.txt">Table of n, a(n) for n = 1..200</a>

%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of Increasing Trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.

%H D. Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions</a> arXiv:math/0501052 [math.CA], 2005.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=89">Encyclopedia of Combinatorial Structures 89</a>

%H John Riordan, <a href="/A002720/a002720_3.pdf">Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences</a>. Note that the sequences are identified by their N-numbers, not their A-numbers.

%H <a href="/index/Mo#mobiles">Index entries for sequences related to mobiles</a>

%F Doubles (index 2+) under "CIJ" (necklace, indistinct, labeled) transform.

%F E.g.f. A(x) satisfies log(1-A(x))+2*A(x)-x = 0. - _Vladeta Jovovic_, Dec 06 2002

%F With offset 0, second Eulerian transform of the powers of 2 [A000079]. See A001147 for definition of SET. - _Ross La Haye_, Feb 14 2005

%F From _Peter Bala_, Sep 05 2011: (Start)

%F The generating function A(x) satisfies the autonomous differential equation A'(x) = (1-A)/(1-2*A) with A(0) = 0. Hence the inverse function A^-1(x) = int {t = 0..x} (1-2*t)/(1-t) = 2*x+log(1-x). The expansion of A(x) can be found by inverting the above integral using the method of [Dominici, Theorem 4.1] to arrive at the result a(n) = D^(n-1)(1) evaluated at x = 0, where D denotes the operator g(x) -> d/dx((1-x)/(1-2*x)*g(x)). Compare with A006351.

%F Applying [Bergeron et al., Theorem 1] to the result x = int {t = 0..A(x)} 1/phi(t), where phi(t) = (1-t)/(1-2*t) = 1+t+2*t^2+4*t^3+8*t^4+... leads to the following combinatorial interpretation for this sequence: a(n) gives the number of plane increasing trees on n vertices where each vertex of outdegree k >= 1 can be colored in 2^(k-1) ways. An example is given below. (End)

%F The integral from 0 to infinity w.r.t. w of exp(-2w)(1-z*w)^(-1/z) gives an o.g.f. for the series with offset 0. Consequently, a(n)= sum(j=1 to infinity): St1d(n,j)/(2^(n+j-1)) where St1d(n,j) is the j-th element of the n-th diagonal of A132393 with offset=1; e.g., a(3)= 5 = 0/2^3 + 2/2^4 + 11/2^5 + 35/2^6 + 85/2^7 + ... . - _Tom Copeland_, Sep 15 2011

%F A signed o.g.f., with Γ(v,x) the incomplete gamma function (see A111999 with u=1), is g(z) = (2/z)^(-(1/z)-1) exp(2/z) Γ((1/z)+1,2/z)/z. - _Tom Copeland_, Sep 16 2011

%F With offset 0, a(n) = Sum[T(n+k,k), k=1..n] where T(n,k) are the associated Stirling numbers of the first kind (A008306). For example, a(3) = 41 = 6 + 20 + 15. - _David Callan_, Nov 21 2011

%F a(n) = sum(k=0..n-1, (n+k-1)!*sum(j=0..k, 1/(k-j)!*sum(l=0..j, (2^l*(-1)^(n+l+1)*stirling1(n-l+j-1,j-l))/(l!*(n-l+j-1)!)))), n>0. - _Vladimir Kruchinin_, Feb 06 2012

%F G.f.: 1/Q(0), where Q(k)= 1 + (k+1)*x - 2*x*(k+1)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, May 01 2013

%F a(n) ~ n^(n-1) / (2 * exp(n) * (1-log(2))^(n-1/2)). - _Vaclav Kotesovec_, Jan 08 2014

%F a(n) = A032034(n)/2. - _Alois P. Heinz_, Jul 04 2018

%F E.g.f: series reversion of 2*x + log(1-x). - _Andrew Howroyd_, Sep 19 2018

%e D^3(1) = (24*x^2-64*x+41)/(2*x-1)^6. Evaluated at x = 0 this gives a(4) = 41.

%e a(3) = 5: Denote the colors of the vertices by the letters a,b,c, .... The 5 possible increasing plane trees on 3 vertices with vertices of outdegree k coming in 2^(k-1) colors are

%e .

%e    1a       1a        1b        1a        1b

%e    |       /  \      /  \      /  \      /  \

%e    2a     2    3    2    3    3    2    3    2

%e    |

%e    3

%p Order := 20; t1 := solve(series((ln(1-A)+2*A),A)=x,A); A000311 := n->n!*coeff(t1,x,n);

%p # With offset 0:

%p a := n -> add(combinat:-eulerian2(n,k)*2^k,k=0..n):

%p seq(a(n),n=0..19); # _Peter Luschny_, Jul 09 2015

%t For[y=x+O[x]^21; oldy=0, y=!=oldy, oldy=y; y=((1-y)Log[1-y]+x*y+y-x)/(2y-1), Null]; Table[n!Coefficient[y, x, n], {n, 1, 20}]

%t Rest[CoefficientList[InverseSeries[Series[2*x + Log[1-x],{x,0,20}],x],x] * Range[0,20]!] (* _Vaclav Kotesovec_, Jan 08 2014 *)

%o (Maxima) a(n):=sum((n+k-1)!*sum(1/(k-j)!*sum((2^l*(-1)^(n+l+1)*stirling1(n-l+j-1,j-l))/(l!*(n-l+j-1)!),l,0,j),j,0,k),k,0,n-1); /* _Vladimir Kruchinin_, Feb 06 2012 */

%o (PARI) N = 66; x = 'x + O('x^N);

%o Q(k) = if(k>N, 1,  1 + (k+1)*x - 2*x*(k+1)/Q(k+1) );

%o gf = 1/Q(0); Vec(gf) \\ _Joerg Arndt_, May 01 2013

%o (PARI) {my(n=20); Vec(serlaplace(serreverse(2*x+log(1-x + O(x*x^n)))))} \\ _Andrew Howroyd_, Jan 16 2018

%Y Cf. A006351, A032034.

%K nonn,eigen

%O 1,3

%A _Christian G. Bower_