A193196 G.f.: A(x) = Sum_{n>=0} x^n / Product_{k=1..n} (1 - k*x^k).

1, 1, 2, 3, 6, 9, 19, 29, 57, 94, 172, 280, 519, 833, 1472, 2433, 4185, 6800, 11666, 18816, 31686, 51340, 84929, 136561, 225476, 359746, 586133, 936243, 1511650, 2397400, 3856698, 6084186, 9711492, 15299490, 24247456, 38016261, 60079125, 93752706, 147284928

Offset: 0

Author

Paul D. Hanna, Jul 17 2011

Keywords

• nonn

Comments

Number of rooted ordered trees with n non-root nodes such that both successive branch heights and the lengths of the branches are weakly increasing; see example. - Joerg Arndt, Aug 27 2014

Examples

			G.f.: A(x) = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 9*x^5 + 19*x^6 + 29*x^7 +...
where:
A(x) = 1 + x/(1-x) + x^2/((1-x)*(1-2*x^2)) + x^3/((1-x)*(1-2*x^2)*(1-3*x^3)) + x^4/((1-x)*(1-2*x^2)*(1-3*x^3)*(1-4*x^4)) +...
From _Joerg Arndt_, Aug 27 2014: (Start)
The a(4) = 5 trees described in the comment are:
:
:     1:
:    [ 1 1 1 1 ]  <--= branch lengths
:    [ 0 0 0 0 ]  <--= branch heights
:
:  O--o
:  .--o
:  .--o
:  .--o
:
:
:     2:
:    [ 1 1 2 ]
:    [ 0 0 0 ]
:
:  O--o
:  .--o
:  .--o--o
:
:
:     3:
:    [ 1 3 ]
:    [ 0 0 ]
:
:  O--o
:  .--o--o--o
:
:
:     4:
:    [ 2 2 ]
:    [ 0 0 ]
:
:  O--o--o
:  .--o--o
:
:
:     5:
:    [ 2 2 ]
:    [ 0 1 ]
:
:  O--o--o
:     .--o--o
:
:
:     6:
:    [ 4 ]
:    [ 0 ]
:
:  O--o--o--o--o
:
See the Arndt link for all examples for 1 <= n <= 7.
(End)
a(6) = 19 because the 11 partitions of 6 with the products as in the comment are
01:  [ 1 1 1 1 1 1 ]   1*1*1*1*1 = 1
02:  [ 1 1 1 1 2 ]     1*1*1*1   = 1
03:  [ 1 1 1 3 ]       1*1*1     = 1
04:  [ 1 1 2 2 ]       1*1*2     = 2
05:  [ 1 1 4 ]         1*1       = 1
06:  [ 1 2 3 ]         1*2       = 1
07:  [ 1 5 ]           1         = 1
08:  [ 2 2 2 ]         2*2       = 4
09:  [ 2 4 ]           2         = 2
10:  [ 3 3 ]           3         = 3
11:  [ 6 ]         (empty prod.) = 1
and the sum of the products is 19. - _Joerg Arndt_, Sep 03 2014
		

Links

• Robert Israel, Table of n, a(n) for n = 0..5627
• Joerg Arndt, trees as in comment for 1<=n<=7

Programs

Maple

N:= 100: # to get all terms up to a(N)
gN:= add(x^n/mul(1-k*x^k,k=1..n),n=0..N):
S:= series(gN,x,N+1):
seq(coeff(S,x,n), n=0..N); # Robert Israel, Aug 28 2014

PARI

{a(n)=my(A=1);polcoeff(sum(m=0,n,x^m/prod(k=1,m,1-k*x^k +x*O(x^n))),n)}

Formula

G.f.: G(0) - 1 where G(k) = 1 + (1-x)/(1-x^k*k)/(1-x/(x+(1-x)/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 22 2013

a(n) = sum( prod(j=2..m, min(C[j-1], C[j]))) where the sum is over all partitions C[1..m] (m parts) of n, see example. - Joerg Arndt, Sep 03 2014

From Vaclav Kotesovec, Jun 18 2019: (Start)

a(n) ~ c * 3^(n/3), where

c = 9390.8440644933535486959046639452060731482141... if mod(n,3)=0

c = 9390.7389359914729419715573277079935321683397... if mod(n,3)=1

c = 9390.7321933046037554603013237581369727858708... if mod(n,3)=2

(End)