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.

  • $\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
    Commented Feb 10, 2017 at 17:13
  • $\begingroup$ @Casteels thanks for your help :) $\endgroup$
    – Winston
    Commented 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$ Commented May 25, 2022 at 14:32


You must log in to answer this question.

Browse other questions tagged .