18 312 Algebraic Combinatorics Lionel Levine Lecture 21 Lecture date April 28 2011 1 Notes by Jacob Bower De Bruijn Sequences Todays lecture begins with a discussion of De Bruijn sequences We have the following definition Definition 1 A binary De Bruijn Sequence of order n is a string of bits bi 0 1 b b1 b2n such that ever string of lengh n a1 an 0 1 n occurs exactly once consecutively in b In other words k such that bk a1 bk 1 a2 bk n 1 an where we take indices mod 2n This definition can perhaps best be illustrated with the example Example 2 A De Bruijn sequence of order 3 is 00010111 One can check by examination that all possible bitstrings of length three occur once and only once in this sequence Remarkably it turns out that De Bruin sequences of order n exist for all n We will shortly see a theorem that enumerates them but before we look at this we first examine the definition of a De Bruijn graph an object that will play an essential role in our proof of our enumeration theorem Definition 3 A De Bruijn graph is a directed graph DB n 0 1 n 1 0 1 n that is a graph with vertex set 0 1 n 1 and edge set 0 1 n where there is an edge from a a1 an 1 to a0 a01 a0n 1 iff a2 a01 a3 a02 an 1 a0n 2 This is equivalent to saying there is an edge from a to a0 iff a is a prefix of some string b1 bn and a0 is a suffix of the same string We can again look at an example to illustrate this definition 21 1 Example 4 The graph of DB 3 is With this definition we are ready to state and prove our theorem about the enumeration of Be Bruijn sequences Theorem 5 Binary De Bruijn sequences of order n exist for all n and there are exactly n 1 22 of them Proof To begin our proof we note that a De Bruijn sequence of order n is just an Eulerian tour of DBn We first wish to prove that an Eulerian Tour exists To do this we note that DBn is balanced This is because we can take any sequence of length n 1 and delete the last digit then add a 0 or 1 in front giving us that indeg 2 for each vertex Similarly we can take any sequence of length n 1 and delete the first digit then add a 0 or a 1 to the end giving us that outdeg 2 for each vertex Because indeg outdeg 2 our graph is balanced As we have seen in previously an Eulerian tour exists as long as a graph is balanced so we know that that for all n there exists a binary De Bruijn sequence of order n Now that we have proved the existence of De Bruijn sequences we want to prove their enumeration From the equivalence of Eulerian Tours in DBn and De Bruijn sequences combined with results we have found from graph theory we have DB sequences of order n Eulerian Tours of DBn X DBn e e E X DBn e e E Y outdeg v 1 v V X DBn e e E 21 2 The last equation here comes from the fact that every vertex of the graph has outdeg 2 as we discussed before We thus want to count the number of spanning trees of DBn in order to cound the number De Bruijn sequences To do this we us a special trick Consider any two vertices v and w in DBn and count the number of paths of length n 1 between v and w In particular let v v1 vn 1 w w1 wn 1 Looking at these there is only 1 way to append our two sequences In particular we must do it in the fashion v1 vn 1 w1 wn 1 v1 v2 w1 w2 wn 1 v1 v2 v3 w2 w3 wn 1 v1 vn 1 w1 wn 1 Because we have exactly one path from v to w must have 1 n 1 A of length n 1 for all vertices v and w we 1 1 1 where A is the 2n 1 2n 1 adjacency matrix of DBn We should then see the Laplacian Matrix having eigenvalues of 0 with multiplicity 1 and 2 with multiplicity 2n 1 Finally we apply matrix tree theory to arrive at the result X DB sequences of order n DBn e e E X 1 2n 1 1 2n 1 e E X 22n 1 1 2n 1 e E n2 2 2n 1 1 2n 1 n 1 22 2 21 3 Remark 6 One may note that the number of De Bruijn sequences is n 1 22 22n n where 22 counts the number of all possible bitstrings of length 2n This leads to the question if there is a bijection pairs of DB sequences of order n all binary bitstrings of length 2n It turns out there is and this fact was proved by two MIT students Kishore and Bidkhori illustrating the many open and accessible problems that exist in the exciting field of combinatorics This concludes our discussion of De Bruijn sequences 2 Po lya Theory The general idea of Po lya theory is counting things up to certain equivalence classes Let us look at a very simple example to start Example 7 Let us consider the number of colorings of 5 squares in a line one with each of n colors That is the number of colorings of It is straight forward to see that under no restrictions the number of colorings is n5 because we can choose any of the n colors seperately for each of the 5 squares As a less trivial example let us impose the equivalence that two colorings are the same if they are mirror images of each other That is we have equivalence Under this equivalence first let us consider the number of colorings that are equivalent to themselves This is all colorings of the form 21 4 Because we have three relevent colors to choose and n choices for each of them there are n3 such colorings All other colorings have exactly one unique equivalent coloring so we take the remaining n5 n3 colorings and divide them by 2 to account for the fact each one of these is equivalent to exatly one other We then conclude equivalence classes of colorings n3 symmetric colorings n5 n3 non symmetric colorings 2 1 n5 n3 2 In general we have some finite set X where X k a group S Sk a subgroup of the group of all permutations of X and a finte set of colors C Then the set of colorings is Y C x f X C We then consider some action G that acts on Y so that G Y Y We then wish to count the orbits YG i e equivalence of colorings As a more …