Counting Palindromic Binary Strings Without r-Runs of Ones

M. A. Nyblom School of Mathematics and Geospatial Science RMIT University Melbourne, Victoria 3001 Australia

                  michael.nyblom@rmit.edu.au

Abstract

A closed-form expression is derived for the enumeration of all palindromic binary strings of length n > r having no r-runs of 1’s, in terms of the r-Fibonacci sequence. A similar closed-form expression for the number of zeros contained in all such palindromic binary strings is derived in terms of the number of zeros contained in all binary strings having no r-runs of 1’s.

1 Introduction

Grimaldi [2] and Hayes [5] have noted the well-known fact that the number of binary strings of length n, in which there are no consecutive 1’s is given by F_{n+2}, where F_{n} denotes the n-th Fibonacci number generated from the difference equation F_{n} = F_{n−1} + F_{n−2}, for n ≥ 2, with F_{0} = 0 and F_{1} = 1. Thus for binary strings of length, say n = 3, there are exactly F_{5} = 5 binary strings in which there are no consecutive 1’s, namely 000, 001, 010, 100 and 101. The property of a binary string having no consecutive 1’s (or equivalently no consecutive zeros), can easily be generalized to the property that a binary string has no substrings of length r consisting of r consecutive ones, where r is a fixed integer greater than or equal to 2. We shall refer to this property in short, by saying that a binary string has no r-runs of 1’s. Both the author [6] and Bollinger [1] showed that the number of such binary strings is given by U_{n+r}, where {U_{n}} denotes the well-known r-Fibonacci sequence generated by the r-th order linear difference equation U_{n} = ∑_{i=1}^{r} U_{n−i}, for n ≥ r, with U_{0} = U_{1} = ⋯ = U_{r−2} = 0 and U_{r−1} = 1.

In this paper we shall first be concerned with counting the number of palindromic binary strings, having no r-runs of 1’s. Letting P_{r}(n) denote the number of such binary strings having length n > r ≥ 2, we will show that

P_{r}(n) = \begin{cases}∑_{i=0}^{⌊ \frac{r−1+(−1)^{r+1}}{2} ⌋} U_{\frac{n}{2} +r−1−i}, & if n even; \\ ∑_{i=−1}^{⌊ \frac{r−2+(−1)^{r}}{2} ⌋} U_{\frac{n−1}{2} +r−1−i}, & if n odd. \end{cases}  (1)

where {U_{n}} is the r-Fibonacci sequence. Thus for example when r = 2 and so U_{n} = F_{n}, then the number of palindromic binary strings of length, say n = 3, having no consecutive 1’s, would be P_{2}(3) = F_{3} + F_{2} = 2 + 1 = 3, namely 000, 101 and 010.

In addition to establishing the closed-form expression for P_{r}(n) in Section 2, we shall also address the problem of enumerating the total number of zeros contained in the P_{r}(n) palindromic strings. Such a characteristic was studied by Grimaldi et al. [3, 4] for both binary and ternary strings, as well as their palindromic counterparts, and was expressed in terms of Fibonacci and Lucas numbers. In the case of the palindromic binary strings in question, we shall approach the problem of enumerating the number of zeros, by first deriving an r-th order non-homogeneous difference equation for the number of zeros, denoted Z_{r}(n), in all U_{n+r} binary strings of length n ≥ 1 having no r-runs of 1’s. By employing a similar argument used to derive P_{r}(n), we shall then in Section 3 produce a closed-form expressions in the style of (1) for the number of zeros contained in all P_{r}(n) palindromic binary strings, in terms of the characteristic Z_{r}(·) and the r-Fibonacci sequence U_{n}.

2 Main result

To begin we note that all palindromic binary string of length n ≤ r will have no r-runs of 1’s, with the exception of the string \underbrace{11 ⋯ 11}_{r 1’s}. Thus as the number of palindromic binary

strings of length n is 2^{\frac{2n+1+(−1)^{n+1}}{4}} , we have P_{r}(n) = 2^{\frac{2n+1+(−1)^{n+1}}{4}} for 1 ≤ n < r and P_{r}(r) =

2^{\frac{2r+1+(−1)^{r+1}}{4}} − 1. To establish the closed-form expression for P_{r}(n), when n > r, we will require the following technical lemma.

Lemma 1. Given an integer r ≥ 1, then max\{s ∈ ℤ : 2s + 1 < r\} = ⌊\frac{r−2+(−1)^{r}}{2} ⌋ and

max\{s ∈ ℤ : 2s < r\} = ⌊\frac{r−1+(−1)^{r+1}}{2} ⌋.

Proof. By definition of the floor function ⌊·⌋, the largest s ∈ ℤ such that 2s + 1 ≤ r is ⌊\frac{r−1}{2}⌋. Now if r is even then 2⌊\frac{r−1}{2}⌋ + 1 < r, while if r is odd then ⌊\frac{r−1}{2}⌋ − 1 = ⌊\frac{r−3}{2}⌋ will be such that 2⌊\frac{r−3}{2}⌋ + 1 < r. By inspection we see the first formula reduces to both these cases. A similar argument establishes the second formula.

We now establish the closed-form expression for P_{r}(n) when n > r.

Theorem 2. The number of palindromic binary strings of length n > r ≥ 2 having no r-runs of 1’s is given by

P_{r}(n) = \begin{cases}∑_{i=0}^{⌊ \frac{r−1+(−1)^{r+1}}{2} ⌋} U_{\frac{n}{2} +r−1−i}, & if n even; \\ ∑_{i=−1}^{⌊ \frac{r−2+(−1)^{r}}{2} ⌋} U_{\frac{n−1}{2} +r−1−i}, & if n odd. \end{cases}

where {U_{n}} is the r-Fibonacci sequence.

Proof. We first note that all palindromic binary strings of an even length n = 2m, are constructed by concatenating to the left of a binary string with its mirror image of length m. Similarly all palindromic binary strings of an odd length n = 2m + 1, are constructed by concatenating to the right and left of a central entry, containing either a 0 or 1, a binary string of length m and its mirror image respectively.

Mirror String of Length m Binary String of Length m
Mirror String of Length m 0/1 Binary String of Length m

Table 1: Even and odd length palindromic binary strings

Thus all palindromic binary strings in question are constructed in this manner, using the binary strings having no r-runs of 1’s, provided that a possible resulting central substring consisting entirely of 1’s does not exceed or reach a length equal to r. With this in mind we further observe that for a fixed integer r ≥ 2, the set of U_{n+r} binary strings of length n > r having no r-runs of 1’s, can be partitioned into r disjoint sets containing those binary strings whose left-hand entries are 0, 10, 110, …, \underbrace{11 ⋯ 1}_{(r−1) 1’s} 0 respectively. We now examine

more closely the construction of the even and odd length palindromic binary strings in question.

Case 1: Even Length n = 2m > r.

In this instance, if the right binary string of length m has a left-hand entry of 0, then the remaining binary string of length m − 1 cannot contain r-runs of 1’s, and so there must be U_{m−1+r} such strings in total. Similarly, if the right binary string of length m has a left-hand entry of \underbrace{11 ⋯ 1}_{s 1’s} 0, where 1 ≤ s < r, then the remaining binary string of length m − s − 1

cannot contain r-runs of 1’s, and so there must be U_{m−s−1+r} such strings in total.

Now if r = 2, then the set of binary strings having a left-hand entry of 10 cannot be used to construct the palindromic binary strings in question, as this would result in a central substring of 11, and so P_{2}(2m) = U_{m+1}. However, if r > 2, then both the above sets of binary strings can be used, provided the binary strings having the left-hand entry of \underbrace{11 ⋯ 1}_{s 1’s} 0 are

Mirror String of Length m − 1 0 0 String of Length m − 1
Mirror String of Length m − s − 1 01 ⋯ 11 11 ⋯ 10 String of Length m − s − 1

Table 2: Even length palindromic binary strings having no r-runs of 1’s

such that 2s < r. Thus by Lemma 1 we conclude 1 ≤ s ≤ ⌊\frac{r−1+(−1)^{r+1}}{2} ⌋, and so

P_{r}(2m) = U_{m−1+r} + ∑_{s=1}^{⌊ \frac{r−1+(−1)^{r+1}}{2} ⌋} U_{m−s−1+r} = ∑_{i=0}^{⌊ \frac{r−1+(−1)^{r+1}}{2} ⌋} U_{\frac{n}{2} +r−1−i} ,  (2)

noting here that the right-hand side of (2) agrees with P_{2}(2m) = U_{m+1}, when r = 2.

Case 2: Odd Length n = 2m + 1 > r.

Now if the palindromic strings in question of length n = 2m + 1 have a central entry containing a 0, then any binary string of length m having no r-runs of 1’s can be used to concatenate to the right of this central entry, and to the left with its mirror image, and so there must be U_{m+r} such strings in total. Alternatively if the central entry contains a 1, then if the right binary string of length m has a left-hand entry of 0, then the remaining binary string of length m − 1 cannot contain r-runs of 1’s, and so there must be U_{m−1+r} such strings in total. Similarly if the right binary string of length m has a left-hand entry of \underbrace{11 ⋯ 1}_{s 1’s} 0, where 1 ≤ s < r, then the remaining binary strings of length m − s − 1 cannot

contain r-runs of 1’s, and so there must be U_{m−s−1+r} such strings in total. Now if r = 2, 3 then the set of binary strings having

Mirror String of Length m 0 Binary String of Length m
Mirror String of Length m − 1 0 1 0 Binary String of Length m − 1
Mirror String of Length m − s − 1 01 ⋯ 11 1 11 ⋯ 10 String of Length m − s − 1

Table 3: Odd length palindromic binary strings having no r-runs of 1’s

a left-hand entry of 10 cannot be used to construct the palindromic binary strings in question, as this would result in a central substring of 111, and so P_{2}(2m + 1) = U_{m+2} + U_{m+1}, and P_{3}(2m + 1) = U_{m+3} + U_{m+2}. However if r > 3, then the above three sets of binary strings can be used, provided the binary strings having a left-hand entry of \underbrace{11 ⋯ 1}_{s 1’s} 0 are such that

2s + 1 < r. Thus again by Lemma 1 we conclude 1 ≤ s ≤ ⌊\frac{r−2+(−1)^{r}}{2} ⌋, and so

P_{r}(2m + 1) = U_{m+r} + U_{m−1+r} + \begin{aligned}⌊ & \frac{r−2+(−1)^{r}}{2} & ⌋ \\ & ∑ \\ & s=1 \end{aligned} U_{m−s−1+r} = ∑_{i=−1}^{⌊ \frac{r−2+(−1)^{r}}{2} ⌋} U_{\frac{n−1}{2} +r−1−i} , (3)

noting here that the right-hand side of (3) agrees with P_{2}(2m + 1) = U_{m+2} + U_{m+1} and P_{3}(2m + 1) = U_{m+3} + U_{m+2}, when r = 2 and r = 3 respectively.

3 Characteristics of palindromic binary strings

We now turn our attention to the problem of enumerating the total number of zeros contained in the set of all palindromic binary strings of length n > r having no r-runs of 1’s. To help achieve this end, it will first be necessary to obtain a recurrence relation for the number of zeros contained in all U_{n+r} binary strings having no r-runs of 1’s, of length n ≥ 1. We first note that the total number of zeros contained in the set of all 2^{n} binary strings of length n ≥ 1, is given by Z(n) = n2^{n−1}. Interested readers can consult Nyblom [6] for a proof.

Lemma 3. For a fixed integer r ≥ 2, the total number of zeros that occur in the U_{n+r} binary strings of length n ≥ 1 having no r-runs of 1’s, satisfy the following r-th order recurrence relation

Z_{r}(n) = ∑_{i=1}^{r} Z_{r}(n − i) + U_{n+r} ,

for n > r, with the r initial conditions Z_{r}(n) = n2^{n−1}, for n = 1, 2, …, r.

Proof. Recall that the binary strings of length n > r having no r-runs of 1’s, can be partitioned into r disjoint sets containing those binary strings whose left-hand entry are 0, 10, 110, …, \underbrace{11 ⋯ 1}_{(r−1) 1’s} 0 respectively. Now if the binary strings in question have a left-hand

entry of 0, then the remaining U_{n−1+r} substrings of length n − 1 will by definition contribute Z_{r}(n − 1) zeros, making a total contribution of Z_{r}(n − 1) + U_{n−1+r} zeros. Similarly if the binary strings in question have a left-hand entry of \underbrace{11 ⋯ 1}_{i 1’s} 0, where 1 ≤ i < r, then the

remaining U_{n−i−1+r} substrings of length n − i − 1 will contribute Z_{r}(n − i − 1) zeros, making a total contribution of Z_{r}(n − i − 1) + U_{n−i−1+r} zeros. Thus for n > r

Z_{r}(n) = Z_{r}(n − 1) + U_{n−1+r} + ∑_{i=1}^{r−1}(Z_{r}(n − i − 1) + U_{n−i−1+r})

= ∑_{i=1}^{r}(Z_{r}(n − i) + U_{n−i+r})

= ∑_{i=1}^{r} Z_{r}(n − i) + ∑_{i=1}^{r} U_{n−i+r}

= ∑_{i=1}^{r} Z_{r}(n − i) + U_{n+r} .

Clearly the number of zeros that occur in the binary strings of length 1 ≤ n ≤ r having no r-runs of 1’s, must be equal to the number of zeros in all binary strings having corresponding length, consequently Z_{r}(n) = Z(n) = n2^{n−1}, for n = 1, 2, …, r.

By employing a similar argument used to establish Theorem 2, we can now obtain an expression for the number of zeros contained in all palindromic binary strings of length n > r ≥ 2 having no r-runs of 1’s, in terms of the characteristic Z_{r}(·), and the r-Fibonacci sequence {U_{n}}.

Theorem 4. For a fixed integer r ≥ 2, the total number of zeros that occur in the P_{r}(n) palindromic binary strings of length n > r having no r-runs of 1’s is

Z̃_{r}(n) = \begin{cases}2 ∑_{i=0}^{⌊ \frac{r−1+(−1)^{r+1}}{2} ⌋}(U_{\frac{n}{2} +r−1−i} + Z_{r}(\frac{n}{2} − 1 − i)), & if n even; \\ U_{\frac{n−1}{2} +r} + 2Z_{r}(\frac{n−1}{2}) + 2 ∑_{i=0}^{⌊ \frac{r−2+(−1)^{r}}{2} ⌋}(U_{\frac{n−1}{2} +r−1−i} + Z_{r}(\frac{n−1}{2} − 1 − i)), & if n odd. \end{cases}

(4)

Proof. In what follows recall the construction of the P_{r}(n) palindromic binary strings of length n > r outlined in the proof of Theorem 2. Now in the case of an even length n = 2m when r = 2, then the U_{m−1+r} = U_{m+1} right substrings contained in

Mirror String of Length m − 1 0 0 String of Length m − 1

will by definition contribute Z_{r}(m−1) = Z_{2}(m−1) zeros, together with the additional U_{m+1} left-hand zeros bringing a total contribution, with the mirror string, of 2(U_{m+1} + Z_{2}(m − 1)) zeros, and so Z̃_{2}(2m) = 2(U_{m+1} + Z_{2}(m − 1)). However when r > 2, then the above string, together with the U_{m−s−1+r} additional right substrings contained in

Mirror String of Length m − s − 1 01 ⋯ 11 11 ⋯ 10 String of Length m − s − 1

for, 1 ≤ s ≤ ⌊\frac{r−1+(−1)^{r+1}}{2} ⌋, will each contribute Z_{r}(m − s − 1) zeros, together with the additional U_{m−s−1+r} zero from each substring \underbrace{11 ⋯ 1}_{s 1’s} 0, bringing a total contribution, with

the mirror string, of

Z̃_{r}(2m) = 2(U_{m−1+r} + Z_{r}(m − 1)) + 2 ∑_{s=1}^{⌊ \frac{r−1+(−1)^{r+1}}{2} ⌋}(U_{m−s−1+r} + Z_{r}(m − s − 1))

= 2 ∑_{i=0}^{⌊ \frac{r−1+(−1)^{r+1}}{2} ⌋}(U_{\frac{n}{2} −i−1+r} + Z_{r}(\frac{n}{2} − i − 1))  (5)

zeros, noting here that the right-hand side of (5) agrees with Z̃_{2}(2m), when r = 2.

Mirror String of Length m 0 Binary String of Length m
Mirror String of Length m − 1 0 1 0 Binary String of Length m − 1

In the case of an odd length n = 2m + 1 when r = 2 and r = 3, then the U_{m+r} and U_{m−1+r} right substring contained in for respectively, will each contribute Z_{r}(m) and Z_{r}(m − 1) zeros. In the first palindromic string, by adding the U_{m+r} centered zeros brings a total contribution, with the mirror substring, of U_{m+r} + 2Z_{r}(m) zeros. However in the second palindromic string, by adding the U_{m−1+r} left-hand zeros brings a total contribution, with the mirror substring, of 2(U_{m−1+r} + Z_{r}(m − 1)) zeros. Thus the total number of zeros contained in the first two palindromic strings is

(U_{m+r} + 2Z_{r}(m)) + 2(U_{m−1+r} + Z_{r}(m − 1)) ,

and so Z̃_{2}(2m + 1) = (U_{m+2} + 2Z_{2}(m)) + 2(U_{m+1} + Z_{2}(m − 1)) and Z̃_{3}(2m + 1) = (U_{m+3} + 2Z_{3}(m)) + 2(U_{m+2} + Z_{3}(m − 1)). Now when r > 3, then the above two strings together with the U_{m−s−1+r} additional right substrings contained in

Mirror String of Length m − s − 1 01 ⋯ 11 1 11 ⋯ 10 String of Length m − s − 1

for 1 ≤ s ≤ ⌊\frac{r−2+(−1)^{r}}{2} ⌋, will each contribute Z_{r}(m−s−1) zeros, together with the additional U_{m−s−1+r} zeros from the substring \underbrace{11 ⋯ 1}_{s 1’s} 0, bringing a total contribution, with the mirror

string, of

Z̃_{r}(2m + 1) = U_{m+r} + 2Z_{r}(m) + 2(U_{m−1+r} + Z_{r}(m − 1))
+ 2 ∑_{s=1}^{⌊ \frac{r−2+(−1)^{r}}{2} ⌋}(U_{m−s−1+r} + Z_{r}(m − s − 1))

= U_{m+r} + 2Z_{r}(m) + 2 ∑_{i=0}^{⌊ \frac{r−2+(−1)^{r}}{2} ⌋}(U_{m+r−1−i} + Z_{r}(m − 1 − i))  (6)

zeros, noting here that the right-hand side of (6) agrees with Z̃_{2}(2m + 1) and Z̃_{3}(2m + 1), when r = 2 and r = 3 respectively.

To illustrate both Theorem 2 and Theorem 4, suppose we wish to calculate the total number of Palindromic binary strings of length n = 5 having no consecutive 1’s, and the total number of zeros contained in these strings. In this case when we set r = 2 and n = 5 into (1) and (4), noting here that the 2-Fibonacci sequence U_{n} = F_{n}, one finds that P_{2}(5) = F_{4}+F_{3} = 3+2 = 5 while Z̃_{2}(5) = F_{4}+2Z_{2}(2)+2(F_{3}+Z_{1})) = 3+(2)(4)+2(2+1) = 17, which is in agreement with palindromic strings displayed below.

0 0 0 0 0
0 1 0 1 0
1 0 0 0 1
0 0 1 0 0
1 0 1 0 1

Table 4: The 5 palindromic binary strings of length 5 having no 2-runs of 1’s

References

[1] R. C. Bollinger, Fibonacci k-sequence, Pascal-t triangles, and k-in-a-row problems, Fibonacci Quart. 22 (1984), 146–151.

[2] R. P. Grimaldi, Discrete and Combinatorial Mathematics, 2nd edition, Addison-Wesley, 1989.

[3] R. P. Grimaldi and S. Heubach, Binary strings without odd runs of zeros, Ars Combinatoria 75 (2005), 241–255.

[4] R. P. Grimaldi, Ternary strings with no consecutive 1’s, Ars Combinatoria 89 (2008), 321–343.

[5] B. Hayes, D. S. Pearson, and M. Andreoli, Solutions 10196, Amer. Math. Monthly 101 (1984), 363–365.

[6] M. A. Nyblom, Enumerating binary strings without r-runs of ones, Int. Math. Forum, 7 (2012), 1865–1876.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 05A15. Keywords: binary strings, r-Fibonacci sequence, r-run of ones.

(Concerned with sequences \underline{A001590} and \underline{A053602}.)

Received June 7 2013; revised version received September 13 2013. Published in Journal of Integer Sequences, October 13 2013.

Return to Journal of Integer Sequences home page.