A381857 Number of n X n binary matrices with at least 2 adjacent 1's.

0, 0, 9, 449, 64302, 33498985, 68713877875, 562948673292362, 18446743413061588661, 2417851638458709952150645, 1267650600226199352445557225326, 2658455991569819662405962686908743173, 22300745198530622979053904922855772969397419

Offset: 0

Author

Benjamin Ghitterman, Mar 08 2025

Keywords

• nonn

Comments

Use black and white square tiles to fill an n X n grid. In some combinations, a black tile will share a side with another black tile. This sequence counts the number of arrangements containing at least one black tile sharing a side with another black tile.

Examples

			For n=1, there are no arrangements with two black tiles touching as there is only space for one tile.
n=2 is a 2 X 2 grid, and there are 9 possible arrangements where at least two black tiles touch on an edge:
  00  01  10  11  01  10  11  11  11
  11, 01, 10, 00, 11, 11, 01, 10, 11.
n=3 is a 3 X 3 grid, and with 2^9=512 possible combinations of black and white tiles, 449 of them have at least two black tiles touching.
		

Crossrefs

Cf. A002416, A006506.

Formula

a(n) = 2^(n^2) - A006506(n).