Des. Codes Cryptogr. DOI 10.1007/s10623-016-0322-4

Mapping prefer-opposite to prefer-one de Bruijn sequences Amir Rubin1

· Gera Weiss1

Received: 3 April 2016 / Revised: 14 December 2016 / Accepted: 16 December 2016 © Springer Science+Business Media New York 2016

Abstract We present a mapping of the binary prefer-opposite de Bruijn sequence of order n onto the binary prefer-one de Bruijn sequence of order n − 1. The mapping is based on the differentiation operator D(b1 , . . . , bl ) = b2 −b1 , b3 −b2 , . . . , bl −bl−1  where bit subtraction is modulo two. We show that if we take the prefer-opposite sequence b1 , b2 , . . . , b2n , apply D to get the sequence bˆ1 , . . . , bˆ2n −1  and drop all the bits bˆi such that bˆi , . . . , bˆi+n−1  is a substring of bˆ1 , . . . , bˆi+n−2 , we get the prefer-one de Bruijn sequence of order n − 1. Keywords De Bruijn sequences · Prefer one · Prefer opposite Mathematics Subject Classification 68R15 · 68R10 · 05A05

1 Introduction A binary de Bruijn sequence of order n is a cyclic sequence of bits (elements of the set {0, 1}) in which every string in {0, 1}n occurs exactly once as a substring [2]. The n dimensional binary de Bruijn graph is a graph whose vertices are the binary strings of length n and each vertex v = b1 , . . . , bn  is connected with a directed edge to the vertices shl-one(v) = b2 , . . . , bn , 1 and shl-zero(v) = b2 , . . . , bn , 0. Formally the graph is Bn = V, E where V = {0, 1}n and E = {v, shl-one(v) : v ∈ {0, 1}n } ∪ {v, shl-zero(v) : v ∈ {0, 1}n }. The operators shl-one(s) and shl-zero(s) drop the left-most bit of s and add one or zero, respectively, at the right. They are so called because they “shift” the bits to the left. The de Bruijn sequences are in one-to-one correspondence with the Hamiltonian cycles in the de

Communicated by M. Paterson.

B

Gera Weiss [email protected] Amir Rubin [email protected]

1

Department of Computer Science, Ben Gurion University of the Negev, Beer-Sheva, Israel

123

A. Rubin, G. Weiss 0, 0, 1

0, 0, 0

0, 1, 1

0, 1, 0

1, 0, 1

1, 0, 0

1, 1, 1

1, 1, 0

Fig. 1 The Hamiltonian cycle generated by the prefer-one construction on B3

Bruijn graph, as follows: (1) Concatenating the leftmost bit of the vertices in a cycle produces a de Bruijn sequence of order n; and (2) A cycle can be constructed from a de Bruijn sequence b1 , . . . , b2n  of order n by visiting the vertex b1 , . . . , bn , then b2 , . . . , bn+1  and so on. For example, Fig. 1 shows the de Bruijn graph B3 . The highlighted cycle corresponds to the de Bruijn sequence constructed by the classic “prefer-one” construction proposed by Martin [4] and specified as follows. Algorithm 1 The prefer-one construction. Start from the vertex with n zeros. From any vertex v = b1 , . . . , bn  go to the vertex shl-one(v) = b2 , . . . , bn , 1 if not already visited, otherwise, choose the other successor shl-zero(v) = b2 , . . . , bn , 0. If the two possible successors were already visited, stop.

This, of course, is not the only Hamiltonian cycle in this graph (there are two to the power 2n−1 − n such cycles). Another construction that we focus on in this paper is called “prefer-opposite” [1]. In this construction, instead of preferring shl-one(v) and going to shl-zero(v) only if shl-one(v) was already visited, we prefer the successor shl-opp(v) = b2 , . . . , bn , 1 − bn  and go to shl-same(v) = b2 , . . . , bn , bn  only if shl-opp(v) has already been visited. The names shl-opp() and shl-same() are abbreviations for “shift-left-and-pushan-opposite-bit” and “shift-left-and-push-the-same-bit” respectively. Algorithm 2 The prefer-opposite construction. Start from the vertex with n zeros. From any vertex v = b1 , . . . , bn  go to the vertex shl-opp(v) = b2 , . . . , bn , 1 − bn , if not already visited, otherwise, choose the other successor shl-same(v)=b2 , . . . , bn , bn . If the two possible successors were already visited, stop.

In B3 , for example, this gives the cycle 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0. Note that this is not an Hamiltonian cycle because it does not contain the vertex 1, 1, 1. To get an Hamiltonian cycle on Bn , for any n, one an add an exception to our preference saying that 1, . . . , 1 is preferred over 1, . . . , 1, 0. In our paper we will consider the sequence without this exception as the correctness of the main result is independent of this choice, as discussed at the end of the introduction. The focus of this paper is the relation between the cycle generated by the preferopposite construction on Bn and the cycle generated by the prefer-one construction on Bn−1 .

123

Mapping prefer-opposite to prefer-one de Bruijn sequences

To this end, we use an operator D : {0, 1}n → {0, 1}n−1 defined by Lempel in [3] as: D(b1 , . . . , bn ) = b2 − b1 , . . . , bn − bn−1  where subtraction is modulo two. The choice of the letter D is because this operator is sometimes considered to be a discrete variant of differentiation. Because D(shl-opp(s)) = shl-one(D(s)) and D(shl-same(s)) = shl-zero(D(s)) for any s ∈ {0, 1}n , and because the prefer-opposite construction becomes textually identical to the prefer-one construction when we replace shl-opp() with shl-one() and shl-same() with shl-zero(), we started to examine the relations between the Hamiltonian cycle s1 , s2 , . . . , s2n −1  generated by the prefer-opposite sequence on n bits, the D images D(s1 ), D(s2 ), . . . , D(s2n −1 ), and the Hamiltonian cycle ˆs1 , sˆ2 , . . . , sˆ2n−1  generated by the prefer-one construction on n − 1 bits. For example, for n=3, s1 = 0, 0, 0, s2 = 0, 0, 1, s3 = 0, 1, 0, s4 = 1, 0, 1, s5 = 0, 1, 1, s6 = 1, 1, 0, and s7 = 1, 0, 0. The images under D are: D(s1 ) = 0, 0, D(s2 ) = 0, 1, D(s3 ) = 1, 1, D(s4 ) = 1, 1, D(s5 ) = 1, 0, D(s6 ) = 0, 1, and D(s7 ) = 1, 0. The prefer-one sequence over n − 1 is sˆ1 = 0, 0, sˆ2 = 0, 1, sˆ3 = 1, 1, sˆ4 = 1, 0. It can be seen, in this example, that if we ignore duplicates by taking only the first occurrence of each element in D(s1 ), . . . , D(s7 ), we get the sequence sˆ1 , . . . , sˆ4 . The main contribution of this paper is a proof that the above example is not a coincidence, i.e., we prove that applying D on the sequence generated by the prefer-opposite construction on Bn , and then deleting the second occurrence of every vertex gives the sequence generated by the prefer-one construction on Bn−1 . Regarding the vertex 1, . . . , 1 that was not visited by our prefer-opposite construction. Note that D(1, . . . , 1) is going to be dropped as it is equal to D(0, . . . , 0) which is the first vertex in the sequence. Therefor, our main result holds also for the full Hamiltonian cycle where the vertex 1, . . . , 1 is added between the vertices 0, 1, . . . , 1 and 1, . . . , 1, 0.

2 Observations, definitions, and an overview of the proof As said above, the main observation that led us to examine the relations between the preferopposite and the prefer-one sequences is Observation 1 For every s ∈ {0, 1}n , shl-zero(D(s)) = D(shl-same(s)) and shl-one(D(s)) = D(shl-opp(s)). D produces tuples that are shorter by one bit than the input. This means that, when D is applied to the list of vertices generated by the prefer-opposite construction, we get 2n − 1 elements in the set {0, 1}n−1 whose size is 2n−1 , i.e., we have repetitions. Our approach is to filter out the repetitions by taking only the first occurrence of every element. This leads to the following definition: Definition 1 For the prefer-opposite sequence s1 , . . . , s2n −1  on n bits, let I be defined by I = i : D(si ) ∈ / {D(s1 ), . . . , D(si−1 )}. I is an ordered set using the standard order on natural numbers. This set can also be defined without a direct reference to D using the notation s, the complement of s, defined by: Definition 2 b1 , b2 , . . . , bn  = 1 − b1 , 1 − b2 , . . . , 1 − bn . Since D maps the vertices s and s to the same image, and them alone, we have the following equivalent definition of I :

123

A. Rubin, G. Weiss

Observation 2 I = i : si ∈ / {s1 , . . . , si−1 }. We aim to show that the subsequence obtained by applying D to the vertices whose indexes are in I gives the prefer-one sequence. For this, we denote the elements of I by I = i 1 , . . . , i 2n−1 . Looking at two consecutive element i k , i k+1 in I , they may be consecutive also in the original sequence, i.e., i k+1 = i k + 1, or not, i.e., i k+1 > i k + 1. In the first case, as we will show, it is possible to apply Observation 1 directly to get what we are aiming for. For the second case, we need to first examine the relations between D(sik ) and D(sik+1 ). Focusing on this second case, our proof goes by fixing some “pivot” p such that p ∈ / I and p + 1 ∈ I (i.e, p = i k+1 − 1). Then, since our proposal is to skip indexes that are not in I , we define the index p  to be the last index in I before p: Definition 3 For p ∈ {1, . . . , 2n − 1} \ I we define p  = max{i < p : i ∈ I }. In our case, p  = i k . Because the successor of s p in the prefer-opposite sequence is sik+1 , the main step of our proof is to show that D(s p ) and D(s p ) have the same successors in the n − 1 dimensional binary de Bruijn graph. By the definition of D, this is only possible when s p = s p or s p = comp(s p ) where the function comp, a shorthand for “companion”, is defined by: Definition 4 comp(b1 , b2 , . . . , bn ) = 1 − b1 , b2 , . . . , bn . We will show that these are indeed the relationship between s p and s p and we will use this fact to conclude that D(i 1 ), . . . , D(i 2n−1 ) is the prefer-one sequence.

3 A formal proof of the main result 2 −1 In this section, we show that if S = si i=1 is the sequence of vertices generated by the prefer-opposite construction on n bits, then D(s j ) j∈I is the sequence of vertices generated by the prefer-one construction on n − 1 bits. We begin with a series of propositions that identify possible ordering (in the sequence generated by the prefer-opposite construction) of vertices that are related to an index p such that p ∈ / I and p + 1 ∈ I . We use the operator idx() that denotes the index of a vertex in S, i.e., idx(si ) = i. n

Proposition 1 If p ∈ / I and p + 1 ∈ I , then p ≥ idx(shl-opp(s p )). Proof Because p ∈ / I , we have that idx(s p ) < p. Because the vertex that comes after any s in the sequence generated by the prefer-opposite construction is either shl-opp(s) or shl-same(s) and because shl-opp(s) comes first in that construction, we know that idx(shl-opp(s)) ≤ idx(s) + 1 for any s. We also have that shl-opp(s) = shl-opp(s) for any s. Putting the two statements together we obtain that idx(shl-opp(s p )) = idx(shl-opp(s p )) ≤ idx(s p ) + 1 ≤ p. 

Proposition 2 If p ∈ / I and p + 1 ∈ I , then the vertex that immediately follows s p is shl-same(s p ). Proof Assume towards contradiction that s p+1 = shl-same(s p ). Then s p+1 = shl-opp(s p ) (because this is the only other vertex that can follow s p ). Since p + 1 ∈ I , we have that 

p + 1 < idx(s p+1 ) = idx(shl-opp(s p )) in contradiction to Proposition 1.

123

Mapping prefer-opposite to prefer-one de Bruijn sequences

Proposition 3 If p ∈ / I and p + 1 ∈ I , then the vertex that immediately follows s p is shl-opp(s p ). Proof Assume towards contradiction that the vertex that immediately follows s p is not shl-opp(s p ). Then it must be shl-same(s p ). Since p ∈ / I, idx(s p ) < p. Therefore, idx(shl-same(s p )) ≤ p < p+1. From Proposition 2 we have that p+1 = idx(shl-same(s p )). Together we get that idx(shl-same(s p )) < idx(shl-same(s p )). This gives, by the definition of I , that idx(shl-same(s p )) ∈ / I , in contradiction to our assumption that p + 1 ∈ I . 

Proposition 4 If p ∈ / I and p + 1 ∈ I , then p ≥ idx(shl-opp(s p )) and shl-opp(s p ) immediately follows comp(s p ). Proof From Proposition 2 and because shl-same(s) always comes after shl-opp(s) in the prefer-opposite construction, we have that p ≥ idx(shl-opp(s p )). Because a vertex and its companion share the same possible successors in the de Bruijn graph, and because the vertex that comes after s p in the sequence is shl-same(s p ), we get that the vertex that comes after comp(s p ) is shl-opp(s p ). 

Proposition 5 If p ∈ / I and p + 1 ∈ I , then p < idx(shl-same(s p )) and shl-same(s p ) immediately follows comp(s p ). Proof From Proposition 2, since p + 1 ∈ I , we have p < idx(shl-same(s p )). Because every vertex in the de Bruijn graph shares its two successors with its companion and because shl-same(s p ) = shl-same(s p ) we get that the vertex preceding shl-same(s p ) must be either s p or comp(s p ). From Proposition 3 and from Proposition 1 we know that p > idx(s p ), thus the vertex that comes before shl-same(s p ) in the prefer-opposite construction must be comp(s p ), i.e., idx(shl-same(s p )) = idx(comp(s p )) + 1 = idx(comp(s p )) + 1. The last equality is because we have that comp(s) = comp(s) for any s. 

In summary, the above propositions identify two possible linear orders among the mentioned vertices: First configuration: If idx(comp(s p )) < idx(s p ), then the only linear order that is consistent with the inequalities and equalities in the above propositions is: idx(shl-same(s p )) = idx(comp(s p )) + 1 ≥ idx(shl-same(s p )) = idx(s p ) + 1 ≥ idx(shl-opp(s p )) = idx(s p ) + 1 ≥ idx(shl-opp(s p )) = idx(comp(s p )) + 1 and by the definition of I we get that, in this case, the indexes of shl-same(s p ), s p , shl-opp(s p ) and of comp(s p ) are in I and that the indexes of s p and of shl-opp(s p ) are not in I , as depicted on the left side of Fig. 2.

123

A. Rubin, G. Weiss shl-same(sp )

shl-same(sp )

comp(sp )

comp(sp )

.. .

.. .

shl-same(sp )

shl-same(sp )

(a)

sp

sp

. ..

. ..

shl-opp(sp )

shl-opp(sp )

sp

comp(sp )

.. .

.. .

shl-opp(sp )

shl-opp(sp )

comp(sp )

sp

If sp is after comp(sp )

(b)

If sp is before comp(sp )

Fig. 2 The two cases possible by Propositions 1–5. The sequences start at the bottom and advance upwards. In both diagrams, the indentation to the right indicates vertices whose indexes are not in I . Note that we did not yet prove that the part marked by the vertical dots below s p does not include indices which are in I

Second configuration: If idx(comp(s p )) > idx(s p ), then the only linear order that is consistent with the inequalities and equalities in the above propositions is: idx(shl-same(s p )) = idx(comp(s p )) + 1 ≥ idx(shl-same(s p )) = idx(s p ) + 1 ≥ idx(shl-opp(s p )) = idx(comp(s p )) + 1 ≥ idx(shl-opp(s p )) = idx(s p ) + 1 and by the definition of I we get that, in this case, the indexes of shl-same(s p ), comp(s p ), shl-opp(s p ), and of s p are in I and that the indexes of s p and of shl-opp(s p ) are not in I . This configuration is depicted on the right side of Fig. 2. Our next step, as hinted in the caption of Fig. 2, is to establish that the part marked by the vertical dots below s p does not include indices which are in I . This is central to our proof because it gives us that s p in configuration (a) or comp(s p ) in configuration (b) are directly followed by shl-same(s p ) when vertices that are not in I are dropped. In our notations, as

123

Mapping prefer-opposite to prefer-one de Bruijn sequences

we defined p  to be the last element of I before p, this means that we need to show that p  is either comp(s p ) or s p . Proposition 6 If p ∈ / I and p + 1 ∈ I , then s p ∈ {comp(s p ), s p }. Proof Assume, toward contradiction, that the proposition is false. Consider the first p such that p ∈ / I , p + 1 ∈ I , and s p ∈ / {comp(s p ), s p }. Note that, in both configurations, idx(s p ) and idx(comps p ) are smaller than p. If we are in the first configuration where s p is after comps p : Let q be the first index after idx(s p ) such that q ∈ / I and q + 1 ∈ I . Since in our configuration idx(s p ) ∈ I and idx(s p ) + 1 ∈ / I , we have that q  , the first index in I before q, is idx(s p ). By the minimality of q, it cannot be bigger than p. If q = p we get that s p = s p in contradiction to our assumption. Thus q < p. By the minimality of p, and because q < p, s p = sq  ∈ {sq , comp(sq )}. Thus, we have one of two cases: (a) s p = sq which implies that sq = s p in contradiction to q < p; or (b) s p = comp(sq ) which implies that comp(s p ) = sq that gives us idx(comp(s p )) = q < p in contradiction to Proposition 5. If we are in the second configuration where s p is before comp(s p ): Let q be the first index after idx(comp(s p )) such that q ∈ / I and q + 1 ∈ I . Because, in our configuration, idx(comp(s p )) ∈ I and idx(comp(s p )) + 1 ∈ / I , we have that q  = idx(comp(s p )). By the minimality of q, it cannot be bigger than p. If q = p we get that s p = comp(s p ) in contradiction to our assumption. Thus q < p. By the minimality of p, and because q < p, comp(s p ) = sq  ∈ {comp(sq ), sq }. Thus, we have one of two cases: (a) comp(sq ) = comp(s p ) which implies that sq = s p in contradiction to q < p; (b) comp(s p ) = sq which implies, that comp(s p ) = sq that gives us idx(comp(s p )) = q < p in contradiction to Proposition 5.

 The following three propositions conclude the analysis of the case where p ∈ / I and p + 1 ∈ I by showing that, in this case, the vertices D(s p ) and D(s p+1 ) follow the preferone rule. Proposition 7 If p ∈ / I and p + 1 ∈ I , then D(shl-same(s p )) = D(shl-same(s p )). Proof We have, by Proposition 6, that either s p = comp(s p ) or s p = s p . If s p = comp(s p ) we have that D(shl-same(s p )) = D(shl-same(comp(s p ))) = D(shl-same(s p )). If s p = s p we have D(shl-same(s p )) = D(shl-same(s p )) = D(shl-same(s p )) = D(shl-same(s p )).

 Proposition 8 If p ∈ / I and p + 1 ∈ I , then D(s p+1 ) = shl-zero(D(s p )). Proof By Proposition 2, we have that D(s p+1 ) = D(shl-same(s p )). By Proposition 7 we have that D(shl-same(s p )) = D(shl-same(s p )). Then, by Observation 1, we conclude that D(shl-same(s p )) = shl-zero(D(s p )) 

The above proposition established that, when D is applied to the subsequence defined by I , the step, in the case p ∈ I , p + 1 ∈ / I , is shl-zero(). To complete the claim that this is the sequence generated by the prefer-one construction, we need to also show that the shl-one() option was already used, as established in the next proposition: Proposition 9 If p ∈ / I and p + 1 ∈ I , then there is an i ∈ I smaller or equal to p  such that D(si ) = shl-one(D(s p )) / I . By the definition of I we get that Proof Recall that by the definition of p  we have p  +1 ∈ there exist an i ≤ p  such that si = s p +1 , and i ∈ I . We now show that s p +1 = shl-opp(s p ).

123

A. Rubin, G. Weiss

In the case where s p = s p , we get this from Proposition 3 using the fact that the operators complementation and shl-opp() commute. In the other case, s p = comp(s p ), we get this by Proposition 4 using the fact that shl-opp(s) = shl-opp(comp(s)) for any s. So we have that si = shl-opp(s p ). Applying D on both sides we get: D(si ) = D(shl-opp(s p )) = D(shl-opp(s p )). By observation 1, D(shl-opp(s p )) = shl-one(D(s p )). From the last two equalities we get D(si ) = shl-one(D(s p )). 

The following proposition is a technical step needed in the proof of the main theorem. For this, let I = {i 1 , . . . , i 2n−1 }, i.e., denote the k’th element of I by i k . Proposition 10 If i k + 1 ∈ I , then D(shl-opp(sik )) ∈ {D(s1 ), . . . , D(sik )} if and only if shl-opp(sik ) ∈ {s1 , . . . , sik }. Proof The fact that shl-opp(sik ) ∈ {s1 , . . . , sik } implies that D(shl-opp(sik )) ∈ {D(s1 ), . . . , D(sik )} is trivial, because D is a function. If D(shl-opp(sik )) appears in {D(s1 ), . . . , D(sik )}, then either shl-opp(sik ) ∈ {s1 , . . . , sik }, and our proposition follows, or, because D −1 (s) contains an element and its complement, shl-opp(sik ) = shl-opp(sik ) ∈ {s1 , . . . , sik }. As i k + 1 ∈ I , we also have that sik +1 ∈ / {s1 , . . . , sik }. In our case, as both i k and i k + 1 are in I , i k+1 = i k + 1. Therefore sik +1 is either shl-opp(sik ) or shl-same(sik ). As shl-opp(sik ) ∈ {s1 , . . . , sik } and sik +1 ∈ / {s1 , . . . , sik }, we get that sik +1 = shl-same(sik ) = shl-same(sik ). This gives us that sik +1 = shl-same(sik ). By the construction of the prefer-opposite sequence shl-opp(sik ) ∈ {s1 , . . . , sik }. 

The main theorem of the paper follows: 2 −1 is the sequence generated by the prefer-opposite construction Theorem 1 If S = si i=1 on n bits, then D(si )i∈I is the sequence generated by the prefer-one construction on n − 1 bits. n

Proof As a first case, let k be such that i k+1 = i k + 1, i.e., i k + 1 ∈ I . Since S is built using the prefer-opposite rule:  shl-opp(sik ) if shl-opp(sik ) ∈ / {s1 , . . . , sik }; sik+1 = sik +1 = shl-same(sik ) otherwise. Because i k + 1 ∈ I , Proposition 10 gives that shl-opp(sik ) ∈ / {s1 , . . . , sik } if and only if D(shl-opp(sik )) ∈ / {D(s1 ), . . . , D(sik )}. This allows to apply D on both sides of the above equality:  D(shl-opp(sik )) if D(shl-opp(sik )) ∈ / {D(s1 ), . . . , D(sik )}; D(sik+1 ) = D(shl-same(sik )) otherwise. By the definitions of I and D, I contains only the first of the two vertices that share the same image under D. This implies that {D(s1 ), . . . , D(sik )} = {D(si1 ), . . . , D(sik )}. Since D(shl-opp(s)) = shl-one(D(s)) and D(shl-same(s)) = shl-zero(D(s)), we get that:  shl-one(D(sik )) if shl-one(D(sik )) ∈ / {D(si1 ), . . . , D(sik )}; D(sik+1 ) = (1) shl-zero(D(sik )) otherwise. Note that this is how we defined the prefer-one construction. For the case where i k+1 > i k + 1 we have from Proposition 8 that D(sik+1 ) = shl-zero(D(sik ))

123

Mapping prefer-opposite to prefer-one de Bruijn sequences

and from Proposition 9 we have shl-one(D(sik )) ∈ {D(si1 ), . . . , D(sik )}. Therefore, equality (1) is true also for this case. n−1 Since D(si1 ) = D(s1 ) = D(0n ) = 0n−1 we get that the sequence {D(sik )}2k=1 , is the sequence of vertices generated by the prefer-one construction.



4 Discussion and future work We proved the claimed correspondence between prefer-opposite and prefer-one de Bruijn sequences. Our result relies on the following relations among the involved operators: D(s) = D(s) D(shl-opp(s)) = shl-one(D(s)) D(shl-same(s)) = shl-zero(D(s)) shl-same(s) = shl-same(s) shl-opp(s) = shl-opp(s) A possible future research direction is to focus on generalising the result by identifying other interesting operators for which similar relations hold. Another future research direction is to generalise the result to non-binary de Bruijn sequences. While preferring maximum is a natural generalisation of preferring one, there are several candidates for generalising opposite preference and, correspondingly, s, which are to be considered and examined. Acknowledgements This research was supported by the ISRAEL SCIENCE FOUNDATION (Grants No. 857/12 and 856/16).

References 1. Alhakim A.M.: A simple combinatorial algorithm for de Bruijn sequences. Am. Math. Mon. 117(8), 728–732 (2010). 2. de Bruijn N.G.: A combinatorial problem. Proc. Koninklijke Ned. Akad. Wet. Ser. A 49(7), 758 (1946). 3. Lempel A.: On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers. IEEE Trans. Comput. 100(12), 1204–1209 (1970). 4. Martin M.H.: A problem in arrangements. Bull. Am. Math. Soc. 40(12), 859–864 (1934).

123