The higher dimensional cases are much more difficult but here is code for 2D. We need some notation and nomenclature. Our notation for the Fibonacci numbers has F0 = 1 and F1 = 2. We use “lite” to describe bit strings and arrays without adjacent 1 bits. There are just Fn lite strings of length n. In a rectangular array a bit is adjacent to just its four nearest neighbors.

Consider 8 × n lite arrays of bits. For n=1 there are already 55 (= F8) such arrays. Let c8nk be the number of lite 8 × n arrays whose right 8 bits form the binary representation of k. We can now compute the 256 c8(n+1)k’s from the 256 c8nk’s. Of these 256 values all but 55 are zero since the right edge, whose bits constitute k, must itself be lite. Each c8(n+1)k is the sum of the c8nm’s for which the bits if k and m are disjoint.

Here is code that computes exactly up to n = 12. It reports x = 397743903151933881 12 by 8 lite arrays. log(x)/log(212*8) = .6090 .

This code finds exactly x = 18396766424410124752958806046933947217821482942 such 16 by 16 configurations. log(x)/log(216*16) = .6003 . Here is its report of the F16 = 2584 counts.

These two calculations include a substantial edge effect since these arrays are embedded in a field of zeros which allows a larger density of 1’s near the edge than inside. Here are some comments on this exact calculation.

We now have information to easily compute the distribution of patterns of bits on a line thru the interior of a randomly selected lite field, or at least the mid-line thru a randomly selected 31 by 16 lite array. A 31 by 16 array can be viewed as two 16 by 16 array sharing one line of 16 bits, the mid-line, which forms an edge to each. Let Nk (= c16,16,k) be the number of lite 16 by 16 arrays whose left edge is k. (We have just calculated Nk for each k.) There are just ∑k Nk2 16 × 31 lite arrays for each such has been counted in just one of these summands. The probability of k as the mid-line thru a random 16 × 31 lite array is proportional to Nk2

To select an array at random

With intermediate counts we can quickly select a random lite n by n array. First choose k from the distribution defined by the cnnk’s. Next redo the sum that produced the particular cnnk for the selected k. Those summands define a distribution for choosing the penultimate column. This continues back to column 0. This tortuous code does just that, with comments.