login
A221857
Number A(n,k) of shapes of balanced k-ary trees with n nodes, where a tree is balanced if the total number of nodes in subtrees corresponding to the branches of any node differ by at most one; square array A(n,k), n>=0, k>=0, read by antidiagonals.
10
1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 3, 1, 1, 0, 1, 1, 4, 3, 4, 1, 0, 1, 1, 5, 6, 1, 4, 1, 0, 1, 1, 6, 10, 4, 9, 4, 1, 0, 1, 1, 7, 15, 10, 1, 27, 1, 1, 0, 1, 1, 8, 21, 20, 5, 16, 27, 8, 1, 0, 1, 1, 9, 28, 35, 15, 1, 96, 81, 16, 1, 0, 1, 1, 10, 36, 56, 35, 6, 25, 256, 81, 32, 1, 0
OFFSET
0,13
LINKS
Jeffrey Barnett, Counting Balanced Tree Shapes, 2007
Samuele Giraudo, Intervals of balanced binary trees in the Tamari lattice, arXiv:1107.3472 [math.CO], Apr 2012
EXAMPLE
: A(2,2) = 2 : A(2,3) = 3 : A(3,3) = 3 :
: o o : o o o : o o o :
: / \ / \ : /|\ /|\ /|\ : /|\ /|\ /|\ :
: o o : o o o : o o o o o o :
:.............:.................:.....................:
: A(3,4) = 6 :
: o o o o o o :
: /( )\ /( )\ /( )\ /( )\ /( )\ /( )\ :
: o o o o o o o o o o o o :
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
0, 1, 1, 3, 6, 10, 15, 21, 28, 36, 45, ...
0, 1, 4, 1, 4, 10, 20, 35, 56, 84, 120, ...
0, 1, 4, 9, 1, 5, 15, 35, 70, 126, 210, ...
0, 1, 4, 27, 16, 1, 6, 21, 56, 126, 252, ...
0, 1, 1, 27, 96, 25, 1, 7, 28, 84, 210, ...
0, 1, 8, 81, 256, 250, 36, 1, 8, 36, 120, ...
MAPLE
A:= proc(n, k) option remember; local m, r; if n<2 or k=1 then 1
elif k=0 then 0 else r:= iquo(n-1, k, 'm');
binomial(k, m)*A(r+1, k)^m*A(r, k)^(k-m) fi
end:
seq(seq(A(n, d-n), n=0..d), d=0..12);
MATHEMATICA
a[n_, k_] := a[n, k] = Module[{m, r}, If[n < 2 || k == 1, 1, If[k == 0, 0, {r, m} = QuotientRemainder[n-1, k]; Binomial[k, m]*a[r+1, k]^m*a[r, k]^(k-m)]]]; Table[a[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Apr 17 2013, translated from Maple *)
CROSSREFS
Rows n=0+1, 2-3, give: A000012, A001477, A179865.
Diagonal and upper diagonals give: A028310, A000217, A000292, A000332, A000389, A000579, A000580, A000581, A000582, A001287, A001288.
Lower diagonals give: A000012, A000290, A092364(n) for n>1.
Sequence in context: A131255 A344566 A198295 * A133607 A103631 A374176
KEYWORD
nonn,tabl,look
AUTHOR
Alois P. Heinz, Apr 10 2013
STATUS
approved