cp's OEIS Frontend

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

%I A306522 #21 Jun 28 2021 10:48:19
%S A306522 3,6,19,179,30176,1202267287
%N A306522 Number of simple directed cycles in the binary de Bruijn graphs of order n.
%C A306522 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 A306522 For n=1, the cycles are (0), (1) and (0, 1).
%e A306522 For n=2, they are (00), (00, 01, 10), (00, 01, 11, 10), (01, 10), (01, 11, 10), (11).
%o A306522 (C++)
%o A306522 #include <iostream>
%o A306522 #include <vector>
%o A306522 // DFS for binary de Bruijn graph. Count cycles starting at start, and
%o A306522 // don't visit cycles with nodes v < start, to avoid double counting
%o A306522 // any cycle.
%o A306522 uint64_t cycles_visit(uint64_t mask, uint64_t start, uint64_t v, std::vector<char>& visited) {
%o A306522   visited[v] = true;
%o A306522   const uint64_t neighbors[2] = { (v << 1) & mask, ((v << 1) & mask) | 1 };
%o A306522   uint64_t count = 0;
%o A306522   for(uint64_t n : neighbors) {
%o A306522     if(n < start) continue;
%o A306522     if(visited[n]) {
%o A306522       if(n == start)
%o A306522         ++count;
%o A306522     } else {
%o A306522         count += cycles_visit(mask, start, n, visited);
%o A306522     }
%o A306522   }
%o A306522   visited[v] = false;
%o A306522   return count;
%o A306522 }
%o A306522 int main(int argc, char *argv[]) {
%o A306522   if(argc != 2) {
%o A306522     std::cerr << "Usage: " << argv[0] << " k\n";
%o A306522     return 1;
%o A306522   }
%o A306522   const unsigned k = std::atoi(argv[1]);
%o A306522   const uint64_t mask = ((uint64_t)1 << k) - 1;
%o A306522   if(k == 1) { // Optimization below does not work for k==1
%o A306522     std::cout << 3 << '\n';
%o A306522     return 0;
%o A306522   }
%o A306522   std::vector<char> visited(mask+1, false);
%o A306522   // Cycles starting with 0...01
%o A306522   uint64_t total = cycles_visit(mask, 1, 1, visited);
%o A306522   // Cycles containing  0...0 also contain 0...01, except for the self loop 0...0
%o A306522   total += total + 1;
%o A306522   // Start from all other nodes
%o A306522   for(uint64_t v = 2; v < mask; ++v) {
%o A306522     total += cycles_visit(mask, v, v, visited);
%o A306522   }
%o A306522   total += 1; // self loop 1...1
%o A306522   std::cout << total << '\n';
%o A306522   return 0;
%o A306522 }
%o A306522 (Python)
%o A306522 import networkx as nx
%o A306522 def deBruijn(n): return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1))
%o A306522 def A306522(n): return sum(1 for c in nx.simple_cycles(deBruijn(n))) # _Pontus von Brömssen_, Jun 28 2021
%Y A306522 Cf. A016031.
%K A306522 nonn,hard,more
%O A306522 1,1
%A A306522 _Guillaume Marçais_, Feb 21 2019