Several decades ago a friend of mine, Garret Boer, was trying to compute the specific heat of ice by counting how many ways a block of ice could arrange its water molecules so that there was just one hydrogen atom between each pair of neighboring oxygen atoms. The oxygen atoms were held fixed.

A simpler problem is to count how many arrays of bits conform to some local property. How many 10 by 10 arrays of bits are such that no two adjacent bits are 1? We use “lite” here to describe bit strings and arrays without adjacent 1 bits. These numbers are too vast to consider simple counting even with powerful computers. Planar Lattice Gases with Nearest-Neighbor Exclusion seems to study the same problem but I have not read it. Similar stuff Communications on Hard Square Entropy Constant was online but not just now. Here are results on a similar problem. THE HARD SQUARE ENTROPY CONSTANT is something that is now online, with a bibliography, and gives a history of the problem. For some purposes it is sufficient to select random elements from this set.

See too the Hard Square Entropy Constant.

Wire stylus printers were driven by digital logic that would drive a stylus, or not, about 200 times per second, but it was mechanically forbidden to drive a stylus on consecutive times. How many timing patterns for a given stylus were possible for the maximum width character? How many 20 bit strings are without consecutive 1’s? There are F20, the 20th Fibonacci number. Here is why. This answer bore on the cost of the ROM holding the printer’s font memory.

Here are some ideas for producing random samples from these populations. They are flawed but fixable, I think.

There are schemes for exact results for small 2D arrays. Here we describe calculations of the exact count of patterns for 8 by 12, and 16 by 16 arrays which exclude neighboring 1’s. For those log(count of confined patterns)/log(unconfined patterns) = .6644 and .6375 respectively.

Here is code to count lite n by n arrays up to 16. Change the definition of fb, then compile and run program.

The trick described here solves the selection problem for smallish arrays.