A333077 Number of maximal independent sets in the binary de Bruijn graph of order n.

1, 2, 3, 8, 64, 2626, 4850838

Offset

0,2

Links

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

Eric Weisstein's World of Mathematics, de Bruijn Graph

Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Wikipedia, De Bruijn graph

Wikipedia, Maximal independent set

Prog

(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 A333077(n):
    return sum(1 for _ in nx.find_cliques(nx.complement(nx.Graph(deBruijn(n)))))
# replacement of a function removed from NetworkX by Ross Barnowski, Nov 12 2023

Crossrefs

Cf. A006946, A333078.

Sequence in context: A095203 A351658 A003096 * A354574 A042815 A191353

Adjacent sequences: A333074 A333075 A333076 * A333078 A333079 A333080

Keyword

nonn,hard,more

Author

Pontus von Brömssen, Mar 07 2020

Status

approved