login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
2
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,1
COMMENTS
T(n,k) is the number of cycles of length k in the directed binary de Bruijn graph of order n.
LINKS
Pontus von Brömssen, Rows n = 1..6, flattened
Bryant, Peter R., and J. Christensen, The enumeration of shift register sequences, Journal of Combinatorial Theory, Series A, Vol. 35, No. 2 (1983), 154-172.
FORMULA
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
EXAMPLE
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,
...
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 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
CROSSREFS
Row sums: A306522.
Sequence in context: A330721 A076622 A194513 * A245040 A161314 A161248
KEYWORD
nonn,tabf
AUTHOR
N. J. A. Sloane, Jun 21 2021
EXTENSIONS
More terms from Pontus von Brömssen, Jun 28 2021
STATUS
approved