|
%I #17 Jun 24 2021 21:33:54
%S 2,2,2,4,2,2,6,6,2,2,12,10,6,2,2,20,22,12,6,2,2,40,38,28,12,6,2,2,74,
%T 82,48,30,12,6,2,2,148,154,106,52,30,12,6,2,2,284,318,198,118,54,30,
%U 12,6,2,2,568,614,414,222,124,54,30,12,6,2,2
%N Triangle T(n,k) read by rows of the number of n-bit words with maximum overlap k.
%C Here an overlap means some initial part of the binary word matches exactly the end part of the word. More precisely if B = b_1,b_2,...,b_n is the word, and k is the largest value for which b_i=b_n-k+i for 1 <= i <= k, k < n, then B is said to have a maximum overlap of k. The smallest possible overlap is 0 and largest possible overlap is n-1.
%C The trivial overlap n=k is ignored.
%C All terms are even, because a word and its bitwise complement have the same maximum overlap.
%H Sean A. Irvine, <a href="/A345530/b345530.txt">Rows n=1..38 flattened</a>
%H H. Harborth, <a href="http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002189852">Endliche 0-1-Folgen mit gleichen Teilblöcken</a>, J. für Reine Angewandte Math. 271 (1974), 139-154.
%H Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a345/A345530.java">Java program</a> (github)
%F Sum_{k=0..n-1} T(n,k) = 2^k.
%F T(n,0) = A003000(n).
%F T(n,1) = A019310(n).
%F T(n,2) = A019311(n).
%e For n=3, the maximum overlaps are as follows:
%e 000 2,
%e 001 0,
%e 010 1,
%e 011 0,
%e 100 0,
%e 101 1,
%e 110 0,
%e 111 2;
%e thus row 3 of the triangle is 4, 2, 2 (4 with overlap 0, 2 with overlap 1, 2 with overlap 2).
%e The triangle begins:
%e 2;
%e 2, 2;
%e 4, 2, 2;
%e 6, 6, 2, 2;
%e 12, 10, 6, 2, 2;
%e 20, 22, 12, 6, 2, 2;
%e ...
%o (Python)
%o def maxoverlap(n):
%o b = bin(n)[2:]
%o for k in range(len(b)-1, -1, -1):
%o if b.startswith(b[-k:]): return k
%o def T(n, k): return 2*sum(maxoverlap(i) == k for i in range(2**(n-1), 2**n))
%o print([T(n, k) for n in range(1, 12) for k in range(n)]) # _Michael S. Branicky_, Jun 24 2021
%o (Python) # faster version, using maxoverlap above
%o from collections import Counter
%o def row(n):
%o c = Counter(maxoverlap(i) for i in range(2**(n-1), 2**n))
%o return [2*c[k] for k in range(n)]
%o def table(r): return [i for n in range(1, r+1) for i in row(n)]
%o print(table(11)) # _Michael S. Branicky_, Jun 24 2021
%Y Cf. A003000, A019310, A019311, A345710.
%K nonn,tabl
%O 1,1
%A _Sean A. Irvine_, Jun 20 2021
|
