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.
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
Examples
: 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, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..140, flattened
- 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
Crossrefs
Programs
-
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 *)