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

Author

Jeffrey Barnett, Jul 24 2007

Keywords

• easy
• nonn

Links

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

Crossrefs

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

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

Programs

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

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.