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

Author

N. J. A. Sloane, Jan 03 2001

Keywords

• nonn
• easy

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

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

A level 1 Hanoi graph is a triangle. Level n+1 is formed from three copies of level n by adding edges between pairs of corner vertices of each pair of triangles. This graph represents the allowable moves in the Towers of Hanoi problem with n disks. a(n) is the number of degree 3 vertices in the level n Hanoi graph. - Allan Bickle, Aug 07 2024

Examples

			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.
The level 2 Hanoi graph has 9 vertices, 6 with degree 3, so a(2) = 6.
		

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.
• Allan Bickle, Properties of Sierpinski Triangle Graphs, Springer PROMS 448 (2021) 295-303.
• A. Hinz, S. Klavzar, and S. Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
• 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).

Crossrefs

Cf. A059116, A059117.

Cf. A000225, A029858, A058809, A375256 (Hanoi graphs).

Programs

Mathematica

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

PARI

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

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