login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A306522 Number of simple directed cycles in the binary de Bruijn graphs of order n. 0
3, 6, 19, 179, 30176, 1202267287 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

The numbers are computed empirically by the C++ program below. For n=7, the value is > 144*10^15 (the number of Hamiltonian cycles, A016031).

LINKS

Table of n, a(n) for n=1..6.

EXAMPLE

For n=1, the cycles are (0), (1) and (0, 1). For n=2, the cycles are (00), (00, 01, 10), (00, 01, 11, 10), (01, 10), (01, 11, 10), (11).

PROG

(C++)

#include <iostream>

#include <vector>

// DFS for binary de Bruijn graph. Count cycles starting at start, and

// don't visit cycles with nodes v < start, to avoid double counting

// any cycle.

uint64_t cycles_visit(uint64_t mask, uint64_t start, uint64_t v, std::vector<char>& visited) {

  visited[v] = true;

  const uint64_t neighbors[2] = { (v << 1) & mask, ((v << 1) & mask) | 1 };

  uint64_t count = 0;

  for(uint64_t n : neighbors) {

    if(n < start) continue;

    if(visited[n]) {

      if(n == start)

        ++count;

    } else {

        count += cycles_visit(mask, start, n, visited);

    }

  }

  visited[v] = false;

  return count;

}

int main(int argc, char *argv[]) {

  if(argc != 2) {

    std::cerr << "Usage: " << argv[0] << " k\n";

    return 1;

  }

  const unsigned k = std::atoi(argv[1]);

  const uint64_t mask = ((uint64_t)1 << k) - 1;

  if(k == 1) { // Optimization below does not work for k==1

    std::cout << 3 << '\n';

    return 0;

  }

  std::vector<char> visited(mask+1, false);

  // Cycles starting with 0...01

  uint64_t total = cycles_visit(mask, 1, 1, visited);

  // Cycles containing  0...0 also contain 0...01, except for the self loop 0...0

  total += total + 1;

  // Start from all other nodes

  for(uint64_t v = 2; v < mask; ++v) {

    total += cycles_visit(mask, v, v, visited);

  }

  total += 1; // self loop 1...1

  std::cout << total << '\n';

  return 0;

}

CROSSREFS

Sequence in context: A215817 A269306 A326317 * A290784 A176993 A276748

Adjacent sequences:  A306519 A306520 A306521 * A306523 A306524 A306525

KEYWORD

nonn,hard,more

AUTHOR

Guillaume Marçais, Feb 21 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 5 15:11 EST 2019. Contains 329753 sequences. (Running on oeis4.)