login
Number of balanced ordered trees with n nodes.
(Formerly M0699)
24

%I M0699 #65 Jan 05 2024 10:13:59

%S 0,1,1,2,3,5,8,14,24,43,77,140,256,472,874,1628,3045,5719,10780,20388,

%T 38674,73562,140268,268066,513350,984911,1892875,3643570,7023562,

%U 13557020,26200182,50691978,98182666,190353370,369393466,717457656

%N Number of balanced ordered trees with n nodes.

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

%C 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_

%C 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]

%C 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

%C 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

%D Arnold Knopfmacher and Neville Robbins, Compositions with parts constrained by the leading summand, Ars Combin. 76 (2005), 287-295.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A007059/b007059.txt">Table of n, a(n) for n = 0..1000</a> (first 401 terms from T. D. Noe)

%H D. Applegate, M. LeBrun, and N. J. A. Sloane, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Sloane/carry2.html">Dismal Arithmetic</a>, J. Int. Seq. 14 (2011) # 11.9.8.

%H A. Frosini and S. Rinaldi, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Frosini/fros2.html">On the Sequence A079500 and Its Combinatorial Interpretations</a>, J. Integer Seq., Vol. 9 (2006), Article 06.3.1.

%H R. Kemp, <a href="http://dx.doi.org/10.1002/rsa.3240050111">Balanced ordered trees</a>, Random Structures Algorithms, 5 (1994), pp. 99-121.

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F 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).

%F 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

%F 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

%F 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

%e 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.

%e From _Joerg Arndt_, Dec 29 2012: (Start)

%e There are a(8)=24 compositions p(1) + p(2) + ... + p(m) = 8 such that p(k) < p(1):

%e [ 1] [ 2 1 1 1 1 1 1 ]

%e [ 2] [ 3 1 1 1 1 1 ]

%e [ 3] [ 3 1 1 1 2 ]

%e [ 4] [ 3 1 1 2 1 ]

%e [ 5] [ 3 1 2 1 1 ]

%e [ 6] [ 3 1 2 2 ]

%e [ 7] [ 3 2 1 1 1 ]

%e [ 8] [ 3 2 1 2 ]

%e [ 9] [ 3 2 2 1 ]

%e [10] [ 4 1 1 1 1 ]

%e [11] [ 4 1 1 2 ]

%e [12] [ 4 1 2 1 ]

%e [13] [ 4 1 3 ]

%e [14] [ 4 2 1 1 ]

%e [15] [ 4 2 2 ]

%e [16] [ 4 3 1 ]

%e [17] [ 5 1 1 1 ]

%e [18] [ 5 1 2 ]

%e [19] [ 5 2 1 ]

%e [20] [ 5 3 ]

%e [21] [ 6 1 1 ]

%e [22] [ 6 2 ]

%e [23] [ 7 1 ]

%e [24] [ 8 ]

%e (End)

%p b:= proc(n, m) option remember; `if`(n=0, 1,

%p `if`(m=0, add(b(n-j, j), j=1..n),

%p add(b(n-j, min(n-j, m)), j=1..min(n, m))))

%p end:

%p a:= n-> b(n-1, 0):

%p seq(a(n), n=0..40); # _Alois P. Heinz_, May 01 2014

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

%o (Python)

%o from functools import cache

%o @cache

%o def F(k, n):

%o return sum(F(k, n-j) for j in range(1, min(k, n))) if n > 1 else n

%o def A007059(n): return sum(F(k, n+1-k) for k in range(1, n+1))

%o print([A007059(n) for n in range(36)]) # _Peter Luschny_, Jan 05 2024

%Y Cf. A048888, A092921.

%K nonn,nice,easy

%O 0,4

%A _N. J. A. Sloane_, _Mira Bernstein_, R. Kemp

%E More terms from _Vladeta Jovovic_, Apr 08 2000