3
$\begingroup$

Determine whether there exists a string of the alphabet in which every sequence of length 3 occurs exactly once, except for sequences of the form vowel-consonant-vowel and consonant-vowel-consonant.

Would commenting that the formula found here - http://en.wikipedia.org/wiki/De_Bruijn_sequence - be enough to argue that a De Bruijn sequence exists? I am only asking because this seems like far too easy of a question if that is so.

If I am wrong, any nudges to the right direction would be greatly appreciated. Thanks!

$\endgroup$
2
  • $\begingroup$ I'm not sure what formula you mean? The $\frac{(k!)^{k^{n-1}}}{k^n}$ counts the number of de Bruijn sequences...but that would include vowel-consonant-vowel and consonant-vowel-consonant subsequences. $\endgroup$
    – Casteels
    Jun 2, 2015 at 5:33
  • $\begingroup$ Hmm, that's what I figured. So I guess the general question here would be, how exactly would I go about proving that the De Bruijn sequence does NOT exist, if that is the case? All I have so far is that the # of words without V-C-V and C-V-C is (26*3) - (5*21*5) - (21*5*21), but I'm not sure how to proceed from there, in terms of proving if the db sequence exists or not $\endgroup$
    – Horace
    Jun 2, 2015 at 15:05

1 Answer 1

Reset to default
0
$\begingroup$

Construct this graph as you would the DeBruijn graph. Let $v$ be a vertex of the form $VC$. Then $deg^+(v) = 5$ and $deg^-(v) = 21$. As the in degree does not equal the out degree, the graph is not Eulerian, so you cannot construct such a sequence.

In fact, the only balanced vertices in the graph are of the form $VV$ and $CC$.

$\endgroup$
1
  • $\begingroup$ oh god thanks, I can't believe I didn't even think of that. Much appreciated! $\endgroup$
    – Horace
    Jun 2, 2015 at 20:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .