login
This site is supported by donations 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)
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 (r.ollerton(AT)uws.edu.au)

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)

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

License Agreements, Terms of Use, Privacy Policy .

Last modified March 22 22:17 EDT 2017. Contains 283901 sequences.