A365606 Number of degree 2 vertices in the n-Sierpinski carpet graph.

8, 20, 84, 500, 3540, 26996, 212052, 1684724, 13442772, 107437172, 859182420, 6872514548, 54977282004, 439809752948, 3518452514388, 28147543587572, 225180119118036, 1801440264196724, 14411520047331156, 115292154179921396, 922337214843187668, 7378697662956950900, 59029581136289955924

Offset

1,1

Comments

The level 0 Sierpinski carpet graph is a single vertex. The level n Sierpinski carpet graph is formed from 8 copies of level n-1 by joining boundary vertices between adjacent copies.

Links

Paolo Xausa, Table of n, a(n) for n = 1..1000

Allan Bickle, Degrees of Menger and Sierpinski Graphs, Congr. Num. 227 (2016) 197-208.

Allan Bickle, MegaMenger Graphs, The College Mathematics Journal, 49 1 (2018) 20-26.

Eric Weisstein's World of Mathematics, Sierpiński Carpet Graph

Index entries for linear recurrences with constant coefficients, signature (12,-35,24).

Formula

a(n) = (1/10)*8^n + (16/15)*3^n + 4.

a(n) = 8*a(n-1) - 16*3^(n-2) - 28.

a(n) = 8^n - A365607(n) - A365608(n).

2*a(n) = 2*A271939(n) - 3*A365607(n) - 4*A365608(n).

G.f.: 4*x*(2 - 19*x + 31*x^2)/((1 - x)*(1 - 3*x)*(1 - 8*x)). - Stefano Spezia, Sep 12 2023

Example

The level 1 Sierpinski carpet graph is an 8-cycle, which has 8 degree 2 vertices and 0 degree 3 or 4 vertices.  Thus a(1) = 8.

Mathematica

LinearRecurrence[{12, -35, 24}, {8, 20, 84}, 30] (* Paolo Xausa, Oct 16 2023 *)

Prog

(Python)
def A365606(n): return ((1<<3*n-1)+(3**(n-1)<<4))//5+4 # Chai Wah Wu, Nov 27 2023

Crossrefs

Cf. A001018 (order), A271939 (size).

Cf. A365606 (degree 2), A365607 (degree 3), A365608 (degree 4).

Cf. A009964, A291066, A359452, A359453, A291066, A083233, A332705 (Menger sponge graph).

Sequence in context: A003685 A066011 A333156 * A007016 A129550 A215181

Adjacent sequences: A365603 A365604 A365605 * A365607 A365608 A365609

Keyword

nonn,easy

Author

Allan Bickle, Sep 12 2023

Status

approved