cp's OEIS Frontend

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.

%I A221857 #49 Aug 01 2019 18:21:23
%S A221857 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,
%T A221857 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,
%U A221857 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
%N 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.
%H A221857 Alois P. Heinz, <a href="/A221857/b221857.txt">Antidiagonals n = 0..140, flattened</a>
%H A221857 Jeffrey Barnett, <a href="http://notatt.com/btree-shapes.pdf">Counting Balanced Tree Shapes</a>, 2007
%H A221857 Samuele Giraudo, <a href="https://arxiv.org/abs/1107.3472">Intervals of balanced binary trees in the Tamari lattice</a>, arXiv:1107.3472 [math.CO], Apr 2012
%e A221857 : A(2,2) = 2  : A(2,3) = 3      : A(3,3) = 3          :
%e A221857 :   o     o   :   o    o    o   :   o      o      o   :
%e A221857 :  / \   / \  :  /|\  /|\  /|\  :  /|\    /|\    /|\  :
%e A221857 : o         o : o      o      o : o o    o   o    o o :
%e A221857 :.............:.................:.....................:
%e A221857 : A(3,4) = 6                                          :
%e A221857 :    o        o        o        o       o        o    :
%e A221857 :  /( )\    /( )\    /( )\    /( )\   /( )\    /( )\  :
%e A221857 : o o      o   o    o     o    o o     o   o      o o :
%e A221857 Square array A(n,k) begins:
%e A221857   1, 1, 1,  1,   1,   1,  1,  1,  1,   1,   1, ...
%e A221857   1, 1, 1,  1,   1,   1,  1,  1,  1,   1,   1, ...
%e A221857   0, 1, 2,  3,   4,   5,  6,  7,  8,   9,  10, ...
%e A221857   0, 1, 1,  3,   6,  10, 15, 21, 28,  36,  45, ...
%e A221857   0, 1, 4,  1,   4,  10, 20, 35, 56,  84, 120, ...
%e A221857   0, 1, 4,  9,   1,   5, 15, 35, 70, 126, 210, ...
%e A221857   0, 1, 4, 27,  16,   1,  6, 21, 56, 126, 252, ...
%e A221857   0, 1, 1, 27,  96,  25,  1,  7, 28,  84, 210, ...
%e A221857   0, 1, 8, 81, 256, 250, 36,  1,  8,  36, 120, ...
%p A221857 A:= proc(n, k) option remember; local m, r; if n<2 or k=1 then 1
%p A221857       elif k=0 then 0 else r:= iquo(n-1, k, 'm');
%p A221857       binomial(k, m)*A(r+1, k)^m*A(r, k)^(k-m) fi
%p A221857     end:
%p A221857 seq(seq(A(n, d-n), n=0..d), d=0..12);
%t A221857 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 *)
%Y A221857 Columns k=1-10 give: A000012, A110316, A131889, A131890, A131891, A131892, A131893, A229393, A229394, A229395.
%Y A221857 Rows n=0+1, 2-3, give: A000012, A001477, A179865.
%Y A221857 Diagonal and upper diagonals give: A028310, A000217, A000292, A000332, A000389, A000579, A000580, A000581, A000582, A001287, A001288.
%Y A221857 Lower diagonals give: A000012, A000290, A092364(n) for n>1.
%K A221857 nonn,tabl,look
%O A221857 0,13
%A A221857 _Alois P. Heinz_, Apr 10 2013