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

 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.

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