A345530 Triangle T(n,k) read by rows of the number of n-bit words with maximum overlap k.

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, 82, 48, 30, 12, 6, 2, 2, 148, 154, 106, 52, 30, 12, 6, 2, 2, 284, 318, 198, 118, 54, 30, 12, 6, 2, 2, 568, 614, 414, 222, 124, 54, 30, 12, 6, 2, 2

Offset: 1

Author

Sean A. Irvine, Jun 20 2021

Keywords

• nonn
• tabl

Comments

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.

The trivial overlap n=k is ignored.

All terms are even, because a word and its bitwise complement have the same maximum overlap.

Examples

			For n=3, the maximum overlaps are as follows:
  000 2,
  001 0,
  010 1,
  011 0,
  100 0,
  101 1,
  110 0,
  111 2;
thus row 3 of the triangle is 4, 2, 2 (4 with overlap 0, 2 with overlap 1, 2 with overlap 2).
The triangle begins:
   2;
   2,  2;
   4,  2, 2;
   6,  6, 2, 2;
  12, 10, 6, 2, 2;
  20, 22, 12, 6, 2, 2;
  ...
		

Links

• Sean A. Irvine, Rows n=1..38 flattened
• H. Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, J. für Reine Angewandte Math. 271 (1974), 139-154.
• Sean A. Irvine, Java program (github)

Crossrefs

Cf. A003000, A019310, A019311, A345710.

Programs

Python

def maxoverlap(n):
    b = bin(n)[2:]
    for k in range(len(b)-1, -1, -1):
        if b.startswith(b[-k:]): return k
def T(n, k): return 2*sum(maxoverlap(i) == k for i in range(2**(n-1), 2**n))
print([T(n, k) for n in range(1, 12) for k in range(n)]) # Michael S. Branicky, Jun 24 2021

Python

# faster version, using maxoverlap above
from collections import Counter
def row(n):
    c = Counter(maxoverlap(i) for i in range(2**(n-1), 2**n))
    return [2*c[k] for k in range(n)]
def table(r): return [i for n in range(1, r+1) for i in row(n)]
print(table(11)) # Michael S. Branicky, Jun 24 2021

Formula

Sum_{k=0..n-1} T(n,k) = 2^k.

T(n,0) = A003000(n).

T(n,1) = A019310(n).

T(n,2) = A019311(n).