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.
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
KEYWORD
nonn,eigen
AUTHOR
STATUS
approved