A306522 - OEIS

%I #21 Jun 28 2021 10:48:19

%S 3,6,19,179,30176,1202267287

%N Number of simple directed cycles in the binary de Bruijn graphs of order n.

%C 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).

%e For n=1, the cycles are (0), (1) and (0, 1).

%e For n=2, they are (00), (00, 01, 10), (00, 01, 11, 10), (01, 10), (01, 11, 10), (11).

%o (C++)

%o #include <iostream>

%o #include <vector>

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

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

%o // any cycle.

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

%o   visited[v] = true;

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

%o   uint64_t count = 0;

%o   for(uint64_t n : neighbors) {

%o     if(n < start) continue;

%o     if(visited[n]) {

%o       if(n == start)

%o         ++count;

%o     } else {

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

%o     }

%o   }

%o   visited[v] = false;

%o   return count;

%o }

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

%o   if(argc != 2) {

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

%o     return 1;

%o   }

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

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

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

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

%o     return 0;

%o   }

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

%o   // Cycles starting with 0...01

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

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

%o   total += total + 1;

%o   // Start from all other nodes

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

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

%o   }

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

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

%o   return 0;

%o }

%o (Python)

%o import networkx as nx

%o def deBruijn(n): return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1))

%o def A306522(n): return sum(1 for c in nx.simple_cycles(deBruijn(n))) # _Pontus von Brömssen_, Jun 28 2021

%Y Cf. A016031.

%K nonn,hard,more

%O 1,1

%A _Guillaume Marçais_, Feb 21 2019