|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,13
|
|
LINKS
|
|
|
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
|
Diagonal and upper diagonals give: A028310, A000217, A000292, A000332, A000389, A000579, A000580, A000581, A000582, A001287, A001288.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|