A359997 Irregular triangle read by rows: T(n,k) is the number of directed cycles of length k in the 2-Fibonacci digraph of order n.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 4, 3, 5, 4, 7, 6, 6, 6, 4, 4, 2, 2, 1, 1, 1, 1, 2, 2, 4, 5, 5, 6, 8, 10, 15, 20, 20, 24, 23, 19, 18, 20, 30, 30, 36, 36, 16, 0, 28, 28, 28

Offset

1,14

Comments

See Dalfó and Fiol (2019) or A360000 for the definition of the 2-Fibonacci digraph.

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

Apparently, the number of terms in the n-th row (i.e., the length of the longest cycle in the 2-Fibonacci digraph of order n) is A080023(n).

Interestingly, the 2-Fibonacci digraph of order 7 has cycles of all lengths from 1 up to the maximum 29, except 26. For all other orders n <= 10, there are no such gaps, i.e., the graph is weakly pancyclic.

Links

Pontus von Brömssen, Table of n, a(n) for n = 1..320 (rows n = 1..10; row 10 computed by Bert Dobbelaere)

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

Formula

T(n,k) = A006206(k) for n >= k-1.

Example

Triangle begins:
  n\k| 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
  ---+-----------------------------------------------------
  1  | 1  1
  2  | 1  1  1
  3  | 1  1  1  1
  4  | 1  1  1  1  2  1  1
  5  | 1  1  1  1  2  2  1  1  2  2  2
  6  | 1  1  1  1  2  2  4  3  5  4  7  6  6  6  4  4  2  2

Prog

(Python)
import networkx as nx
from collections import Counter
def F(n): return nx.DiGraph(((0, 0), (0, 1), (1, 0))) if n == 1 else nx.line_graph(F(n-1))
def A359997_row(n):
    a = Counter(len(c) for c in nx.simple_cycles(F(n)))
    return [a[k] for k in range(1, max(a)+1)]

Crossrefs

Cf. A006206 (main diagonal), A080023, A344018, A359998 (last element in each row), A359999, A360000 (row sums).

Sequence in context: A139039 A279061 A206491 * A122172 A030613 A025910

Adjacent sequences: A359994 A359995 A359996 * A359998 A359999 A360000

Keyword

nonn,tabf

Author

Pontus von Brömssen, Jan 21 2023

Status

approved