A131890 a(n) is the number of shapes of balanced trees with constant branching factor 4 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.

1, 1, 4, 6, 4, 1, 16, 96, 256, 256, 1536, 3456, 3456, 1296, 3456, 3456, 1536, 256, 256, 96, 16, 1, 64, 1536, 16384, 65536, 1572864, 14155776, 56623104, 84934656, 905969664, 3623878656, 6442450944, 4294967296, 17179869184, 25769803776, 17179869184, 4294967296

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1365

Jeffrey Barnett, Counting Balanced Tree Shapes

Formula

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

Maple

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

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

Crossrefs

Cf. A110316, A131889, A131891, A131892, A131893.

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

Sequence in context: A010670 A240444 A199358 * A062751 A135911 A164356

Adjacent sequences: A131887 A131888 A131889 * A131891 A131892 A131893

Keyword

easy,nonn

Author

Jeffrey Barnett, Jul 24 2007

Status

approved