3
$\begingroup$

I'm trying to count the number of binary strings of length $n$ with the properties described below. Say we break the string into substrings (starting from left to right) of consecutive $0$'s or $1$'s. We must have:

  1. The first substring can be of any length (from $1$ to $n$).

  2. The last (ending at $n$) substring can be of any appropriate length (namely, a length between $1$ and whatever is left, is allowed).

  3. All the intermediate substrings must have a length of at least $2$.

For example, if $n=10$, the following strings are viable:

$$0111001111$$

$$1110000001$$

$$1001100110$$

This, however, is not allowed: $010...$ or $110001101..$

I've tried to furnish a recursive relation but since there are different constraints on the first and last substrings, the recursion seems to go all the way back to the start.

I'm currently trying to think of this as a question of Stars and Bars and maybe get a (set of) Diophantine equation(s). No luck yet though.

$\endgroup$
  • 5
    $\begingroup$ They're in bijective correspondence with strings of length $n + 2$ where all runs (including the first and last) have length $\geq 2$. $\endgroup$ – Adam P. Goucher Jul 30 '17 at 11:22
  • 1
    $\begingroup$ One of descriptions in A000045 (Fibonacci numbers) explicitly says "F(n) = number of compositions of n+1 with no part equal to 1. [Cayley, Grimaldi]". I think it is easy to find a 1-1 correspondence with your strings. $\endgroup$ – მამუკა ჯიბლაძე Jul 30 '17 at 13:46
  • $\begingroup$ May I ask just what is the value of this investigation? $\endgroup$ – Michael Karas Jul 31 '17 at 4:04
9
$\begingroup$

We start considering words with no consecutive equal characters at all. These words are called Smirnov words or Carlitz words. (See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.)

A generating function for the number of Smirnov words over a binary alphabet is given by \begin{align*} \left(1-\frac{2z}{1+z}\right)^{-1}\tag{1} \end{align*}

To only get words with runs of length at least $2$ we replace in (1) each occurrence of $z$ by \begin{align*} z&\longrightarrow z^2+z^3+\cdots=\frac{z^2}{1-z}\\ \end{align*}

Doubling first and last character of a word implies we can focus on words containing solely of subword runs with length $\geq 2$ and the wanted number of occurrences of words of length $n$ is

\begin{align*} [z^{n+2}]&\left(1-\frac{2\frac{z^2}{1-z}}{1+\frac{z^2}{1-z}}\right)^{-1} =[z^{n+2}]\frac{1-z+z^2}{1-z-z^2}\tag{2} \end{align*}

with $\frac{1}{1-z-z^2}$ the generating function of the Fibonacci numbers $F_n$. We obtain from (2) the sequence \begin{align*} (F_{n+3}-F_{n+2}+F_{n+1})_{n\geq 1} &=\left(2F_{n+1}\right)_{n\geq 1}\\ &=(2,4,6,10,16,26,42,\ldots) \end{align*}

$\endgroup$
  • $\begingroup$ Thanks a lot for the answer. Something strikes me as a bit weird though: For $n=4$, don't we have: $(0011)$, $(1100)$, $(1001)$, $(0110)$, $(1000)$, $(0111)$, $(0001)$ and $(1110)$, all being valid? Think doesn't correspond to the value 6 above. Am I missing something? $\endgroup$ – AD1984 Jul 30 '17 at 14:02
  • 1
    $\begingroup$ @AD1984: Typo corrected. Thanks. There are $10$ admissible words for $n=4$ which are $0000,0001,0011,0110,0111,1000,1001,1100,1110,1111$. $\endgroup$ – Markus Scheuer Jul 30 '17 at 14:18
  • $\begingroup$ Yes, I got it now. Perfect. $\endgroup$ – AD1984 Jul 30 '17 at 14:19
  • $\begingroup$ @AD1984: You're welcome! :-) $\endgroup$ – Markus Scheuer Jul 30 '17 at 14:20
  • 1
    $\begingroup$ @AD1984: It does not account. We respect the special boundary conditions by looking for words of length $n+2$ instead of $n$ as indicated by the coefficient of operator $[z^{n+2}]$. We look at these words of length $n+2$ and skip the first and last character. This way we obtain all admissible words of length $n$. $\endgroup$ – Markus Scheuer Jul 30 '17 at 14:32
11
$\begingroup$

An answer has already been given, but let me additionally give you a meta-answer: the constraints you describe define a rational language on the alphabet $\{0,1\}$, namely a set of words (=finite strings) on this alphabet which can be described by a regular expression or finite automaton. In your case, a regular expression is easily described: $$ 00^*(111^*000^*)^*111^*00^* + 00^*(111^*000^*)^*11^* + 11^*(000^*111^*)^*00^* + 11^*(000^*111^*)^*000^*11^* + 0^* + 1^* $$ where "$^*$" means "any number (at least zero) of", and "$+$" (sometimes written "$|$") means "or" (the cases in the above sum are, moreover, disjoint: the first four describe the four cases where your string begins with $0$ and ends with $0$, begins with $0$ and ends with $1$, etc., and the last two make a special case of the sequences with just zeros or just ones — you might wish to add $\varepsilon$ to the expression if you consider the empty string to match your condition).

Now there are well known algorithms which will

  • take a regular expression such as above and turn it into a finite automaton recognizing the language,

  • turn this finite automaton into a deterministic one,

  • compute the generating function of the language generated by a deterministic finite automaton.

Any book on rational languages or finite automata (e.g., the one by Sakarovitch¹) should discuss at least the first two and probably all three; the third is also discussed, e.g., here.

Alternatively, you can go through the "unambiguous regular expression" path, as discussed here: I don't know which is algorithmically more efficient in general, but in the case of your particular question, this works very well, as the above regular expression is unambiguous, and the procedure described here immediately produces the rational function $2\frac{x+x^2}{1-x-x^2}$.

My point is, this answers not only your particular question, but all questions about counting (or at least, producing a generating function for) the number of words described by any rational expression. Furthermore, these algorithms are actually implemented in the Vaucanson/Vaucanson2/Vaucanson-R/Wali/VCSN programs¹ (none of which are terribly usable at the present, unfortunately).

  1. Full disclosure: Sakarovitch is my office neighbour.
$\endgroup$
  • 2
    $\begingroup$ Note that the generating function of the Catalan numbers -- which count words of balanced parentheses such as (()())()(()) -- is not a rational function. The contrapositive of your answer thus implies, correctly, that no regular expression can verify whether a word of parentheses is balanced. $\endgroup$ – Adam P. Goucher Jul 30 '17 at 18:34
  • 1
    $\begingroup$ @ Gro-Tsen: Interesting. This is a kind of `constraint coding' perspective on the problem. Define the constrained language via a finite-state machine and proceed from there. The (asymptotic) capacity of the system, i.e., the $\limsup_{n\to\infty}\frac{1}{n}\log|\mathcal{C}_n|$, where $\mathcal{C}_n$ is the set of viable words of length $n$, is extremely easy to get. Namely, it is the $log$ of the largest eigenvalue of the adjacency matrix (through the Perron–Frobenius theorem). For my case (and in correspondence to the provided answers), we get the logarithm of the Golden Ration as the answer. $\endgroup$ – AD1984 Jul 31 '17 at 10:26
  • $\begingroup$ @AD1984 Could you give a reference for this constraint coding method with finite-state machines? I suspect I could use it for some of my own questions here (namely mathoverflow.net/q/201205/41291, mathoverflow.net/q/200762/41291 and mathoverflow.net/q/146802/41291). $\endgroup$ – მამუკა ჯიბლაძე Aug 1 '17 at 9:06
  • 1
    $\begingroup$ @მამუკა ჯიბლაძე: A decent (online version of a) book on the topic of constrained coding would be math.ubc.ca/~marcus/Handbook. In particular, you should take a look at Chapter 4: Finite-State Encoders. The explanations on how to define the appropriate finite-state machine should be there. $\endgroup$ – AD1984 Aug 2 '17 at 11:32
  • $\begingroup$ I would like to add that Graham, Knuth, Patashnik, Concrete mathematics chapter 7 gives some practical examples for the third step in a popular way, although it mostly concentrates on the fourth step, computing an explicit formula of the terms from the generating function. $\endgroup$ – Zsbán Ambrus Aug 27 '17 at 19:52
3
$\begingroup$

Call strings in which all runs are of length at least 2 "duplicative strings".

Note that a duplicative string of length $n + 2$ either ends in a run of length exactly 2 or a run of length greater than 2. In the former case, it can be any duplicative string of length $n$, followed by the two characters opposite from this one's last character (assume here $n$ is positive). In the latter case, it can be any duplicative string of length $n + 1$ with its last character duplicated.

Thus, if we denote the number of duplicative strings of length $n + 2$ by $F(n + 2)$, we obtain the Fibonacci-type recurrence $F(n + 2) = F(n) + F(n + 1)$ for positive $n$.

This along with the obvious initial values $F(1) = 0$, $F(2) = 2$, and the observation made by others that the strings you are interested in are (by duplicating initial and final characters for those of length at least 1) in correspondence with duplicative strings of length $n + 2$, makes quick work of the problem. We have that $F(n)$ is twice the $(n - 1)$-th Fibonacci number (on the indexing whose $0$-th and $1$-st Fibonacci numbers are $0$ and $1$, respectively), and that the quantity you are interested in is $F(n + 2)$ (for positive $n$), which is therefore twice the $(n + 1)$-th Fibonacci number.

$\endgroup$
  • $\begingroup$ This is exactly how I ended up counting the strings with runs of length $\geq 2$. A neat and simple combinatoric argument. Thanks! $\endgroup$ – AD1984 Jul 31 '17 at 10:21

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.