Given a cyclical binary string $S$ (i.e., the first and last elements are considered adjacent) with $O$ ones and $Z$ zeros, how many of the permutations of $S$ avoid a run of $N$ (or more) consecutive ones?

I've been toying with generating cases and looking at patterns, having come up with polynomials for $N$=$2$ or $3$, but have not been able to discern any pattern to the coefficients yet.

Is there a more direct combinatorial means to get the desired result?


Here's a first pass at the problem...

As if often the case with cyclical strings, it is useful to mark the "beginning" of the string of length $n$ (giving a so-called necklace with a clasp). Then, after the mark you may have $k$ alternating blocks of zeros and ones. The zeros are unlimited, so the corresponding generating function is $x+x^2+x^3+\cdots=\frac x{1-x}$. The ones are limited by $\ell=\text{your }N-1$, so the corresponding generating function is $x+x^2+\cdots+x^\ell=x\frac{1-x^\ell}{1-x}$. Then, the your desired numbered of strings following the mark would be $$[x^n]\sum_k\left( \frac x{1-x}\cdot\frac{x(1-x^\ell)}{1-x}\right)^k.$$ Of course, it takes some doing to extract the coefficient of any generating function, but in this case it's very doable. After removing the factor of $x^{2k}$, you're left with a product of $\frac1{(1-x)^{2k}}$ and $(1-x^\ell)^k$, giving rise to a sum of a product of two binomial coefficients.

It will take some further consideration (which I am deliberately avoiding) to "remove the clasp".

If you're looking for general descriptions of similar types of pattern-avoidance problems, you should first read the classic paper by Zeilberger and Noonan on the Goulden-Jackson cluster method. More specifically, there is a paper by Wilf and Burnstein that addresses an almost identical question to yours, and a direct generalization of this with the Goulden-Jackson cluster method for cyclic strings.

| cite | improve this answer | |
  • $\begingroup$ Ah, G.J. - I believe you answered an old question of mine and used that method - it answered it perfectly - so I shall pull the additional papers you ref'd and read today - pending a fit, accept on your way. Thanks. $\endgroup$ – rasher Sep 20 '15 at 20:25
  • $\begingroup$ Accept- started reading papers, saw forms of the very polynomials I'd conjured, brought a smile to my face. The last paper looks to fit the bill. Thanks again. $\endgroup$ – rasher Sep 20 '15 at 21:59

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.