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

Author

Allan Bickle, Sep 12 2023

Keywords

• nonn
• easy

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.

Examples

			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.
		

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).

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).

Programs

Mathematica

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

Python

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

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