A360000 Number of directed cycles in the 2-Fibonacci digraph of order n.

2, 3, 4, 8, 16, 61, 437, 17766, 5885824, 111327315589

Offset

1,1

Comments

The 2-Fibonacci digraph of order n, F(n), is defined by Dalfó and Fiol (2019). It can be defined as an iterated line digraph, where F(1) has two nodes, one directed edge in each direction between them, and a loop at one of the nodes, and for n >= 2 F(n) is the line digraph of F(n-1). (Compare the related de Bruijn graph, where the graph of order one has loops at both nodes.) Its nodes can be identified with binary sequences of length n with no adjacent 1's (or fibbinary numbers below 2^n if the nodes are labeled by integers instead of binary sequences), with a directed edge from (x_0, ..., x_{n-1}) to (x_1, ..., x_n) if there are no consecutive 1's in (x_0, ..., x_n). For n >= 2, it is also the subgraph of the de Bruijn graph (of the same order) induced by the nodes with no adjacent 1's. It has A000045(n+2) nodes and A000045(n+3) edges.

Equivalently, a(n) is the number of cycles with no adjacent 1's that can be produced by a general n-stage feedback shift register.

Links

Table of n, a(n) for n=1..10.

C. Dalfó and M. A. Fiol, On d-Fibonacci digraphs, arXiv:1909.06766 [math.CO], 2019.

Example

For n = 4 there are a(4) = 8 cycles:
  0000 -> 0000;
  0101 -> 1010 -> 0101;
  0010 -> 0100 -> 1001 -> 0010;
  0001 -> 0010 -> 0100 -> 1000 -> 0001;
  0000 -> 0001 -> 0010 -> 0100 -> 1000 -> 0000;
  0010 -> 0101 -> 1010 -> 0100 -> 1001 -> 0010;
  0001 -> 0010 -> 0101 -> 1010 -> 0100 -> 1000 -> 0001;
  0000 -> 0001 -> 0010 -> 0101 -> 1010 -> 0100 -> 1000 -> 0000.

Prog

(Python)
import networkx as nx
def F(n): return nx.DiGraph(((0, 0), (0, 1), (1, 0))) if n == 1 else nx.line_graph(F(n-1))
def A360000(n): return sum(1 for c in nx.simple_cycles(F(n)))

Crossrefs

Cf. A000045, A306522, A359997, A359998, A359999.

Sequence in context: A244750 A140974 A349763 * A372100 A296109 A102276

Adjacent sequences: A359997 A359998 A359999 * A360001 A360002 A360003

Keyword

nonn,more

Author

Pontus von Brömssen, Jan 21 2023

Extensions

a(10) from Bert Dobbelaere, Jan 24 2023

Status

approved