%I #44 Aug 17 2024 23:06:37

%S 0,0,6,24,78,240,726,2184,6558,19680,59046,177144,531438,1594320,

%T 4782966,14348904,43046718,129140160,387420486,1162261464,3486784398,

%U 10460353200,31381059606,94143178824,282429536478,847288609440

%N 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.

%C 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

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

%C For n >= 3, this is the number of acyclic orientations of the wheel graph of order n+1. - _Peter Kagey_, Oct 13 2020

%C Number of ternary strings of length n with at least 2 different digits. - _Enrique Navarrete_, Nov 20 2020

%C 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

%H Vincenzo Librandi, <a href="/A058809/b058809.txt">Table of n, a(n) for n = 0..1000</a>

%H Federico Ardila and Laura Escobar, <a href="https://arxiv.org/abs/2006.03078">The harmonic polytope</a>, arXiv:2006.03078 [math.CO], 2020.

%H Allan Bickle, <a href="https://allanbickle.wordpress.com/wp-content/uploads/2016/05/sierpinskigraphpaper2.pdf">Properties of Sierpinski Triangle Graphs</a>, Springer PROMS 448 (2021) 295-303.

%H A. Hinz, S. Klavzar, and S. Zemljic, <a href="https://doi.org/10.1016/j.dam.2016.09.024">A survey and classification of Sierpinski-type graphs</a>, Discrete Applied Mathematics 217 3 (2017), 565-600.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HanoiGraph.html">Hanoi Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/WheelGraph.html">Wheel Graph</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3).

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

%F 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

%F G.f.: 6*x^2 / ((1 - x)*(1 - 3*x)). - _Colin Barker_, Oct 14 2020

%e 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.

%e The level 2 Hanoi graph has 9 vertices, 6 with degree 3, so a(2) = 6.

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

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

%Y Cf. A059116, A059117.

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

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, Jan 03 2001