CIRCULAR BINARY STRINGS WITHOUT ZIGZAGS

Emanuele Munarini

Dipartimento di Matematica, Politecnico di Milano, P.za Leonardo da Vinci 32, 20133 Milano, Italy

                         munarini@mate.polimi.it

Norma Zagaglia Salvi

Dipartimento di Matematica, Politecnico di Milano, P.za Leonardo da Vinci 32, 20133 Milano, Italy

                          norzag@mate.polimi.it

Received: 4/11/03, Revised: 11/20/03, Accepted: 12/9/03, Published: 12/11/03

Abstract

We study several enumerative properties of the set of all circular binary strings without zigzags and of the set of all (0, 1)-necklaces without zigzags, where a zigzag is a 1 followed and preceded by a 0 or a 0 followed and preceded by a 1.

1. Introduction

A circular binary string is a function defined on a cycle with values in {0, 1}. As usual we write a circular binary string as a linear string with the convention that the first and the last letter are adjacent. A (0, 1)-necklace is a circular binary string defined up to cyclic shifts. Hence a (0, 1)-necklace is an equivalence class of circular binary strings. However, for simplicity, we write circular binary strings and necklaces in the same way. For instance 001 , 010 and 100 are different circular binary strings but represent the same necklace.

We say that a circular binary string has a zigzag when a 1 is followed and preceded by a 0 or, dually, when a 0 is followed and preceded by a 1. Recall that a linear string σ is a substring of a circular string α when there exist two linear strings α_{1} and α_{2} such that α = α_{1}σα_{2} or when σ = σ_{1}σ_{2} and there exists a linear string β such that α = σ_{2}βσ_{1} . For instance the substrings of length 3 of the circular string α = 1011 are 101 , 011 , 111 and 110 .

For linear strings a zigzag is equivalent to a substring equal to 010 or 101 . This is still true for circular binary strings of length n ≠ 2 , but when n = 2 also the circular strings 10 and 01 have a zigzag.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A19 2

The aim of this paper is to obtain enumerative properties for the circular binary strings without zigzags and for the (0, 1)-necklaces without zigzags. Specifically we obtain the recurrences, the generating series and several explicit formulas for the numbers z_{m,n} of all circular binary strings without zigzags with m 1’s and n 0’s and in particular for the numbers z_{n} = z_{n,n} of central strings. In particular for the numbers z_{n} we also give a first-order asymptotic formula.

Then we consider the infinite matrix Z = [z_{i,j}]_{i,j≥0} and we prove that it can be decomposed as LT L^{t} where L is a lower triangular matrix and T is a tridiagonal matrix. Both such matrices have non-negative integer entries. Moreover we show that the lower triangular matrix R = [r_{i,j}]_{i,j≥0} , where r_{i,j} = z_{i,i−j} for i ≥ j, i ≠ 0 , r_{0,0} = 1 and r_{i,j} = 0 otherwise, is a Riordan matrix [13].

Finally we consider the cyclic species of all circular binary strings without zigzags and we prove that it can be decomposed as a suitable composition of species. Such a decomposition passes to types allowing to obtain an explicit formula for the numbers z̃_{m,n} of all (0, 1)-necklaces without zigzags with m 1’s and n 0’s.

In [11] we studied the same problem for linear binary strings. Both the problems, for linear and circular strings, were posed by Jie Wu in the particular case in which the number of 1’s is equal to the number of 0’s. See [3] for an algorithmic approach to this particular case for linear strings.

2. Explicit formulas and generating functions

Let Z be the set of all circular binary strings without zigzags. Then let Z_{m,n} be the set of all strings in Z with m 1’s and n 0’s and let z_{m,n} = |Z_{m,n}|. The conjugate string \overline{α} of a binary string α is the string obtained by interchanging 0 and 1 in α. For instance, if α = 100110 then \overline{α} = 011001 . Clearly conjugation establishes a bijection between Z_{m,n} and Z_{n,m} which implies the symmetry z_{m,n} = z_{n,m}.

First formula. Here we give a canonical decomposition for the strings in Z_{m,n} similar to the one used in [11] for linear strings. Let α be any string in Z_{m,n}. Since α has no zigzags, each maximal block of 1’s and 0’s has length at least two, except possibly for the first and the last maximal block. This implies that α can be uniquely decomposed as a product of strings of the form 01 , 10 , 0 ⋯ 0 , 1 ⋯ 1 in one of the following way

(1 ⋯ 1)(10)(0 ⋯ 0)(01)(1 ⋯ 1) ⋯
(0 ⋯ 0)(01)(1 ⋯ 1)(10)(0 ⋯ 0) ⋯

where any block 01 is followed by a block 1 ⋯ 1 and is preceded by a block 0 ⋯ 0 , and dually any block 10 is followed by a block 0 ⋯ 0 and is preceded by a block 1 ⋯ 1 . For instance, the string α = 000011110001100 decomposes as α = (000)(01)(11)(10)(0)(01)(10)(0) . We say that 01 and 10 are the principal blocks. The non principal blocks can also be empty.

To enumerate all the stings in Z_{m,n} we have to consider two cases, according to the parity of the number of principal blocks. Suppose first there are 2k (with k ≥ 1 ) principal blocks. Then to obtain all the strings α of the form

0 ⋯ 0 01 1 ⋯ 1 10 0 ⋯ 0 ⋯ 01 1 ⋯ 1 10 0 ⋯ 0

we fix the principal blocks and then we distribute m − 2k 1’s in k places and n − 2k 0’s in k + 1 places. Hence the total number of the strings of this form is

\begin{aligned}( \\ ( & {k \atop m − 2k} & ) \\ & & ) \end{aligned}\begin{aligned}( \\ ( & {k + 1 \atop n − 2k} & ) \\ & & ) \end{aligned} .  (1)

Similarly, the total number of the strings α of the form

1 ⋯ 1 10 0 ⋯ 0 01 1 ⋯ 1 ⋯ 10 0 ⋯ 0 01 1 ⋯ 1

turns out to be

\begin{aligned}( \\ ( & {k + 1 \atop m − 2k} & ) \\ & & ) \end{aligned}\begin{aligned}( \\ ( & {k \atop n − 2k} & ) \\ & & ) \end{aligned} .  (2)

Suppose now that α contains 2k +1 principal blocks. Then α has one of the following forms:

0 ⋯ 0 0 01 1 ⋯ 1 10 0 ⋯ 0 ⋯ 01 1 1 ⋯ 1
1 ⋯ 1 1 10 0 ⋯ 0 01 1 ⋯ 1 ⋯ 10 0 0 ⋯ 0

In both cases we have m − 2k − 2 1’s to distribute in k + 1 places and n − 2k − 2 0’s to distribute in k + 1 places. Then the total number of the strings of this second case is equal to

2\begin{aligned}( \\ ( & {k + 1 \atop m − 2k − 2} & ) \\ & & ) \end{aligned}\begin{aligned}( \\ ( & {k + 1 \atop n − 2k − 2} & ) \\ & & ) \end{aligned} .  (3)

All this implies the identity

z_{m,n} = ∑_{k≥1} \begin{aligned}( \\ ( & {k \atop m − 2k} & ) \\ & & ) \end{aligned}\begin{aligned}( \\ ( & {k + 1 \atop n − 2k} & ) \\ & & ) \end{aligned} + ∑_{k≥1} \begin{aligned}( \\ ( & {k + 1 \atop m − 2k} & ) \\ & & ) \end{aligned}\begin{aligned}( \\ ( & {k \atop n − 2k} & ) \\ & & ) \end{aligned} +

+ 2 ∑_{k≥0} \begin{aligned}( \\ ( & {k + 1 \atop m − 2k − 2} & ) \\ & & ) \end{aligned}\begin{aligned}( \\ ( & {k + 1 \atop n − 2k − 2} & ) \\ & & ) \end{aligned} .  (4)

Generating series. To obtain the generating series for the numbers z_{m,n} we use the Schützenberger symbolic method [12, 4]. The above analysis also implies that the set Z, considered as a language, is given by

Z = 0^{+} + 1^{+} +

+ ∑_{k≥1} \underbrace{0^{∗}(01)1^{∗}(10) ⋯ (01)1^{∗}(10)0^{∗}}_{2k principal blocks} + ∑_{k≥1} \underbrace{1^{∗}(10)0^{∗}(01) ⋯ (10)0^{∗}(01)1^{∗}}_{2k principal blocks} +

+ ∑_{k≥0} \underbrace{0^{∗}(0)(01)1^{∗}(10) ⋯ (10)0^{∗}(01)(1)1^{∗}}_{2k+1 principal blocks} + ∑_{k≥0} \underbrace{1^{∗}(1)(10)0^{∗}(01) ⋯ (01)1^{∗}(10)(0)0^{∗}}_{2k+1 principal blocks}

where 0^{∗} = {ε, 0, 00, 000, … }, 0^{+} = 0^{∗} \ {ε}, etc. Substituting 1 and 0 with the indeterminates x and y respectively, the above identity yields the following geometric series

Z(x, y) = ∑_{m,n≥0} z_{m,n} x^{m}y^{n}

= \frac{x}{1 − x} + \frac{y}{1 − y} + ∑_{k≥1} \frac{x^{2k}}{(1 − x)^{k}} \frac{y^{2k}}{(1 − y)^{k+1}} +

+ ∑_{k≥1} \frac{x^{2k}}{(1 − x)^{k+1}} \frac{y^{2k}}{(1 − y)^{k}} + 2 ∑_{k≥0} \frac{x^{2k+2}}{(1 − x)^{k+1}} \frac{y^{2k+2}}{(1 − y)^{k+1}}

which turns out to be equal to

Z(x, y) = \frac{x + y − 2xy + 4x^{2}y^{2}}{1 − x − y + xy − x^{2}y^{2}} .  (5)

The form of this series immediately implies the recurrence

z_{m+2,n+2} = z_{m+1,n+2} + z_{m+2,n+1} − z_{m+1,n+1} + z_{m,n} + 4δ_{m,0}δ_{n,0}  (6)

where δ_{n,k} is the usual Kronecker delta.

Second formula. The formal series (5) yields another expression for the coefficients z_{m,n}. First notice that it can be rewritten as

Z(x, y) = −1 + \frac{1 + xy + x^{2}y^{2}}{1 − x − y + xy − x^{2}y^{2}} − 2\frac{xy − x^{2}y^{2}}{1 − x − y + xy − x^{2}y^{2}} .

Since we have

\frac{1 + xy + x^{2}y^{2}}{1 − x − y + xy − x^{2}y^{2}} = \frac{1}{(1 − x)(1 − y)} \frac{1 + xy + x^{2}y^{2}}{1 − \frac{x^{2}}{1 − x} \frac{y^{2}}{1 − y}} =

= ∑_{k≥0} \frac{x^{k−⌊k/3⌋}}{(1 − x)^{⌊k/3⌋+1}} \frac{y^{k−⌊k/3⌋}}{(1 − y)^{⌊k/3⌋+1}}

= ∑_{m,n≥0} [∑_{k≥0} \binom{m − k + 2⌊k/3⌋}{⌊k/3⌋}\binom{n − k + 2⌊k/3⌋}{⌊k/3⌋}] x^{m}y^{n}

\begin{matrix}z_{m,n} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 3 & 1 & 0 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 4 & 1 & 0 & 6 & 7 & 12 & 18 & 25 & 33 & 42 & 52 & 63 \\ 5 & 1 & 0 & 7 & 8 & 18 & 30 & 44 & 60 & 78 & 98 & 120 \\ 6 & 1 & 0 & 8 & 9 & 25 & 44 & 70 & 104 & 147 & 200 & 264 \\ 7 & 1 & 0 & 9 & 10 & 33 & 60 & 104 & 168 & 255 & 368 & 510 \\ 8 & 1 & 0 & 10 & 11 & 42 & 78 & 147 & 255 & 412 & 629 & 918 \\ 9 & 1 & 0 & 11 & 12 & 52 & 98 & 200 & 368 & 629 & 1014 & 1558 \\ 10 & 1 & 0 & 12 & 13 & 63 & 120 & 264 & 510 & 918 & 1558 & 2514 \end{matrix}

Figure 1: Numbers of circular binary strings without zigzags.

and

\frac{xy − x^{2}y^{2}}{1 − x − y + xy − x^{2}y^{2}} = \frac{1}{(1 − x)(1 − y)} \frac{xy − x^{2}y^{2}}{1 − \frac{x^{2}}{1 − x} \frac{y^{2}}{1 − y}} =

= ∑_{k≥0}(−1)^{k} \frac{x^{k+1}}{(1 − x)^{⌊k/2⌋+1}} \frac{y^{k+1}}{(1 − y)^{⌊k/2⌋+1}}

= ∑_{m,n≥0} [∑_{k≥0} \binom{m − ⌈k/2⌉ − 1}{⌊k/2⌋}\binom{n − ⌈k/2⌉ − 1}{⌊k/2⌋}(−1)^{k}] x^{m}y^{n} ,

then, for m, n ≠ 0 , we have the identity

z_{m,n} = ∑_{k≥0} \binom{m − k + 2⌊k/3⌋}{⌊k/3⌋}\binom{n − k + 2⌊k/3⌋}{⌊k/3⌋}+

−2 ∑_{k≥0} \binom{m − ⌈k/2⌉ − 1}{⌊k/2⌋}\binom{n − ⌈k/2⌉ − 1}{⌊k/2⌋}(−1)^{k} .  (7)

Total number of circular binary strings without zigzags. Let s_{n} be the total number of all circular binary strings without zigzags of length n. Then the generating series S(t) = ∑_{n≥0} s_{n} t^{n} of these numbers is given by

S(t) = Z(t, t) = \frac{2t − 2t^{2} + 4t^{4}}{1 − 2t + t^{2} − t^{4}} = \frac{2t(1 − t + 2t^{3})}{(1 − t − t^{2})(1 − t + t^{2})} .  (8)

Since (1 − 2t + t^{2} − t^{4})S(t) = 2t − 2t^{2} + 4t^{4} , we have the linear recurrence

s_{n+4} = 2s_{n+3} − s_{n+2} + s_{n} + 4δ_{n,0} .  (9)

The first few terms of this sequence are: 0, 2, 2, 2, 6, 12, 20, 30, 46, 74, 122, 200, 324, 522, 842, 1362, 2206, 3572, 5780, 9350, 15126, 24474. Moreover, since series (8) can be written as

S(t) = \frac{2 − t}{1 − t − t^{2}} + \frac{2 − t}{1 − t + t^{2}} − 4 = ∑_{n≥0} L_{n} t^{n} + ∑_{n≥0} H_{n} t^{n} − 4 ,

we have that s_{n} = L_{n} + H_{n} − 4δ_{n,0} where the L_{n}’s are Lucas numbers and the H_{n}’s are the numbers defined by the recurrence H_{n+2} = H_{n+1} − H_{n} with the initial values H_{0} = 2 and H_{1} = 1 . It is easy to see that the sequence {H_{n}}_{n} is periodic with period 2, 1, −1, −2, −1, 1 .

3. Central strings

We say that a circular binary string is central when the number of 1’s is equal to the number of 0’s. Let z_{n} be the number of all central circular binary strings without zigzags, with length 2n. The first few values of z_{n} are: 0, 2, 4, 6, 12, 30, 70, 168, 412, 1014, 2514, 6270, 15702, 39468, 99516, 251586, 637500. Identities (4), (7), (25) immediately imply that

z_{n} = 2 ∑_{k≥1} \begin{aligned}( \\ ( & {k \atop n − 2k} & ) \\ & & ) \end{aligned}\begin{aligned}( \\ ( & {k + 1 \atop n − 2k} & ) \\ & & ) \end{aligned} + 2 ∑_{k≥0} \begin{aligned}( \\ ( & {k + 1 \atop n − 2k − 2} & ) \\ & & ) \end{aligned}^{2}  (10)

z_{n} = ∑_{k≥0} \binom{n − k + 2⌊k/3⌋}{⌊k/3⌋}^{2} − 2 ∑_{k≥0} \binom{n − ⌈k/2⌉ − 1}{⌊k/2⌋}^{2}(−1)^{k}  (11)

z_{n} = ∑_{k≥0} \binom{n − k − 2}{k}^{2} \frac{2n}{k + 1} .  (12)

Now we will find the geometric series, a recurrence and a first-order asymptotic formula for the numbers z_{n}. The geometric series of the numbers z_{n} is the diagonal series of (5) and, by Cauchy’s integral theorem, is given by [2, 8, 15, 7]

z(t) = ∑_{n≥0} z_{n} t^{n} = \frac{1}{2πi} ∮ Z (z, \frac{t}{z} ) \frac{dz}{z}

= \frac{1}{2πi} ∮ \frac{z^{2} − (2t − 4t^{2})z + t}{−z(z^{2} − (1 + t − t^{2})z + t)}dz

where the integral is taken over a simple contour containing all the singularities s(t) of the series such that s(t) → 0 as t → 0 . The polynomial z^{2} − (1 + t − t^{2})z + t at the denominator has roots

z^{±} = \frac{1 + t − t^{2} ± \sqrt{(1 + t − t^{2})^{2} − 4t}}{2}

of which only z^{−} → 0 as t → 0 . Hence z = 0 and z = z^{−} are the only poles (of first order) which tend to zero as t → 0 . By the residue theorem, we have

z(t) = lim_{z→0} \frac{z^{2} − (2t − 4t^{2})z + t}{−(z^{2} − (1 + t − t^{2})z + t)} + lim_{z→z^{−}} \frac{z^{2} − (2t − 4t^{2})z + t}{−z(z − z^{+})}

that is

z(t) = \frac{1 − t + 3t^{2} − \sqrt{1 − 2t − t^{2} − 2t^{3} + t^{4}}}{\sqrt{1 − 2t − t^{2} − 2t^{3} + t^{4}}} .  (13)

Now to obtain a recurrence for the numbers z_{n} we rewrite identity (13) as

\sqrt{1 − 2t − t^{2} − 2t^{3} + t^{4}} = \frac{(1 − 2t − t^{2} − 2t^{3} + t^{4})(z(t) + 1)}{1 − t + 3t^{2}} .

Then, differentiating such an identity, we obtain the identity

(1 − 3t + 4t^{2} − 7t^{3} − 7t^{5} + 3t^{6})z′(t)+
−(8t − 6t^{2} − 6t^{3} − 2t^{4})z(t) − 8t + 6t^{2} + 6t^{3} + 2t^{4} = 0

which implies the linear recurrence

(n + 6)z_{n+6} − 3(n + 5)z_{n+5} + 4(n + 2)z_{n+4}+
−(7n + 15)z_{n+3} + 6z_{n+2} − (7n + 5)z_{n+1} + 3nz_{n} = 0 .  (14)

Finally we give a first-order asymptotic formula for z_{n}. Recall ([1] p. 252) that given a complex number ξ ≠ 0 and a complex function f(t) analytic at the origin, if f(t) = (1 − t/ξ)^{−α}ψ(t) where ψ(t) is a series with radius of convergence R > |ξ| and α ∉ {0, −1, −2, … }, then

[t^{n}]f(t) ∼ \frac{ψ(ξ)}{ξ^{n}} \frac{n^{α−1}}{Γ(α)} .

Since

z(t) = \frac{1 − t + 3t^{2}}{\sqrt{1 − 2t − t^{2} − 2t^{3} + t^{4}}} − 1
= (1 − \frac{t}{ξ} )^{−1/2} \frac{1 − t + 3t^{2}}{\sqrt{(1 + t + t^{2})(1 − ξt)}} − 1

where ξ = (3 − \sqrt{5})/2 and α = 1/2 , we have

z_{n} ∼ \frac{\sqrt{5} − 1}{2}\sqrt{\frac{\sqrt{5}}{nπ}} (\frac{3 + \sqrt{5}}{2})^{n} .  (15)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A19 8

In particular

lim_{n→∞} \frac{z_{n+1}}{z_{n}} = \frac{3 + \sqrt{5}}{2} .  (16)

In [11] we proved that for the number w_{n} of all central binary strings, without zigzags, of length 2n we have the asymptotic formula

w_{n} ∼ \sqrt{\frac{4}{nπ\sqrt{5}}} (\frac{3 + \sqrt{5}}{2})^{n} .

This implies that

lim_{n→∞} \frac{w_{n}}{z_{n}} = \frac{4}{\sqrt{5} − 1} ≃ 3.24

or equivalently w_{n} ≃ 3.24 z_{n}.

4. The matrix Z In this section we will prove that the matrix

Z = [z_{i,j}]_{i,j≥0} = [\begin{matrix}0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 0 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 1 & 0 & 6 & 7 & 12 & 18 & 25 & 33 & 42 \\ 1 & 0 & 7 & 8 & 18 & 30 & 44 & 60 & 78 \\ 1 & 0 & 8 & 9 & 25 & 44 & 70 & 104 & 147 \\ 1 & 0 & 9 & 10 & 33 & 60 & 104 & 168 & 255 \\ 1 & 0 & 10 & 11 & 42 & 78 & 147 & 255 & 412 \\ … \end{matrix}]

has a factorization LT L^{t} where L is the lower triangular matrix

L = [l_{i,j}]_{i,j≥0} = [\begin{matrix}1 \\ 0 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 2 & 1 \\ 0 & 1 & 1 & 3 & 2 & 1 \\ 0 & 1 & 1 & 4 & 3 & 3 & 1 \\ 0 & 1 & 1 & 5 & 4 & 6 & 3 & 1 \\ 0 & 1 & 1 & 6 & 5 & 10 & 6 & 4 & 1 \\ … \end{matrix}]

with entries given by

l_{i,0} = 0^{i} , l_{i,j} = \binom{i − ⌊j/2⌋ − 1}{i − j} for i ≥ j > 1 ,

L^{t} is the transpose of L and T is the tridiagonal matrix

T = [t_{i,j}]_{i,j≥0} = [\begin{matrix}0 & 1 \\ 1 & 0 & 0 \\ & 0 & 4 & 1 \\ & & 1 & 0 & 0 \\ & & & 0 & 4 & 1 \\ & & & & 1 & 0 & 0 \\ & & & & & 0 & 4 & 1 \\ & & & & & & 1 & 0 & 0 \\ & & & & & & & 0 & 4 \\ & & & & & & & & … \end{matrix}]

with entries

t_{i,j} = [ j mod 2 = 0 ] δ_{i,j+1} + 4[ i mod 2 = 0, i ≠ 0 ]δ_{i,j} + [ i mod 2 = 0 ] δ_{i+1,j}

where the square brackets denote the Iverson notation [6] for the characteristic function of a proposition and δ_{i,j} = [ i = j] is the usual Kronecker delta.

To prove the stated decomposition it is sufficient to rewrite the series Z(x, y) in the following way:

Z(x, y) = \frac{x(1 − y) + 4x^{2}y^{2} + y(1 − y)}{(1 − x)(1 − y) − x^{2}y^{2}}

= \frac{x}{1 − x} \frac{1}{1 − \frac{x^{2}}{1 − x} \frac{y^{2}}{1 − y}} + 4\frac{x^{2}}{1 − x} \frac{y^{2}}{1 − y} \frac{1}{1 − \frac{x^{2}}{1 − x} \frac{y^{2}}{1 − y}} + \frac{y^{2}}{1 − y} \frac{1}{1 − \frac{x^{2}}{1 − x} \frac{y^{2}}{1 − y}}

= ∑_{k≥0} \frac{x^{2k+1}}{(1 − x)^{k+1}} \frac{y^{2k}}{(1 − y)^{k}} + 4 ∑_{k≥1} \frac{x^{2k}}{(1 − x)^{k}} \frac{y^{2k}}{(1 − y)^{k}} + ∑_{k≥0} \frac{x^{2k}}{(1 − x)^{k}} \frac{y^{2k+1}}{(1 − y)^{k+1}}

= ∑_{h,k≥0} \frac{x^{h}}{(1 − x)^{⌈h/2⌉}} [ k mod 2 = 0 ]δ_{h,k+1} \frac{y^{k}}{(1 − y)^{⌈k/2⌉}} +

∑_{h,k≥0} \frac{x^{h}}{(1 − x)^{⌈h/2⌉}} [ k mod 2 = 0 , k ≥ 1 ]δ_{h,k} \frac{y^{k}}{(1 − y)^{⌈k/2⌉}} +

∑_{h,k≥0} \frac{x^{h}}{(1 − x)^{⌈h/2⌉}} [ k mod 2 = 0 ]δ_{h+1,k} \frac{y^{k}}{(1 − y)^{⌈k/2⌉}}

= ∑_{h,k≥0} \frac{x^{h}}{(1 − x)^{⌈h/2⌉}} t_{h,k} \frac{y^{k}}{(1 − y)^{⌈k/2⌉}}

= ∑_{i,j≥0} ( ∑_{h,k≥0} l_{i,h}t_{h,k}l_{j,k}) x^{i}y^{j}

where the numbers l_{i,j} are the coefficients of the series

∑_{i≥1} l_{i,j} x^{i} = \frac{x^{j}}{(1 − x)^{⌈j/2⌉}} .

Then it follows that

l_{i,j} = \binom{i − j + ⌈j/2⌉ − 1}{⌈j/2⌉ − 1} = \binom{i − ⌊j/2⌋ − 1}{i − j} .

Hence we have the identity

∑_{h,k≥0} l_{i,h}t_{h,k}l_{j,k} = z_{i,j}  (17)

which is equivalent to the decomposition W = LT L^{t}.

5. A Riordan Matrix

In [11] we observed that the numbers w_{i,j} of all linear binary strings without zigzags with i 1’s and j 0’s can be used to generate a Riordan matrix. This is also true for the numbers z_{i,j}. Let r_{n,k} = z_{n,n−k} for k ≤ n, n ≠ 0 , r_{0,0} = 1 and r_{n,k} = 0 otherwise. Then

R = [r_{n,k}]_{n,k≥0} = [ \begin{matrix}1 \\ 0 & 1 \\ 4 & 0 & 1 \\ 6 & 5 & 0 & 1 \\ 12 & 7 & 6 & 0 & 1 \\ 30 & 18 & 8 & 7 & 0 & 1 \\ 70 & 44 & 25 & 9 & 8 & 0 & 1 \\ 168 & 104 & 60 & 33 & 10 & 9 & 0 & 1 \\ 412 & 255 & 147 & 78 & 42 & 11 & 10 & 0 & 1 \\ … \end{matrix} ]

is a Riordan matrix [13, 10]. Indeed also this time we have the recurrence

r_{n+2,k+1} = r_{n+1,k} + r_{n+2,k+2} − r_{n+1,k+1} + r_{n,k+1}  (18)

which can be obtained by (6). Moreover the matrix R is completely determined by the recurrences

\{ \begin{matrix}r_{n+2,k+1} = r_{n+1,k} + r_{n,k+1} + r_{n,k+2} + ⋯ + r_{n,n} \\ r_{n+2,0} = r_{n+1,0} + r_{n,0} + 2r_{n,1} + ⋯ + 2r_{n,n} + 3δ_{n,0} \end{matrix}

with the initial conditions r_{0,0} = 1 , r_{1,0} = 0 and r_{1,1} = 1 .

It is easy to see that the recurrence (18) imply that the generating series r_{k}(t) = ∑_{n≥k} r_{n,k} t^{n} of the columns of the matrix R have the form r_{k}(t) = g(t)f(t)^{k} where g(t) = r_{0}(t) = z(t) + 1 and

f(t) = \frac{1 + t − t^{2} − \sqrt{1 − 2t − t^{2} − 2t^{3} + t^{4}}}{2} .

This last series is the generating series of the numbers of irreducible secondary structures [16, 15]. Since g_{0} = 1 , f_{0} = 0 and f_{1} ≠ 0 , R is the Riordan matrix

(\frac{1 − t + 3t^{2}}{\sqrt{1 − 2t − t^{2} − 2t^{3} + t^{4}}} , \frac{1 + t − t^{2} − \sqrt{1 − 2t − t^{2} − 2t^{3} + t^{4}}}{2} ) .

Finally, since (for k ≥ 1 )

r_{n,k} = [t^{n}] g(t)f(t)^{k} = (1 − \frac{t}{ξ} )^{−1/2} \frac{1 − t + 3t^{2}}{\sqrt{(1 + t + t^{2})(1 − ξt)}} f(t)^{k}

where ξ = (3 − \sqrt{5})/2 and α = 1/2 , using the theorem we recalled in Section 3, it follows that (for every fixed k)

r_{n,k} ∼ \frac{\sqrt{5} − 1}{2}\sqrt{\frac{\sqrt{5}}{nπ}} (\frac{3 + \sqrt{5}}{2})^{n} (\frac{\sqrt{5} − 1}{2})^{k} = \sqrt{\frac{\sqrt{5}}{nπ}} (ϕ + 1)^{n}(ϕ − 1)^{k+1}  (19)

where ϕ = (1 + \sqrt{5})/2 is the golden ratio. More in general we have [14]

∑_{k=0}^{n} a_{k}r_{n,k} = [t^{n}] g(t) a(f(t))

where a(t) is the ordinary generating series for the numbers a_{k}. For instance, for a_{k} = 1 and a_{k} = k, we have

∑_{k=0}^{n} r_{n,k} = [t^{n}] g(t) f(t) ∼ \frac{3 − \sqrt{5}}{2} \sqrt{\frac{\sqrt{5}}{nπ}} ϕ^{2n}

∑_{k=0}^{n} k r_{n,k} = [t^{n}] g(t) \frac{f(t)}{1 − f(t)} ∼ \sqrt{\frac{\sqrt{5}}{nπ}} ϕ^{2n+2} .

6. Cyclic species and generating series

The theory of species allows to interpret combinatorially several algebraic operations on formal series. As well known [9, 1, 5] ordinary species, linear species and cyclic species correspond to the combinatorics of sets, linearly ordered sets and cycles, respectively. Moreover their cardinalities are the exponential series, the ordinary power series and the logarithmic series. In this way several combinatorial operations on species become algebraic operations on series. In particular if a species S can be expressed by means of sums, products and compositions of other species S_{1} , …, S_{k} then its cardinality can be expressed in the same way in terms of the cardinalities of S_{1} , …, S_{k}. This is true also for types, considering as cardinalities the indicatrice series.

In this section we consider the cyclic species of circular binary strings without zigzags and we show that it can be decomposed in more elementary species. This decomposition allows to compute the logarithmic series for the numbers s_{n} and z_{m,n} and above all it allows to obtain the indicatrice series for types (see next section).

Let Z be the cyclic species of circular binary strings without zigzags and let Z^{≥2} be the cyclic species of circular binary strings without zigzags with maximal blocks of length at least 2. Then clearly Z = 2X + Z^{≥2} where X is the linear species of singletons.

Let C be a cycle and α ∈ Z^{≥2}[C] . Decompose α in its maximal blocks of 1’s and 0’s. Then pair each maximal block of 1’s with the next maximal block of 0’s. For instance, if α = 110001111001 then we have the grouping α = 11)(000)][(1111)(00)][(1 . The square brackets define a cyclic partition [5] of the cycle C, while the parenthesis inside the square brackets define a linear partition of an interval in two classes of size ≥ 2 . The blocks determined by the square brackets will be called external blocks.

Hence we have that to give a structure of species Z^{≥2} on a cycle C is equivalent to assign a cyclic partition π of C and then to assign on each class of π a pair of disjoint intervals with at least 2 elements whose union is all the class. So it follows that

Z^{≥2} = L ∘ (G^{≥2} · G^{≥2})  (20)

where L is the logarithmic species (or the uniform cyclic species) and G is the geometric species (or the uniform linear species). Relation (20) implies that

Card(Z^{≥2}; t) = Card(L; t) ∘ Card(G^{≥2}; t)^{2}
= ln \frac{1}{1 − t} ∘ (\frac{t^{2}}{1 − t})^{2}
= ln \frac{(1 − t)^{2}}{1 − 2t + t^{2} − t^{4}}

that is

Card(Z^{≥2}; t) = ln \frac{1}{1 − 2t + t^{2} − t^{4}} − 2 ln \frac{1}{1 − t} .  (21)

Since Z = 2X + Z^{≥2} , it follows that

Card(Z; t) = ∑_{n≥1} s_{n} \frac{t^{n}}{n} = ln \frac{1}{1 − 2t + t^{2} − t^{4}} .  (22)

This is the logarithmic generating series for the numbers s_{n}. This identity can be obtained directly by (8) using the formula

∑_{n≥1} s_{n} \frac{t^{n}}{n} = ∫_{0}^{t} \frac{S(u) − S(0)}{u} du .

To obtain a generating series for the numbers z_{m,n} we can consider the weighted cyclic species Z_{x,y} where each maximal block of 1’s have weight x and each block of 0’s have weight y. Then, exactly as before, we have

Z_{x,y}^{≥2} = L ∘ (G_{x}^{≥2} · G_{y}^{≥2})  (23)

where G_{x}^{≥2} is the weighted linear species of the linear orders of size at least 2 with weight x. Hence we have

Card(Z_{x,y}^{≥2}; t) = Card(L; t) ∘ (Card(G_{x}^{≥2}; t) · Card(G_{y}^{≥2}; t))
= ln \frac{1}{1 − t} ∘ (\frac{x^{2}t^{2}}{1 − xt} \frac{y^{2}t^{2}}{1 − yt})
= ln \frac{(1 − xt)(1 − yt)}{1 − xt − yt + xyt^{2} − x^{2}y^{2}t^{4}}

that is

Card(Z_{x,y}^{≥2}; t) = ln \frac{1}{1 − xt − yt + xyt^{2} − x^{2}y^{2}t^{4}} − ln \frac{1}{(1 − xt)(1 − yt)} .

Since Z_{x,y} = X_{x} + X_{y} + Z_{x,y}^{≥2} , we have

Card(Z_{x,y}; t) = ln \frac{1}{1 − xt − yt + xyt^{2} − x^{2}y^{2}t^{4}} .

In particular, for t = 1 , we obtain the series

∑_{m+n≥1} z_{m,n} \frac{x^{m}y^{n}}{m + n} = ln \frac{1}{1 − x − y + xy − x^{2}y^{2}}  (24)

from which we have that

z_{m,n} = (m + n)[x^{m}y^{n}] ln \frac{1}{1 − x − y + xy − x^{2}y^{2}} .

Identity (24) can also be obtained by (5) using the formula

∑_{m+n≥1} z_{m,n} \frac{x^{m}y^{n}}{m + n} = ∫_{0}^{x} Z (t, \frac{y}{x}t) \frac{dt}{t} .

Third formula. We can obtain another explicit formula for the numbers z_{m,n} expanding the series Card(Z_{x,y}^{≥2}; 1) . Indeed we have

Card(Z_{x,y}^{≥2}; 1) = ln \frac{1}{1 − \frac{x^{2}}{1 − x} \frac{y^{2}}{1 − y}}

= ∑_{k≥1} \frac{1}{k} (\frac{x^{2}}{1 − x})^{k} (\frac{y^{2}}{1 − y} )^{k}

= ∑_{k≥1} \frac{1}{k} ∑_{m≥0} \binom{m − k − 1}{k − 1}x^{m} ∑_{n≥0} \binom{n − k − 1}{k − 1}y^{n}

= ∑_{m,n≥0} [∑_{k≥1} \binom{m − k − 1}{k − 1}\binom{n − k − 1}{k − 1}\frac{m + n}{k}] \frac{x^{m}y^{n}}{m + n} .

Hence, for m, n ≥ 2 , we have the identity

z_{m,n} = ∑_{k≥0} \binom{m − k − 2}{k}\binom{n − k − 2}{k}\frac{m + n}{k + 1} .  (25)

7. Types

Let z̃_{m,n} be the number of (0, 1)-necklaces without zigzags with m 1’s and n 0’s. Equivalently z̃_{m,n} is the number of types of circular binary strings without zigzags with m 1’s and n 0’s. See [9, 1] for the theory of types of structures and [5] for the theory of type of cyclic structures.

Since Z_{x,y}^{≥2} = L ∘ (G_{x}^{≥2} · G_{y}^{≥2}) , it follows that the corresponding species of types is given by

Z̃_{x,y}^{≥2} = { \atop L ∘ (G_{x}^{≥2} · G_{y}^{≥2})} = L^{⟲} ⟲ (G_{x}^{≥2} · G_{y}^{≥2}) .

Similarly, if Z_{x,y,k}^{≥2} is the cyclic species of all circular binary strings without zigzags with exactly k external blocks, then

Z_{x,y,k}^{≥2} = \frac{X^{k}}{k} ∘ (G_{x}^{≥2} · G_{y}^{≥2})

and consequently

{ \atop Z_{x,y,k}^{≥2}} = (\frac{X^{k}}{k} )^{⟲} ⟲ (G_{x}^{≥2} · G_{y}^{≥2}) .

Hence it follows that

Card({ \atop Z_{x,y,k}^{≥2}}; t) = Z_{k} (\frac{x^{2}t^{2}}{1 − xt} \frac{y^{2}t^{2}}{1 − yt}, \frac{x^{4}t^{4}}{1 − x^{2}t^{2}} \frac{y^{4}t^{4}}{1 − y^{2}t^{2}} , …, \frac{x^{2k}t^{2k}}{1 − x^{k}t^{k}} \frac{y^{2k}t^{2k}}{1 − y^{k}t^{k}} )

where

Z_{k}(x_{1}, x_{2}, …, x_{k}) = \frac{1}{k} ∑_{d|k} φ(d)x_{d}^{k/d}

is the indicatrice series for k-cycles [1, 9, 5], where φ is the Euler function. Then, for t = 1 , we have

Card({ \atop Z_{x,y,k}^{≥2}}; 1) =

= \frac{1}{k} ∑_{d|k} φ(d) (\frac{x^{2d}}{1 − x^{d}} \frac{y^{2d}}{1 − y^{d}} )^{k/d}

= \frac{1}{k} ∑_{d|k} φ(d)\frac{(x^{d})^{2k/d}}{1 − x^{d}} \frac{(y^{d})^{2k/d}}{1 − y^{d}}

= \frac{1}{k} ∑_{d|k} φ(d) ∑_{m≥0} \binom{m − k/d − 1}{k/d − 1} x^{md} ∑_{n≥0} \binom{n − k/d − 1}{k/d − 1} y^{nd}

= ∑_{m,n≥0} \frac{1}{k} ∑_{d|k} \binom{m − k/d − 1}{k/d − 1}\binom{n − k/d − 1}{k/d − 1}φ(d) x^{md}y^{nd}

= ∑_{m,n≥0} \frac{1}{k} ∑_{{d|m , d|n \atop d|k}} \binom{m/d − k/d − 1}{k/d − 1}\binom{n/d − k/d − 1}{k/d − 1}φ(d) x^{m}y^{n}

= ∑_{m,n≥0} [\frac{1}{k} ∑_{{d|m , d|n \atop d|k}} \binom{m/d − k/d}{k/d}\frac{k/d}{(m − k)/d}\binom{n/d − k/d}{k/d}\frac{k/d}{(n − k)/d}φ(d)] x^{m}y^{n} .

It follows that the number of all (0, 1)-necklaces without zigzags with m 1’s, n 0’s and k external blocks is given by

z̃_{m,n}(k) = ∑_{d|(m,n,k)} \binom{(m − k)/d}{k/d}\binom{(n − k)/d}{k/d}\frac{kφ(d)}{(m − k)(n − k)}  (26)

where (m, n, k) is the greatest common divisor of m, n and k. Then, since z̃_{m,n} = ∑_{k≥1} z̃_{m,n}(k) , we have

z̃_{m,n} = ∑_{k≥1} [ ∑_{d|(m,n,k)} \binom{(m − k)/d}{k/d}\binom{(n − k)/d}{k/d}\frac{kφ(d)}{(m − k)(n − k)}]  (27)

where in the sum the index k is at most min(m/2, n/2) . In particular we have

z̃_{n} = z̃_{n,n} = ∑_{k=1}^{⌊n/2⌋} [ ∑_{d|(n,k)} \binom{(n − k)/d}{k/d}^{2} \frac{kφ(d)}{(n − k)^{2}} ] .  (28)

\begin{matrix}z̃_{m,n} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 3 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 4 & 1 & 0 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 \\ 5 & 1 & 0 & 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 6 & 1 & 0 & 1 & 1 & 3 & 4 & 7 & 8 & 11 & 14 & 17 \\ 7 & 1 & 0 & 1 & 1 & 3 & 5 & 8 & 12 & 17 & 23 & 30 \\ 8 & 1 & 0 & 1 & 1 & 4 & 6 & 11 & 17 & 27 & 37 & 52 \\ 9 & 1 & 0 & 1 & 1 & 4 & 7 & 14 & 23 & 37 & 57 & 82 \\ 10 & 1 & 0 & 1 & 1 & 5 & 8 & 17 & 30 & 52 & 82 & 128 \end{matrix}

Figure 2: Numbers of types of circular binary strings without zigzags.

See Figure for the first values of z̃_{m,n}. The first few values of z̃_{n} are: 0, 1, 1, 2, 3, 7, 12, 27, 57, 128, 285, 659, 1518, 3561, 8389, 19936, 47607, 114397, 276018, 669035.

When (m, n) = 1 identity (27) simplifies in

z̃_{m,n} = ∑_{k≥1} \binom{m − k}{k}\binom{n − k}{k}\frac{k}{(m − k)(n − k)} .  (29)

Finally consider the number s̃_{n} of all (0, 1)-necklaces of length n without zigzags. Then

s̃_{n} = ∑_{k=0}^{n} z̃_{n,n−k} .

The first few values of s̃_{n} are: 0, 2, 2, 2, 3, 4, 5, 6, 8, 10, 15, 20, 31, 42, 64, 94, 143, 212, 329, 494, 766, 1170, 1811, 2788, 4341.

Acknowledgments. The authors are grateful to Gian-Carlo Meloni, Douglas Rogers and the referee for useful suggestions and comments.

References

[1] F. Bergeron, G. Labelle, P. Leroux, “Combinatorial Species and Tree-like Structures”, Encyclopedia of Mathematics and Its Applications 67, Cambridge University Press, Cambridge, 1998.

[2] L. Comtet, “Advanced Combinatorics”, Reidel, Dordrecht-Holland, Boston, 1974.

[3] F. Dai, M. Dhawan, C. Wu, J. Wu, On Solutions to a Seating Problem. 2002 ISCA International Conference on Parallel and Distributed Computing Systems, 2002.

[4] P. Flajolet, R. Sedgewick, “An Introduction to the Analysis of Algorithms”, Addison-Wesley 1996.

[5] S. Fontanesi, E. Munarini, Cyclic Species, preprint.

[6] R.L. Graham, D.E. Knuth, O. Patashnik, “Concrete Mathematics”, Addison-Wesley, Reading, MA, 1989.

[7] D.H. Greene, D.E. Knuth, “Mathematics for the Analysis of Algorithms”, Birkäuser 1982.

[8] M.L.J. Hautus, D.A. Klarner, The Diagonal of a Double Power Series, Duke Math. J. 38 (1971), 229-235.

[9] A. Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), 1–82.

[10] D. Merlini, D. Rogers, R. Sprugnoli, M.C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math. 49 (1997), 301–320.

[11] E. Munarini, N. Zagaglia Salvi, Binary strings without zigzags, to appear in the Seminaire Lotharingien de Combinatoire.

[12] M.P. Schützenberger, Context-free language and pushdown automata, Information and Control 6 (1963), 246–264.

[13] L. W. Shapiro, S. Getu, W. J. Woan, L. C. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991), 229–239.

[14] R. Sprugnoli, Riordan Arrays and Combinatorial Sums, Discrete Math. 132 (1994), 267–290.

[15] R.P. Stanley, “Enumerative Combinatorics”, Volume 2, Cambridge Studies in Advanced Mathematics 62, Cambridge University Press, Cambridge, 1999.

[16] P.R. Stein, M.S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math. 26 (1979), 261–272.