A058809 The sequence lambda(3,n), where lambda is defined in A055203. Number of ways of placing n identifiable positive intervals with a total of exactly three starting and/or finishing points.

0, 0, 6, 24, 78, 240, 726, 2184, 6558, 19680, 59046, 177144, 531438, 1594320, 4782966, 14348904, 43046718, 129140160, 387420486, 1162261464, 3486784398, 10460353200, 31381059606, 94143178824, 282429536478, 847288609440

Offset

0,3

Comments

For all n, a(n)=1*3^n-3*1^n+3*0^n-1*0^n [with 0^0=1] where powers are taken of triangular numbers and multiplied by binomial coefficients with alternating signs. - Henry Bottomley, Jan 05 2001

For n>=1, a(n) is the number of facets of the harmonic polytope. See Ardila and Escobar. - Michel Marcus, Jun 08 2020

The number of degree 3 vertices in the n-Hanoi graph. - Allan Bickle, Aug 01 2020

For n >= 3, this is the number of acyclic orientations of the wheel graph of order n+1. - Peter Kagey, Oct 13 2020

Number of ternary strings of length n with at least 2 different digits. - Enrique Navarrete, Nov 20 2020

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Federico Ardila and Laura Escobar, The harmonic polytope, arXiv:2006.03078 [math.CO], 2020.

Eric Weisstein's World of Mathematics, Hanoi Graph

Eric Weisstein's World of Mathematics, Wheel Graph

Index entries for linear recurrences with constant coefficients, signature (4,-3).

Formula

For n>0, a(n) = 3^n-3 = 3*a(n-1)+6.

a(0)=0, a(1)=0, a(2)=6, a(n) = 4*a(n-1)-3*a(n-2). - Harvey P. Dale, Sep 29 2013

G.f.: 6*x^2 / ((1 - x)*(1 - 3*x)). - Colin Barker, Oct 14 2020

Example

a(2)=6 since intervals a-a and b-b can be combined as a-ab-b, a-b-ab, ab-a-b, b-ab-a, b-a-ab, or ab-b-a.

Mathematica

Join[{0}, NestList[3#+6&, 0, 30]] (* or *) Join[{0}, LinearRecurrence[{4, -3}, {0, 6}, 30]] (* Harvey P. Dale, Sep 29 2013 *)

Prog

(PARI) concat([0, 0], Vec(6*x^2 / ((1 - x)*(1 - 3*x)) + O(x^30))) \\ Colin Barker, Oct 14 2020

Crossrefs

Cf. A059116, A059117.

Sequence in context: A276179 A162583 A259662 * A140088 A359133 A011855

Adjacent sequences: A058806 A058807 A058808 * A058810 A058811 A058812

Keyword

nonn,easy

Author

N. J. A. Sloane, Jan 03 2001

Status

approved