login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007059 Number of balanced ordered trees with n nodes.
(Formerly M0699)
20
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 (eg 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

T. D. Noe and Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 401 terms from T. D. Noe)

D. Applegate, M. LeBrun, 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

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{2<=h<=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

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} ]

CROSSREFS

Cf. A048888.

Sequence in context: A127603 A108351 A038495 * A079500 A108296 A072100

Adjacent sequences:  A007056 A007057 A007058 * A007060 A007061 A007062

KEYWORD

nonn,nice,easy

AUTHOR

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

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 5 11:43 EST 2021. Contains 349557 sequences. (Running on oeis4.)