A395943 Number of tilings of an n X n grid by 1 X p rectangles using the prime partitions of n^2 into prime parts p <= n, counting distinct symmetry variants.

1, 0, 2, 14, 184, 16906, 2442118, 1435139134, 2019636259814, 7941042712515578

Offset

0,3

Comments

For each prime partition of n^2 into prime parts p <= n, tile an n X n grid using one 1 X p rectangle for each part p in the partition.

Rectangles may be placed horizontally or vertically.

Rotations and reflections of a tiling are counted when distinct.

A395942 counts the corresponding tilings up to rotation and reflection.

For n = 2..8, the ratio A395943(n)/A395942(n) increases toward 8.

Links

Table of n, a(n) for n=0..9.

Sean A. Irvine, Java program (github)

Chuck Seggelin, GitHub Repository containing source code used to compute the terms of A395941, A395942, and A395943, and a slide deck describing the technical challenges in the implementation.

Example

a(3) = 14 because there are 12 distinct symmetry variants of tilings of a 3 X 3 grid with three 1 X 2 rectangles and one 1 X 3 rectangle, and 2 distinct symmetry variants of tilings with three 1 X 3 rectangles. Thus 12 + 2 = 14.

Crossrefs

Cf. A000607, A254127, A395941, A395942.

Sequence in context: A370940 A237852 A219874 * A074655 A381478 A268005

Adjacent sequences: A395940 A395941 A395942 * A395944 A395945 A395946

Keyword

nonn,more

Author

Chuck Seggelin, May 11 2026

Extensions

a(9) from Sean A. Irvine, May 18 2026

Status

approved