login
Number of vertices in Sierpiński triangle of order n.
22

%I #101 Aug 18 2024 14:10:11

%S 3,6,15,42,123,366,1095,3282,9843,29526,88575,265722,797163,2391486,

%T 7174455,21523362,64570083,193710246,581130735,1743392202,5230176603,

%U 15690529806,47071589415,141214768242,423644304723,1270932914166

%N Number of vertices in Sierpiński triangle of order n.

%C An order 0 Sierpiński triangle is a triangle. Order n+1 is formed from three copies of order n by identifying pairs of corner vertices of each pair of triangles. - _Allan Bickle_, Aug 03 2024

%C This sequence represents another link from the product factor space Q X Q / {(1,1), (-1, -1)} to Sierpiński's triangle. The first "link" found was to sequence A048473. - _Creighton Dement_, Aug 05 2004

%C a(n) equals the number of orbits of the finite group PSU(3,3^n) on subsets of size 3 of the 3^(3n)+1 isotropic points of a unitary 3 space. - _Paul M. Bradley_, Jan 31 2017

%C For n >= 1, number of edges in a planar Apollonian graph at iteration n. - _Andrew D. Walker_, Jul 08 2017

%C Also the total domination number of the (n+3)-Dorogovtsev-Goltsev-Mendes graph, using the convention DGM(0) = P_2. - _Eric W. Weisstein_, Jan 14 2024

%D Peter Wessendorf and Kristina Downing, personal communication.

%H Vincenzo Librandi, <a href="/A067771/b067771.txt">Table of n, a(n) for n = 0..600</a>

%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 Paul Bradley and Peter Rowley, <a href="http://eprints.ma.man.ac.uk/2167/01/covered/MIMS_ep2014_42.pdf">Orbits on k-subsets of 2-transitive Simple Lie-type Groups</a>, 2014.

%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 András Kaszanyitzky, <a href="https://arxiv.org/abs/1710.09475">Triangular fractal approximating graphs and their covering paths and cycles</a>, arXiv:1710.09475 [math.CO], 2017. See Table 2.

%H C. Lanius, <a href="http://math.rice.edu/~lanius/fractals/">Fractals</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Dorogovtsev-Goltsev-MendesGraph.html">Dorogovtsev-Goltsev-Mendes Graph</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SierpinskiGasketGraph.html">Sierpiński Gasket Graph</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TotalDominationNumber.html">Total Domination Number</a>.

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

%F a(n) = (3/2)*(3^n + 1).

%F a(n) = 3 + 3^1 + 3^2 + 3^3 + 3^4 + ... + 3^n = 3 + Sum_{k=1..n} 3^n.

%F a(n) = 3*A007051(n).

%F a(0) = 3, a(n) = a(n-1) + 3^n. a(n) = (3/2)*(1+3^n). - _Zak Seidov_, Mar 19 2007

%F a(n) = 4*a(n-1) - 3*a(n-2).

%F G.f.: 3*(1-2*x)/((1-x)*(1-3*x)). - _Colin Barker_, Jan 10 2012

%F a(n) = A233774(2^n). - _Omar E. Pol_, Dec 16 2013

%F a(n) = 3*a(n-1) - 3. - _Zak Seidov_, Oct 26 2014

%F E.g.f.: 3*(exp(x) + exp(3*x))/2. - _Stefano Spezia_, Feb 09 2021

%F a(n) = A029858(n+1) + 3. - _Allan Bickle_, Aug 03 2024

%e Order 0 is a triangle, so a(0) = 3.

%e Order 1 has three corners (degree 2) and three other vertices, so a(1) = 6.

%e 3 example graphs: o

%e / \

%e o---o

%e / \ / \

%e o o---o---o

%e / \ / \ / \

%e o o---o o---o o---o

%e / \ / \ / \ / \ / \ / \ / \

%e o---o o---o---o o---o---o---o---o

%e Graph: S_1 S_2 S_3

%e Vertices: 3 6 15

%e Edges: 3 9 27

%t LinearRecurrence[{4, -3}, {3, 6}, 26] (* or *)

%t CoefficientList[Series[3 (1 - 2 x)/((1 - x) (1 - 3 x)), {x, 0, 25}], x] (* _Michael De Vlieger_, Feb 02 2017 *)

%t Table[3/2 (3^n + 1), {n, 0, 20}] (* _Eric W. Weisstein_, Jan 14 2024 *)

%t 3/2 (3^Range[0, 20] + 1) (* _Eric W. Weisstein_, Jan 14 2024 *)

%o (Magma) [(3/2)*(1+3^n): n in [0..30]]; // _Vincenzo Librandi_, Jun 20 2011

%Y Cf. A048473.

%Y Cf. A003462, A007051, A034472, A024023.

%Y Cf. A007283, A029858, A067771, A193277, A233774, A233775, A246959 (Sierpiński triangle graphs).

%K nonn,easy

%O 0,1

%A Martin Wessendorf (martinw(AT)mail.ahc.umn.edu), Feb 09 2002

%E More terms from _Benoit Cloitre_, Feb 22 2002