login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007059 Number of balanced ordered trees with n nodes.
(Formerly M0699)
24
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
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
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.
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
EXAMPLE
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)
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} ]
PROG
(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
CROSSREFS
Sequence in context: A127603 A108351 A038495 * A079500 A108296 A072100
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
More terms from Vladeta Jovovic, Apr 08 2000
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 04:58 EDT 2024. Contains 370952 sequences. (Running on oeis4.)