2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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"].

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

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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.