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

Cf. A000010, A001037, A016031, A346018.

Row sums: A306522.

Sequence in context: A330721 A076622 A194513 * A245040 A161314 A161248

Adjacent sequences: A344015 A344016 A344017 * A344019 A344020 A344021

Keyword

nonn,tabf

Author

N. J. A. Sloane, Jun 21 2021

Extensions

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

Status

approved