cp's OEIS Frontend

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.

%I A058809 #45 Feb 16 2025 08:32:43
%S A058809 0,0,6,24,78,240,726,2184,6558,19680,59046,177144,531438,1594320,
%T A058809 4782966,14348904,43046718,129140160,387420486,1162261464,3486784398,
%U A058809 10460353200,31381059606,94143178824,282429536478,847288609440
%N 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.
%C A058809 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 A058809 For n>=1, a(n) is the number of facets of the harmonic polytope. See Ardila and Escobar. - _Michel Marcus_, Jun 08 2020
%C A058809 For n >= 3, this is the number of acyclic orientations of the wheel graph of order n+1. - _Peter Kagey_, Oct 13 2020
%C A058809 Number of ternary strings of length n with at least 2 different digits. - _Enrique Navarrete_, Nov 20 2020
%C A058809 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 A058809 Vincenzo Librandi, <a href="/A058809/b058809.txt">Table of n, a(n) for n = 0..1000</a>
%H A058809 Federico Ardila and Laura Escobar, <a href="https://arxiv.org/abs/2006.03078">The harmonic polytope</a>, arXiv:2006.03078 [math.CO], 2020.
%H A058809 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 A058809 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 A058809 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HanoiGraph.html">Hanoi Graph</a>
%H A058809 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/WheelGraph.html">Wheel Graph</a>
%H A058809 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3).
%F A058809 For n>0, a(n) = 3^n-3 = 3*a(n-1)+6.
%F A058809 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 A058809 G.f.: 6*x^2 / ((1 - x)*(1 - 3*x)). - _Colin Barker_, Oct 14 2020
%e A058809 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 A058809 The level 2 Hanoi graph has 9 vertices, 6 with degree 3, so a(2) = 6.
%t A058809 Join[{0},NestList[3#+6&,0,30]] (* or *) Join[{0},LinearRecurrence[{4,-3},{0,6},30]] (* _Harvey P. Dale_, Sep 29 2013 *)
%o A058809 (PARI) concat([0,0], Vec(6*x^2 / ((1 - x)*(1 - 3*x)) + O(x^30))) \\ _Colin Barker_, Oct 14 2020
%Y A058809 Cf. A059116, A059117.
%Y A058809 Cf. A000225, A029858, A058809, A375256 (Hanoi graphs).
%K A058809 nonn,easy
%O A058809 0,3
%A A058809 _N. J. A. Sloane_, Jan 03 2001