Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Enumerating words with forbidden factors
Some things that could be better known

Richard Pinch
Institute of Mathematics and its Applications

07 February 2019

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

In this talk . . .

Some facts, well-known and less-well-known, about
recurrence relations and power series
Counting walks on graphs
Counting words with forbidden factors
An application

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

In this talk . . .

Some facts, well-known and less-well-known, about
recurrence relations and power series
Counting walks on graphs
Counting words with forbidden factors
An application

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

In this talk . . .

Some facts, well-known and less-well-known, about
recurrence relations and power series
Counting walks on graphs
Counting words with forbidden factors
An application

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

In this talk . . .

Some facts, well-known and less-well-known, about
recurrence relations and power series
Counting walks on graphs
Counting words with forbidden factors
An application

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

A curiosity?

1= 0.011235 . . .
89

Words without runs

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

A curiosity?

189= 0.011235955056179 . . .

Words without runs

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

A curiosity?

189= 0.0112358
13213455..

.

Words without runs

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

A curiosity?

Let Fn denote the nth Fibonacci number (with F0 = 0).
∞X
1=Fn 10−n−1 .
89
n=0

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

A curiosity?

This is simply the power series expansion∞Xz=Fn z n1 − z − z2n=01
. The occurence of the polynomial
evaluated at z = 102
1 − z − z should come as no surprise, as it is the driving
polynomial of the Fibonacci sequence.

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Not a curiosity

The power series with coefficients which satisfy a linear
recurrence relation are precisely the formal power series
attached to rational functions: indeed, the denominator of therational function will be the driving polynomial of the linear
recurrence.

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Not a curiosity

The polynomials over a field K form a K -algebra with dual thespace of infinite sequences.
The linear recurrent sequences form the restricted dual, andhence have a coalgebra structure.
Indeed, the polynomials and the linear recurrent sequences
form bialgebras and in two different ways.

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Generating functions

Let (rn ) be a sequence defined by a recurrence relation
rn+k = ck −1 rn+k −1 + · · · + c0 rn
for n ≥ 0, with c0 6= 0, subject to given initial conditions onr0 , . . . , rk −1 . Let f (x) be the auxiliary polynomialf (x) = x k − ck −1 x k −1 + · · · + c0 .
Let the roots of f be α1 , . . . αk : we shall assume for simplicity ofthis exposition that f has no repeated roots.

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Generating functions
The generating function as a formal power series is equal to arational function of the form
∞Xn=1

rn z n =p(z)f̃ (z)where p is a polynomial of degree ≤ k − 1, determined by theinitial conditions, and f̃ is the reciprocal polynomialf̃ (z) =kY
i=1(1 − αi z) = (−1/c0 )z k f (1/z) .

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Traces

We may also express any such generating function askX
i=1βi,
1 − αi zthat is, as a tracetrβ
1 − αz.

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Impulse response sequence

The impulse response sequence has initial values 0, . . . , 0, 1,
so that every sequence is a linear combination of this and its
left shifts. The corresponding generating function has initialterm z k −1 .
We have
1/f 0 (α)= z k −1 + O(z k )tr(1 − αz)as the generating function of the IRS in trace form.

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Walks on graphs

Let G = (V , E) be a directed graph with possibly multiple
edges, and A the adjacency matrix with entry Aij counting thenumber of edges from vertex vi to vertex vj . Then the entries ofthe matrix power An , for n ≥ 0, count the number of directed
paths of length n between vertices.

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Walks on graphs

We can regard the formal power series
XAn z nn≥0

as either a formal power series over the matrix ring or as amatrix whose entries are formal power series.

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Generating function

Let G = (V , E) be a directed graph with possibly multiple
edges, and
It is then easy to see that
X(I − Az) An z n  = In≥0and since I − Az is invertible, this matrix formal power series is
an expression for the inverse (I − Az)−1 .

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Formal power series

We are considering the formal term z n as encoding paths oflength n. Let B be a matrix in which every entry is a polynomialin z with integer coefficients and with zero constant term: sothat Az is an example of such a matrix. Then the sumXBnn≥0converges (formally speaking in the z-adic topology) to a formalpower series in z over the ring of matrices.

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Counting paths

If we want to count the number of paths of length n from a given
vertex i to vertex j, then we write
Xei> An z n  ejn≥0where ei is the coordinate vector for the i-th position.

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Counting paths

We have the generating functionei> (I − Az)−1 ej
and expanding (I − Az)−1 we obtain
1e> adj(I − Az)ej
det(1 − Az) i
which is a rational function with the characteristic polynomial ofA as denominator.

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Forbidden factors

We give as a worked example the problem of counting words
over a finite alphabet with forbidden factors: that is, words withno consecutive substring drawn from a finite forbidden set.

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

An application

The specific application that motivated us to look at thisproblem comes from the problem of counting binary words in
prefix normal binary words: words over the alphabet {0, 1} withthe property that no factor has more occurrences of the symbol
1 than the prefix of the same length. This problem isaddressed, for example, by Burcsi et al. They obtain an upperbound of the form 2n−lg n+1 by observing that a binary word in
prefix form for which the first k symbols are an initial run of 1k −1
followed by a 0 necessarily has the property that it has no factorof the form 1k .

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runsde Bruijn graphs

We wish to enumerate words whose factors of length k comefrom a permissible set S. The de Bruijn graph or state machine
GS has vertex set S. There is a directed edge from a vertex
xY ∈ S to a vertex Yz ∈ S, where x, z denote single letters andY denotes a string of length k − 1: following an edge represents
the movement one place of a k -long window into the word.
This reduces the problem to one of enumerating walks in thegraph GS .

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runsde Bruijn graphs

We wish to enumerate words whose factors of length k comefrom a permissible set S. The de Bruijn graph or state machine
GS has vertex set S. There is a directed edge from a vertex
xY ∈ S to a vertex Yz ∈ S, where x, z denote single letters andY denotes a string of length k − 1: following an edge represents
the movement one place of a k -long window into the word.
This reduces the problem to one of enumerating walks in thegraph GS .

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Words without runs

We illustrate the application of power series to obtain this upperbound for binary words with no factor 1k .
The de Bruijn graph has 2k − 1 vertices, labelled by all binarystrings except 1k , and each vertex xY has two arrows tovertices Y 0 and Y 1: except for the vertex 01k −1 which has onlya single arrow, to 1k −1 0.

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Words without runs

Fix k ≥ 2 and consider the number F (n) of binary words oflength n with no runs of k consecutive 1. We know that F
satisfies a linear recurrence relation which we can obtain fromits de Bruijn diagram. In this case, it is easy to see that F
satisfies the recurrence
F (n) = F (n − 1) + · · · + F (n − k )with initial conditions F (i) = 2i , i = 0, . . . , k − 1.

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

The characteristic equation

Let f (z) = z k − (z k −1 + · · · 1) be the auxiliary polynomial of thisrecurrence. It is clear that f has no roots of absolute value
greater than or equal to 2. Let α1 denote the largest real root.
Theorem
The dominant root satisfies α1 < 2 − 21kf has no repeated roots
All roots other than α1 are inside the unit circle.

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

A picture

0.98103-0.98311-0.97841

2

Words without runs

Close

Introduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

The characteristic equation

This already gives us the asymptotic behaviour of F . For a
more explicit bound we need to locate the other roots and to
estimate f 0 (α) as α runs over the roots of f .

Theorem
The roots of f within the unit circle are at distance of order 1/kfrom the k − 1 non-trivial k -th roots of unity.

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Conclusion

We conclude that f 0 (α) ∼ k , for α one of the roots inside theunit circle. Hence we can obtain an estimate strong enough togive Theorem 15 of [BFLRS]
nX
k =1

Fk (n − k ) < 2n−lg n+1 ,CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Summary

Recurrent sequences and the associated power series
have a rich natural algebraic structureThis structure is useful in a wide range of applications in
combinatorics

CloseIntroduction

Power series

Generating functions

Counting walks

Forbidden factors

Words without runs

Summary

Recurrent sequences and the associated power series
have a rich natural algebraic structureThis structure is useful in a wide range of applications in
combinatorics

CloseIntroduction

Power series

The end

Questions?

Comments!

Generating functions

Counting walks

Forbidden factors

Words without runs

Close