Let us fix an alphabet $\Sigma$ of size $c$, then we have the finite language $\Sigma^n$ which is the set of all $n$ length words. For each $N,M$ how many words are there in $\Sigma^n$ such that no sequence of $N$ characters repeats $M$ times in a row?For instance with N=2 and M=3101010 would not be counted, but 111010 would beHere is some data I found on it with a simulation:c n N M total percent2,4,2,2,10,0.6252,5,2,2,16,0.52,6,2,2,26,0.406252,6,3,2,48,0.752,6,2,3,48,0.752,7,2,2,42,0.3281252,7,3,2,88,0.68752,7,2,3,88,0.68752,8,2,2,68,0.2656252,8,3,2,162,0.63281252,8,4,2,216,0.843752,8,2,3,162,0.63281252,8,2,4,216,0.843752,9,2,2,110,0.214843752,9,3,2,298,0.582031252,9,4,2,416,0.81252,9,2,3,298,0.582031252,9,3,3,416,0.81252,9,2,4,416,0.81252,10,2,2,178,0.1738281252,10,3,2,548,0.535156252,10,4,2,802,0.7832031252,10,5,2,928,0.906252,10,2,3,548,0.535156252,10,3,3,802,0.7832031252,10,2,4,802,0.7832031252,10,2,5,928,0.906253,4,2,2,66,0.81481481481481483,5,2,2,180,0.74074074074074073,6,2,2,492,0.67489711934156383,6,3,2,666,0.91358024691358023,6,2,3,666,0.91358024691358023,7,2,2,1344,0.61454046639231833,7,3,2,1944,0.88888888888888883,7,2,3,1944,0.88888888888888883,8,2,2,3672,0.55967078189300413,8,3,2,5676,0.86511202560585283,8,4,2,6318,0.96296296296296293,8,2,3,5676,0.86511202560585283,8,2,4,6318,0.96296296296296293,9,2,2,10032,0.5096784026825183,9,3,2,16572,0.84194482548392013,9,4,2,18792,0.95473251028806583,9,2,3,16572,0.84194482548392013,9,3,3,18792,0.95473251028806583,9,2,4,18792,0.95473251028806583,10,2,2,27408,0.46415688665345733,10,3,2,48384,0.8193872885230913,10,4,2,55896,0.94660366814001933,10,5,2,58158,0.98491083676268863,10,2,3,48384,0.8193872885230913,10,3,3,55896,0.94660366814001933,10,2,4,55896,0.94660366814001933,10,2,5,58158,0.98491083676268864,4,2,2,228,0.8906254,5,2,2,864,0.843754,6,2,2,3276,0.79980468754,6,3,2,3936,0.96093754,6,2,3,3936,0.96093754,7,2,2,12420,0.7580566406254,7,3,2,15552,0.949218754,7,2,3,15552,0.949218754,8,2,2,47088,0.7185058593754,8,3,2,61452,0.937683105468754,8,4,2,64704,0.98730468754,8,2,3,61452,0.937683105468754,8,2,4,64704,0.98730468754,9,2,2,178524,0.68101501464843754,9,3,2,242820,0.92628479003906254,9,4,2,258048,0.9843754,9,2,3,242820,0.9262847900390625The values seem to go to $c^n$ as $N,M$ increase and appear to be a function of $c$, $N+M$. It also seems to decrease as you increase $n$ and increase as you increase $c$. This all makes intuitive sense to me. If I had to guess I would say it is exponential in $n$, polynomial in $c$, and exponential in $N+M$A secondary question I have is how would you represent the language defined by just the strings counted.
How many restricted length strings are there without significant repetitions
formal languages;word combinatorics