login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A032188 Number of labeled series-reduced mobiles (circular rooted trees) with n leaves (root has degree 0 or >= 2). 15
1, 1, 5, 41, 469, 6889, 123605, 2620169, 64074901, 1775623081, 54989743445, 1882140936521, 70552399533589, 2874543652787689, 126484802362553045, 5977683917752887689, 301983995802099667861, 16239818347465293071401, 926248570498763547197525, 55847464116157184894240201 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

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

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..200

F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.

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

Index entries for sequences related to mobiles

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

EXAMPLE

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

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

PROG

(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

CROSSREFS

Cf. A006351, A032034.

Sequence in context: A210661 A049119 A305981 * A240996 A143415 A056545

Adjacent sequences:  A032185 A032186 A032187 * A032189 A032190 A032191

KEYWORD

nonn,eigen

AUTHOR

Christian G. Bower

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 13:31 EDT 2018. Contains 316459 sequences. (Running on oeis4.)