login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

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

Columns k=1-10 give: A000012, A110316, A131889, A131890, A131891, A131892, A131893, A229393, A229394, A229395.

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: A201093 A131255 A198295 * A133607 A103631 A263191

Adjacent sequences:  A221854 A221855 A221856 * A221858 A221859 A221860

KEYWORD

nonn,tabl,look

AUTHOR

Alois P. Heinz, Apr 10 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 21 06:54 EDT 2019. Contains 326162 sequences. (Running on oeis4.)