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.

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,3

Comments

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

Links

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

Jeffrey Barnett, Counting Balanced Tree Shapes.

Formula

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.

Maple

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

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

Crossrefs

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

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

Sequence in context: A157401 A143911 A185422 * A292386 A174287 A186826

Adjacent sequences: A131886 A131887 A131888 * A131890 A131891 A131892

Keyword

easy,nonn,look

Author

Jeffrey Barnett, Jul 24 2007

Status

approved