A306522 -id:A306522 - cp's OEIS frontend

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

Pontus von Brömssen, Jan 21 2023

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.

			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.

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

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

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

a(10) from Bert Dobbelaere, Jan 24 2023

A344018 Table read by rows: T(n,k) (n >= 1, 1 <= k <= 2^n) is the number of cycles of length k which can be produced by a general n-stage feedback shift register.

Original entry on oeis.org

2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 3, 4, 2, 2, 1, 2, 3, 6, 7, 8, 12, 14, 17, 14, 13, 12, 20, 32, 16, 2, 1, 2, 3, 6, 9, 12, 20, 32, 57, 78, 113, 154, 208, 300, 406, 538, 703, 842, 1085, 1310, 1465, 1544, 1570, 1968, 2132, 2000, 2480, 2176, 2816, 4096, 2048

Offset: 1

N. J. A. Sloane, Jun 21 2021

T(n,k) is the number of cycles of length k in the directed binary de Bruijn graph of order n.

			The first four rows of the triangle are
2, 1,
2, 1, 2, 1,
2, 1, 2, 3, 2, 3, 4, 2,
2, 1, 2, 3, 6, 7, 8, 12, 14, 17, 14, 13, 12, 20, 32, 16,
...

Pontus von Brömssen, Rows n = 1..6, flattened
Peter R. Bryant and J. Christensen, The enumeration of shift register sequences, Journal of Combinatorial Theory, Series A, Vol. 35, No. 2 (1983), 154-172.
Oscar Cabrera, Introducing loop compression for encoding de Bruijn sequences, engrXiv (2025) Art. No. 4431. See p. 13.

Cf. A000010, A001037, A016031, A346018.

Row sums: A306522.

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 A344018_row(n):
  a=[0]*2**n
  for c in nx.simple_cycles(deBruijn(n)):
    a[len(c)-1]+=1
  return a # Pontus von Brömssen, Jun 28 2021

From Pontus von Brömssen, Jun 28 2021: (Start)
T(n,k) = A001037(k) for n >= k-1.
T(k-2,k) = A001037(k) - A000010(k).
T(k-3,k) = A001037(k) - 2*A346018(k,2) + 2 for k >= 5.
T(n,2^n-1) = 2*T(n,2^n) = 2*A016031(n).
(See page 157 in the paper by Bryant and Christensen.)
(End)
From Pontus von Brömssen, Jul 01 2021: (Start)
Conjectures by Bryant and Christensen (1983):
Conjecture 1: T(k-4,k) = A001037(k) - 4*A346018(k,3) - 2*gcd(k,2) + 10 for k >= 8.
Conjecture 2: T(k-5,k) = A001037(k) - 8*A346018(k,4) - gcd(k,3) + 19 for k >= 11.
Conjecture 3: T(k-6,k) = A001037(k) - 16*A346018(k,5) - 4*gcd(k,2) - 2*gcd(k,3) + 48 for k >= 15. (End)
Sum_{k=1..m} T(n, k) = A062692(m) for 1 <= m <= n + 1. - C.S. Elder, Nov 07 2023

More terms from Pontus von Brömssen, Jun 28 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions