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

3, 6, 19, 179, 30176, 1202267287

Offset: 1

Author

Guillaume Marçais, Feb 21 2019

Keywords

• nonn
• hard
• more

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

Examples

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

Crossrefs

Cf. A016031.

Programs

Python

import networkx as nx
def deBruijn(n): return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1))
def A306522(n): return sum(1 for c in nx.simple_cycles(deBruijn(n))) # Pontus von Brömssen, Jun 28 2021