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

1, 1, 5, 41, 469, 6889, 123605, 2620169, 64074901, 1775623081, 54989743445, 1882140936521, 70552399533589, 2874543652787689, 126484802362553045, 5977683917752887689, 301983995802099667861, 16239818347465293071401, 926248570498763547197525, 55847464116157184894240201

Offset: 1

Author

Christian G. Bower

Keywords

• nonn
• eigen

Comments

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

Examples

			D^3(1) = (24*x^2-64*x+41)/(2*x-1)^6. Evaluated at x = 0 this gives a(4) = 41.
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
.
   1a       1a        1b        1a        1b
   |       /  \      /  \      /  \      /  \
   2a     2    3    2    3    3    2    3    2
   |
   3
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• François Bergeron, Philippe Flajolet, and Bruno Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
• Bishal Deb and Alan D. Sokal, Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness, arXiv:2507.18959 [math.CO], 2025. See pp. 6, 16, 30.
• Diego Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions arXiv:math/0501052 [math.CA], 2005.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 89
• John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
• Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See p. 12.
• Index entries for sequences related to mobiles

Crossrefs

Cf. A006351, A032034.

Programs

Maple

Order := 20; t1 := solve(series((ln(1-A)+2*A),A)=x,A); A000311 := n->n!*coeff(t1,x,n);
# With offset 0:
a := n -> add(combinat:-eulerian2(n,k)*2^k,k=0..n):
seq(a(n),n=0..19); # Peter Luschny, Jul 09 2015

Mathematica

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}]
Rest[CoefficientList[InverseSeries[Series[2*x + Log[1-x],{x,0,20}],x],x] * Range[0,20]!] (* Vaclav Kotesovec, Jan 08 2014 *)

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

PARI

N = 66; x = 'x + O('x^N);
Q(k) = if(k>N, 1,  1 + (k+1)*x - 2*x*(k+1)/Q(k+1) );
gf = 1/Q(0); Vec(gf) \\ Joerg Arndt, May 01 2013

PARI

{my(n=20); Vec(serlaplace(serreverse(2*x+log(1-x + O(x*x^n)))))} \\ Andrew Howroyd, Jan 16 2018

Formula

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

E.g.f. A(x) satisfies log(1-A(x))+2*A(x)-x = 0. - Vladeta Jovovic, Dec 06 2002

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

From Peter Bala, Sep 05 2011: (Start)

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.

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)

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

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

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

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

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

a(n) ~ n^(n-1) / (2 * exp(n) * (1-log(2))^(n-1/2)). - Vaclav Kotesovec, Jan 08 2014

a(n) = A032034(n)/2. - Alois P. Heinz, Jul 04 2018

E.g.f: series reversion of 2*x + log(1-x). - Andrew Howroyd, Sep 19 2018