login
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.
4
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
KEYWORD
nonn,tabf
AUTHOR
STATUS
approved