login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 1
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 (list; graph; refs; listen; history; text; internal format)
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)

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 27 03:13 EDT 2022. Contains 354093 sequences. (Running on oeis4.)