number of distinct de Bruijn sequences B(n,k)

Ask Question

Asked 6 years, 3 months ago

Modified 6 years ago

Viewed 375 times

I am trying to find out where does the formula for finding the number of all distinct de Bruijn sequences come from. Wikipedia page :https://en.wikipedia.org/wiki/De_Bruijn_sequence here is the formula part:B(n,k)

p.s: This is not homework! I'm just self-studying Graph Theory.

asked Feb 10, 2017 at 14:33

Winston

1371 silver badge9 bronze badges

$\begingroup$ See Van Lint and Wilson, "A Course in Combinatorics" for the $k=2$ case (the general case is similar I'm sure). Basically, you proceed by induction using the de Bruijn graphs. $\endgroup$
– Casteels
Feb 10, 2017 at 17:13
$\begingroup$ @Casteels thanks for your help :) $\endgroup$
– Winston
Feb 16, 2017 at 8:06
$\begingroup$ See "Circuits and trees in oriented linear graphs" by de Bruijn and van Aardenne-Ehrenfest for a proof of the general case. $\endgroup$
– Mike Earnest
May 25, 2022 at 14:32

Add a comment |

0