How to calculate the number of 1 × n*n binary matrices which have no adjacent ones by column, with exactly k ones for large n

Question

How to calculate the number of 1 × n*n binary matrices which have no adjacent ones by column only, with exactly k ones for large n. No adjacent 11 allowed. ex: 1 by 9(n=3), k = 3 ones, no adjacent 11. Possible matrices: 001010010, 10101010, ... total number of sequences = desired value Cannot find the detail of Hard Square Entropy Constant computation which look similar The fibonnaci is involve in generating the possible sequence, but too large number for large n to be useful.

Answer 1

I'm not sure why you restricted the problem to $n*n$ columns. In this answer, I'm going to simply refer to sequences of $n$ values.

If you ignore the possibility of the last element being 1, then the sequence can be composed of two kinds of "tokens": 10 and 0 (1 is always followed by at least one 0.)

If the last element is 1, we can count those possibilities by looking at sequences of n-1 numbers with k-1 1's.

The number of 1's is k, and thus, we must have k 10 tokens, making 2k numbers. Then there's $n-2k$ 0 tokens, and $n-k$ tokens total. There's ${n-k \choose k}$ orders.

That's the sequences not ending in 1. By the same kind of logic, there's ${n-k \choose k-1}$ sequences ending in 1. This gives ${n-k \choose k}+{n-k \choose k-1} = {n-k+1 \choose k}$ total