|
%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
| 