A007059 Number of balanced ordered trees with n nodes.

0, 1, 1, 2, 3, 5, 8, 14, 24, 43, 77, 140, 256, 472, 874, 1628, 3045, 5719, 10780, 20388, 38674, 73562, 140268, 268066, 513350, 984911, 1892875, 3643570, 7023562, 13557020, 26200182, 50691978, 98182666, 190353370, 369393466, 717457656

Offset: 0

Author

N. J. A. Sloane, Mira Bernstein, R. Kemp

Keywords

• nonn
• nice
• easy

Comments

Essentially the same as A079500: a(0)=0 and a(n)=A079500(n-1) for n >= 1.

Diagonal sums of the "postage stamp" array: for rows n >= -1, column m >= 0 is given by F(n,m) = F(n-1,m) + F(n-2,m) + ... + F(n-m,m) with F(0,m)=1 (m >= 0), F(n,m)=0 (n < 0) and F(n,0)=0 (n > 0). (Rows indicate the required sum, columns indicate the integers available {0,...,m}, entries F(n,m) indicate number of ordered ways sum can be achieved (e.g., n=3, m=2: 3 = 1+1+1 = 1+2 = 2+1 so F(3,2)=3 ways)). - Richard L. Ollerton

Conjecture: for n > 0, a(n+1) is the number of "numbral" divisors of (4^n-1)/3 = A002450(n) (see A048888 for the definition of numbral arithmetic). This has been verified computationally up to n=15. - John W. Layman, Dec 18 2001 [This conjecture follows immediately from Proposition 2.3 of Frosini and Rinaldi. - N. J. A. Sloane, Apr 29 2011]

Also number of Dyck paths of semi-length n-1 with all peaks at the same height. (not mentioned in Frosini reference) - David Scambler, Nov 19 2010

For n >= 1, a(n) is the number of compositions of n where all parts are smaller than the first part, see example. For n >= 1, a(n-1) = A079500(n) is the number of compositions of n where no part exceeds the first part, see the example in A079500. - Joerg Arndt, Dec 29 2012

Examples

			F(-1,0)=0 so a(0)=0. F(0,0)=1, F(-1,1)=0 so a(1)=1. F(1,0)=0, F(0,1)=1, F(-1,2)=0 so a(2)=1. F(2,0)=0, F(1,1)=1, F(0,2)=1, F(-1,3)=0 so a(3)=2.
From _Joerg Arndt_, Dec 29 2012: (Start)
There are a(8)=24 compositions p(1) + p(2) + ... + p(m) = 8 such that p(k) < p(1):
[ 1]  [ 2 1 1 1 1 1 1 ]
[ 2]  [ 3 1 1 1 1 1 ]
[ 3]  [ 3 1 1 1 2 ]
[ 4]  [ 3 1 1 2 1 ]
[ 5]  [ 3 1 2 1 1 ]
[ 6]  [ 3 1 2 2 ]
[ 7]  [ 3 2 1 1 1 ]
[ 8]  [ 3 2 1 2 ]
[ 9]  [ 3 2 2 1 ]
[10]  [ 4 1 1 1 1 ]
[11]  [ 4 1 1 2 ]
[12]  [ 4 1 2 1 ]
[13]  [ 4 1 3 ]
[14]  [ 4 2 1 1 ]
[15]  [ 4 2 2 ]
[16]  [ 4 3 1 ]
[17]  [ 5 1 1 1 ]
[18]  [ 5 1 2 ]
[19]  [ 5 2 1 ]
[20]  [ 5 3 ]
[21]  [ 6 1 1 ]
[22]  [ 6 2 ]
[23]  [ 7 1 ]
[24]  [ 8 ]
(End)
		

References

• Arnold Knopfmacher and Neville Robbins, Compositions with parts constrained by the leading summand, Ars Combin. 76 (2005), 287-295.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 401 terms from T. D. Noe)
• D. Applegate, M. LeBrun, and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
• A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, J. Integer Seq., Vol. 9 (2006), Article 06.3.1.
• R. Kemp, Balanced ordered trees, Random Structures Algorithms, 5 (1994), pp. 99-121.
• Index entries for sequences related to trees

Crossrefs

Cf. A048888, A092921.

Programs

Maple

b:= proc(n, m) option remember; `if`(n=0, 1,
      `if`(m=0, add(b(n-j, j), j=1..n),
      add(b(n-j, min(n-j, m)), j=1..min(n, m))))
    end:
a:= n-> b(n-1, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, May 01 2014

Mathematica

f[ n_, m_ ] := f[ n, m ]=Which[ n>0, Sum[ f[ n-i, m ], {i, 1, m} ], n<0, 0, n==0, 1 ] Table[ Sum[ f[ i, n-i ], {i, 0, n} ], {n, -1, 40} ]

Python

from functools import cache
@cache
def F(k, n):
    return sum(F(k, n-j) for j in range(1, min(k, n))) if n > 1 else n
def A007059(n): return sum(F(k, n+1-k) for k in range(1, n+1))
print([A007059(n) for n in range(36)])  # Peter Luschny, Jan 05 2024

Formula

Define generalized Fibonacci numbers by Sum_{h>=0} F(p, h)z^n = z^(p-1)(1-z)/(1-2z+z^p+1). Then a(n) = 1 + Sum_{h=2..n} F(h-1, n-2).

G.f.: Sum_{k>0} x^k*(1 - 2*x + x^2 + (1-x)*x^(k+1))/(1 - 2*x + x^(k+1)). - Vladeta Jovovic, Feb 25 2003

G.f.: -(1 + x^2 + 1/(x-1))*(1 + x*(x-1)^3*(1-x+x^3)/(Q(0)- x*(x-1)^3*(1-x+x^3))), where Q(k) = (x+1)*(2*x-1)*(1-x)^2 + x^(k+2)*(x + x^2 + x^3 - 2*x^4 - 1 - x^(k+3) + x^(k+5)) - x*(-1 + 2*x - x^(k+3))*(1 - 2*x + x^2 + x^(k+4) - x^(k+5))*(-1 + 4*x - 5*x^2 + 2*x^3 - x^(k+2) - x^(k+5) + 2*x^(k+3) - x^(2*k+5) + x^(2*k+6))/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 14 2013

G.f.: Sum_{n>=1} q^n/(1-q*(1-q^n)/(1-q)) = Sum_{n>=1} q^n/(1 - Sum_{k=1..n} q^k ). - Joerg Arndt, Jan 03 2024

Extensions

More terms from Vladeta Jovovic, Apr 08 2000