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

Author

F. Skerman, Jul 05 2017

Keywords

• nonn
• easy

Examples

			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.
		

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (7,-15,9).

Crossrefs

Partial sums of A036290.

Programs

PARI

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

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)