login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A345530 Triangle T(n,k) read by rows of the number of n-bit words with maximum overlap k. 2
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 (list; table; graph; refs; listen; history; text; internal format)
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: A049627 A278223 A134058 * A216955 A086973 A240131

Adjacent sequences:  A345527 A345528 A345529 * A345531 A345532 A345533

KEYWORD

nonn,tabl

AUTHOR

Sean A. Irvine, Jun 20 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 05:51 EDT 2021. Contains 347509 sequences. (Running on oeis4.)