A365608 Number of degree 4 vertices in the n-Sierpinski carpet graph.

0, 4, 100, 1060, 9316, 77092, 624484, 5019172, 40223332, 321996580, 2576602468, 20614709284, 164923342948, 1319403749668, 10555281015652, 84442401180196, 675539668606564, 5404318726347556, 43234553943265636, 345876443943580708, 2767011588741012580, 22136092821505201444, 177088742906772914020

Offset

1,2

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) = (3/10)*8^n - (32/15)*3^n + 4.

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

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

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

G.f.: 4*x^2*(1 + 13*x)/((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) = 0.

Mathematica

LinearRecurrence[{12, -35, 24}, {0, 4, 100}, 30] (* Paolo Xausa, Oct 16 2023 *)

Prog

(Python)
def A365608(n): return ((3<<3*n-1)-(3**(n-1)<<5))//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: A158082 A017090 A029995 * A244352 A173987 A052144

Adjacent sequences: A365605 A365606 A365607 * A365609 A365610 A365611

Keyword

nonn,easy

Author

Allan Bickle, Sep 12 2023

Status

approved