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