A131890 -id:A131890 - 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.

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

Alois P. Heinz, Apr 10 2013

			: 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, ...

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

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.

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);

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 *)

A131889 a(n) is the number of shapes of balanced trees with constant branching factor 3 and n nodes. The node is balanced if the size, measured in nodes, of each pair of its children differ by at most one node.

Original entry on oeis.org

1, 1, 3, 3, 1, 9, 27, 27, 81, 81, 27, 27, 9, 1, 27, 243, 729, 6561, 19683, 19683, 59049, 59049, 19683, 177147, 531441, 531441, 1594323, 1594323, 531441, 531441, 177147, 19683, 59049, 59049, 19683, 19683, 6561, 729, 243, 27, 1, 81, 2187, 19683, 531441, 4782969

Offset: 0

Jeffrey Barnett, Jul 24 2007

a(n) is always an integer power of 3.

Alois P. Heinz, Table of n, a(n) for n = 0..1093
Jeffrey Barnett, Counting Balanced Tree Shapes.

Cf. A110316, A131890, A131891, A131892, A131893.

Column k=3 of A221857. - Alois P. Heinz, Apr 17 2013

a:= proc(n) option remember; local m, r; if n<2 then 1 else
      r:= iquo(n-1, 3, 'm'); binomial(3, m) *a(r+1)^m *a(r)^(3-m) fi
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Apr 10 2013

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)]]];
a[n_] := a[n, 3];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

a(0) = a(1) = 1; a(3n+1+m) = (3 choose m) * a(n+1)^m * a(n)^(3-m), where n >= 0 and 0 <= m <= 3.

A131891 a(n) is the number of shapes of balanced trees with constant branching factor 5 and n nodes. The node is balanced if the size, measured in nodes, of each pair of its children differ by at most one node.

Original entry on oeis.org

1, 1, 5, 10, 10, 5, 1, 25, 250, 1250, 3125, 3125, 31250, 125000, 250000, 250000, 100000, 500000, 1000000, 1000000, 500000, 100000, 250000, 250000, 125000, 31250, 3125, 3125, 1250, 250, 25, 1, 125, 6250, 156250, 1953125, 9765625, 488281250, 9765625000

Offset: 0

Jeffrey Barnett, Jul 24 2007

Alois P. Heinz, Table of n, a(n) for n = 0..781
Jeffrey Barnett, Counting Balanced Tree Shapes

Cf. A110316, A131889, A131890, A131892, A131893.

Column k=5 of A221857. - Alois P. Heinz, Apr 17 2013

a:= proc(n) option remember; local m, r; if n<2 then 1 else
      r:= iquo(n-1, 5, 'm'); binomial(5, m) *a(r+1)^m *a(r)^(5-m) fi
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Apr 10 2013

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)]]];
a[n_] := a[n, 5];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

a(0) = a(1) = 1; a(5n+1+m) = (5 choose m) * a(n+1)^m * a(n)^(5-m), where n >= 0 and 0 <= m <= 5.

A131892 a(n) is the number of shapes of balanced trees with constant branching factor 6 and n nodes. The node is balanced if the size, measured in nodes, of each pair of its children differ by at most one node.

Original entry on oeis.org

1, 1, 6, 15, 20, 15, 6, 1, 36, 540, 4320, 19440, 46656, 46656, 699840, 4374000, 14580000, 27337500, 27337500, 11390625, 91125000, 303750000, 540000000, 540000000, 288000000, 64000000, 288000000, 540000000, 540000000, 303750000, 91125000, 11390625, 27337500

Offset: 0

Jeffrey Barnett, Jul 24 2007

Alois P. Heinz, Table of n, a(n) for n = 0..259
Jeffrey Barnett, Counting Balanced Tree Shapes

Cf. A110316, A131889, A131890, A131891, A131893.

Column k=6 of A221857. - Alois P. Heinz, Apr 17 2013

a:= proc(n) option remember; local m, r; if n<2 then 1 else
      r:= iquo(n-1, 6, 'm'); binomial(6, m) *a(r+1)^m *a(r)^(6-m) fi
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Apr 10 2013

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)]]];
a[n_] := a[n, 6];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

a(0) = a(1) = 1; a(6n+1+m) = (6 choose m) * a(n+1)^m * a(n)^(6-m), where n >= 0 and 0 <= m <= 6.

A131893 a(n) is the number of shapes of balanced trees with constant branching factor 7 and n nodes. The node is balanced if the size, measured in nodes, of each pair of its children differ by at most one node.

Original entry on oeis.org

1, 1, 7, 21, 35, 35, 21, 7, 1, 49, 1029, 12005, 84035, 352947, 823543, 823543, 17294403, 155649627, 778248135, 2334744405, 4202539929, 4202539929, 1801088541, 21012699645, 105063498225, 291843050625, 486405084375, 486405084375, 270225046875, 64339296875

Offset: 0

Jeffrey Barnett, Jul 24 2007

Alois P. Heinz, Table of n, a(n) for n = 0..400
Jeffrey Barnett, Counting Balanced Tree Shapes

Cf. A110316, A131889, A131890, A131891, A131892.

Column k=7 of A221857. - Alois P. Heinz, Apr 17 2013

a:= proc(n) option remember; local m, r; if n<2 then 1 else
      r:= iquo(n-1, 7, 'm'); binomial(7, m) *a(r+1)^m *a(r)^(7-m) fi
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Apr 10 2013

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)]]];
a[n_] := a[n, 7];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

a(0) = a(1) = 1; a(7n+1+m) = (7 choose m) * a(n+1)^m * a(n)^(7-m), where n >= 0 and 0 <= m <= 7.

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A131889 a(n) is the number of shapes of balanced trees with constant branching factor 3 and n nodes. The node is balanced if the size, measured in nodes, of each pair of its children differ by at most one node.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A131891 a(n) is the number of shapes of balanced trees with constant branching factor 5 and n nodes. The node is balanced if the size, measured in nodes, of each pair of its children differ by at most one node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A131892 a(n) is the number of shapes of balanced trees with constant branching factor 6 and n nodes. The node is balanced if the size, measured in nodes, of each pair of its children differ by at most one node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A131893 a(n) is the number of shapes of balanced trees with constant branching factor 7 and n nodes. The node is balanced if the size, measured in nodes, of each pair of its children differ by at most one node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula