|
|
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
|
D. Applegate, M. LeBrun, and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
|
|
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.
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):
|
|
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))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|