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!
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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"].
-
-
$\begingroup$ @user34104, my pleasure. Thank you for the accept and welcome to mma.se. $\endgroup$– kglrNov 19, 2018 at 19:33
$\begingroup$
$\endgroup$
1
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).
-
$\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$ Nov 19, 2018 at 19:32