A384764 Number of uniquely solveable n X m nonograms (hanjie), read by antidiagonals.

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 14, 8, 1, 1, 16, 52, 52, 16, 1, 1, 32, 210, 384, 210, 32, 1, 1, 64, 816, 3152, 3152, 816, 64, 1, 1, 128, 3206, 24230, 52362, 24230, 3206, 128, 1, 1, 256, 12536, 189898, 814632, 814632, 189898, 12536, 256, 1, 1, 512, 48962, 1473674, 12819322, 25309575, 12819322, 1473674, 48962, 512, 1

Offset

0,5

Comments

In this game there is an n X m grid where each square may or may not be filled. Each column and each row is labeled by the length of each successive block of filled squares, but without indication of the number of unfilled squares in between. The object is to determine which squares are filled.

Links

Bertram Felgenhauer, Antidiagonals n+m = 0..13, flattened

Bertram Felgenhauer, Counting Nonograms.

Wikipedia, Nonogram.

Formula

Basic properties include A(n,m) = A(m,n), A(n,m) <= 2^(n*m), A(0,n) = A(n,0) = 1, and A(1,n) = A(n,1) = 2^n.

Example

A(2,2) = 16-2 because out of the possible 2^(2*2) grids, only 10/01 and 01/10 have the same row and column clues.
Top left corner of the array:
  1,  1,    1,      1,        1,         1,           1, ...
  1,  2,    4,      8,       16,        32,          64, ...
  1,  4,   14,     52,      210,       816,        3206, ...
  1,  8,   52,    384,     3152,     24230,      189898, ...
  1, 16,  210,   3152,    52362,    814632,    12819322, ...
  1, 32,  816,  24230,   814632,  25309575,   794378773, ...
  1, 64, 3206, 189898, 12819322, 794378773, 49745060669, ...

Crossrefs

Cf. A242876 (main diagonal), A000012 (column m=0), A000079 (column m=1), A383345 (column m=2).

Cf. A385862 (variant: uniquely solveable n X m yesnograms).

Sequence in context: A099594 A255256 A385862 * A328887 A372067 A299906

Adjacent sequences: A384761 A384762 A384763 * A384765 A384766 A384767

Keyword

nonn,tabl,hard

Author

Bertram Felgenhauer, Jun 09 2025

Status

approved