A289399 Total path length of the complete ternary tree of height n.

0, 3, 21, 102, 426, 1641, 6015, 21324, 73812, 250959, 841449, 2790066, 9167358, 29893557, 96855123, 312088728, 1000836264, 3196219035, 10169787837, 32252755710, 101988443730, 321655860993, 1012039172391, 3177332285412, 9955641160956, 31137856397031

Offset

0,2

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (7,-15,9).

Formula

From Colin Barker, Jul 05 2017: (Start)

G.f.: 3*x / ((1 - x)*(1 - 3*x)^2).

a(n) = 3*(1 - 3^n + 2*3^n*n) / 4.

a(n) = 7*a(n-1) - 15*a(n-2) + 9*a(n-3) for n>2.

(End)

Example

The complete ternary tree of height two consists of one root node (at depth 0), three children of the root (at depth 1) and 9 leaf nodes (at depth 2). Thus a(2) = 0 + 3*1 + 9*2 = 21.

Prog

(PARI) concat(0, Vec(3*x / ((1 - x)*(1 - 3*x)^2) + O(x^30))) \\ Colin Barker, Jul 05 2017

Crossrefs

Partial sums of A036290.

Sequence in context: A074597 A350726 A241795 * A306093 A076207 A134057

Adjacent sequences: A289396 A289397 A289398 * A289400 A289401 A289402

Keyword

nonn,easy

Author

F. Skerman, Jul 05 2017

Status

approved