|
%I #42 Nov 08 2023 12:35:17
%S 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,
%T 2,1,2,3,6,9,12,20,32,57,78,113,154,208,300,406,538,703,842,1085,1310,
%U 1465,1544,1570,1968,2132,2000,2480,2176,2816,4096,2048
%N 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.
%C T(n,k) is the number of cycles of length k in the directed binary de Bruijn graph of order n.
%H Pontus von Brömssen, <a href="/A344018/b344018.txt">Rows n = 1..6, flattened</a>
%H Bryant, Peter R., and J. Christensen, <a href="https://doi.org/10.1016/0097-3165(83)90004-3">The enumeration of shift register sequences</a>, Journal of Combinatorial Theory, Series A, Vol. 35, No. 2 (1983), 154-172.
%F From _Pontus von Brömssen_, Jun 28 2021: (Start)
%F T(n,k) = A001037(k) for n >= k-1.
%F T(k-2,k) = A001037(k) - A000010(k).
%F T(k-3,k) = A001037(k) - 2*A346018(k,2) + 2 for k >= 5.
%F T(n,2^n-1) = 2*T(n,2^n) = 2*A016031(n).
%F (See page 157 in the paper by Bryant and Christensen.)
%F (End)
%F From _Pontus von Brömssen_, Jul 01 2021: (Start)
%F Conjectures by Bryant and Christensen (1983):
%F Conjecture 1: T(k-4,k) = A001037(k) - 4*A346018(k,3) - 2*gcd(k,2) + 10 for k >= 8.
%F Conjecture 2: T(k-5,k) = A001037(k) - 8*A346018(k,4) - gcd(k,3) + 19 for k >= 11.
%F 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)
%F Sum_{k=1..m} T(n, k) = A062692(m) for 1 <= m <= n + 1. - _C.S. Elder_, Nov 07 2023
%e The first four rows of the triangle are
%e 2, 1,
%e 2, 1, 2, 1,
%e 2, 1, 2, 3, 2, 3, 4, 2,
%e 2, 1, 2, 3, 6, 7, 8, 12, 14, 17, 14, 13, 12, 20, 32, 16,
%e ...
%o (Python)
%o import networkx as nx
%o def deBruijn(n): return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1))
%o def A344018_row(n):
%o a=[0]*2**n
%o for c in nx.simple_cycles(deBruijn(n)):
%o a[len(c)-1]+=1
%o return a # _Pontus von Brömssen_, Jun 28 2021
%Y Cf. A000010, A001037, A016031, A346018.
%Y Row sums: A306522.
%K nonn,tabf
%O 1,1
%A _N. J. A. Sloane_, Jun 21 2021
%E More terms from _Pontus von Brömssen_, Jun 28 2021
|
