A067771 Number of vertices in Sierpiński triangle of order n.

3, 6, 15, 42, 123, 366, 1095, 3282, 9843, 29526, 88575, 265722, 797163, 2391486, 7174455, 21523362, 64570083, 193710246, 581130735, 1743392202, 5230176603, 15690529806, 47071589415, 141214768242, 423644304723, 1270932914166

Offset: 0

Author

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

Keywords

• nonn
• easy

Comments

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

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

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

For n >= 1, number of edges in a planar Apollonian graph at iteration n. - Andrew D. Walker, Jul 08 2017

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

Examples

			Order 0 is a triangle, so a(0) = 3.
Order 1 has three corners (degree 2) and three other vertices, so a(1) = 6.
3 example graphs:                        o
                                        / \
                                       o---o
                                      / \ / \
                        o            o---o---o
                       / \          / \     / \
             o        o---o        o---o   o---o
            / \      / \ / \      / \ / \ / \ / \
           o---o    o---o---o    o---o---o---o---o
Graph:      S_1        S_2              S_3
Vertices:    3          6                15
Edges:       3          9                27
		

References

• Peter Wessendorf and Kristina Downing, personal communication.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..600
• Allan Bickle, Properties of Sierpinski Triangle Graphs, Springer PROMS 448 (2021) 295-303.
• Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, 2014.
• A. Hinz, S. Klavzar, and S. Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
• András Kaszanyitzky, Triangular fractal approximating graphs and their covering paths and cycles, arXiv:1710.09475 [math.CO], 2017. See Table 2.
• C. Lanius, Fractals.
• Eric Weisstein's World of Mathematics, Dorogovtsev-Goltsev-Mendes Graph.
• Eric Weisstein's World of Mathematics, Sierpiński Gasket Graph.
• Eric Weisstein's World of Mathematics, Total Domination Number.
• Index entries for linear recurrences with constant coefficients, signature (4,-3).

Crossrefs

Cf. A048473.

Cf. A003462, A007051, A034472, A024023.

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

Programs

Magma

[(3/2)*(1+3^n): n in [0..30]]; // Vincenzo Librandi, Jun 20 2011

Mathematica

LinearRecurrence[{4, -3}, {3, 6}, 26] (* or *)
CoefficientList[Series[3 (1 - 2 x)/((1 - x) (1 - 3 x)), {x, 0, 25}], x] (* Michael De Vlieger, Feb 02 2017 *)
Table[3/2 (3^n + 1), {n, 0, 20}] (* Eric W. Weisstein, Jan 14 2024 *)
3/2 (3^Range[0, 20] + 1) (* Eric W. Weisstein, Jan 14 2024 *)

Formula

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

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

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

a(0) = 3, a(n) = a(n-1) + 3^n. a(n) = (3/2)*(1+3^n). - Zak Seidov, Mar 19 2007

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

G.f.: 3*(1-2*x)/((1-x)*(1-3*x)). - Colin Barker, Jan 10 2012

a(n) = A233774(2^n). - Omar E. Pol, Dec 16 2013

a(n) = 3*a(n-1) - 3. - Zak Seidov, Oct 26 2014

E.g.f.: 3*(exp(x) + exp(3*x))/2. - Stefano Spezia, Feb 09 2021

a(n) = A029858(n+1) + 3. - Allan Bickle, Aug 03 2024

Extensions

More terms from Benoit Cloitre, Feb 22 2002