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,1

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.

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)

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).

Example

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;
  ...

Prog

(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

Crossrefs

Cf. A003000, A019310, A019311, A345710.

Sequence in context: A278223 A368556 A134058 * A216955 A086973 A240131

Adjacent sequences: A345527 A345528 A345529 * A345531 A345532 A345533

Keyword

nonn,tabl

Author

Sean A. Irvine, Jun 20 2021

Status

approved