# Counting the number of Configurations in an Array with Constraints

Consider an array $$\{a_i\}, i=1, ..., N$$ with periodic boundary condition, i.e. $$i\equiv i+N$$. $$a_i\in \{0, 1\}$$. I would like to count the number of configurations of the array $$\{a_i\}$$ satisfying 3 adjacent numbers can not be all 1. i.e., (a_i, a_{i+1}, a_{i+2})=(1, 1, 1) is not allowed. How to count this in Mathematica? Thanks a lot!

A brute-force approach:

ClearAll[f]
f[n_Integer?(# <= 27&)] := Length@Select[FreeQ[Partition[#, 3, 1, {1, 1}], {1, 1, 1}] &]@
Most@Tuples[{0, 1}, n]

Grid[{Range[2 20], f /@ Range[2, 20]}, Dividers -> All] // TeXForm


$$\tiny\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \hline 3 & 7 & 11 & 21 & 39 & 71 & 131 & 241 & 443 & 815 & 1499 & 2757 & 5071 & 9327 & 17155 & 31553 & 58035 & 106743 & 196331 \\ \hline \end{array}$$

Note: For n>27 we get SystemException["MemoryAllocationFailure"].

• Thank you for helping! – user34104 Nov 19 '18 at 19:29
• @user34104, my pleasure. Thank you for the accept and welcome to mma.se. – kglr Nov 19 '18 at 19:33

I think you are looking for the number of binary necklaces of length n with no subsequence 000 (or 111), which is Sloane's A09335. The code given there is the following.

Table[
1/n*Sum[
EulerPhi[n/d]*(d*Sum[Sum[Binomial[j,d-3*k+2*j]*Binomial[k,j],{j,d-3*k,k}]/k,
{k, 1, d}]),
{d, Divisors[n]}],
{n, 20}]


{1, 2, 3, 4, 5, 9, 11, 19, 29, 48, 75, 132, 213, 369, 627, 1083, 1857, 3244, 5619, 9844}

The count initially given by @kglr does not remove duplicates such as {0,1,1,0} and {0,0,1,1}. These are duplicates because of the cyclical necklace condition (if I understood your question correctly).

• Thank you for helping! It is fine to count the permuted configurations as different ones. But your perspective is also very interesting and useful. – user34104 Nov 19 '18 at 19:32