A342240 Table read by upward antidiagonals: T(n,k) is the number of strings of length k over an n-letter alphabet that have a bifix; n, k >= 1.

0, 0, 1, 0, 2, 1, 0, 3, 4, 1, 0, 4, 9, 10, 1, 0, 5, 16, 33, 20, 1, 0, 6, 25, 76, 99, 44, 1, 0, 7, 36, 145, 304, 315, 88, 1, 0, 8, 49, 246, 725, 1264, 945, 182, 1, 0, 9, 64, 385, 1476, 3725, 5056, 2883, 364, 1, 0, 10, 81, 568, 2695, 9036, 18625, 20404, 8649, 740, 1

Offset

1,5

Comments

A bifix is a nonempty substring that is both a prefix and a suffix.

Links

Peter Kagey, Antidiagonals n = 1..100, flattened

Formula

T(n,k) = n^k - A342239(n,k).

Example

Table begins:
n\k | 1 2  3   4    5     6      7       8        9
----+----------------------------------------------
  1 | 0 1  1   1    1     1      1       1        1
  2 | 0 2  4  10   20    44     88     182      364
  3 | 0 3  9  33   99   315    945    2883     8649
  4 | 0 4 16  76  304  1264   5056   20404    81616
  5 | 0 5 25 145  725  3725  18625   93605   468025
  6 | 0 6 36 246 1476  9036  54216  326346  1958076
  7 | 0 7 49 385 2695 19159 134113  940807  6585649
  8 | 0 8 64 568 4544 36800 294400 2358728 18869824
For n = 2, k = 4, the A(2,4) = 10 length-4 strings over a 2-letter alphabet with a bifix are:
0000 with prefix and suffix 0,
0010 with prefix and suffix 0,
0100 with prefix and suffix 0,
0101 with prefix and suffix 01,
0110 with prefix and suffix 0,
1001 with prefix and suffix 1,
1010 with prefix and suffix 10,
1011 with prefix and suffix 1,
1101 with prefix and suffix 1, and
1111 with prefix and suffix 1.

Prog

(Python)
from itertools import product
def has_bifix(s): return any(s[:i] == s[-i:] for i in range(1, len(s)//2+1))
def T(n, k): return sum(has_bifix(s) for s in product(range(n), repeat=k))
def atodiag(maxd): # maxd anti-diagonals
  return [T(n, d-n+1) for d in range(1, maxd+1) for n in range(d, 0, -1)]
print(atodiag(11)) # Michael S. Branicky, Mar 07 2021

Crossrefs

Cf. A342239.

Rows: A094536 (n=2), A094538 (n=3), A094559 (n=4).

Columns: A000290 (k=3), A081437 (k=4).

Sequence in context: A220399 A268830 A095884 * A128908 A285072 A300454

Adjacent sequences: A342237 A342238 A342239 * A342241 A342242 A342243

Keyword

nonn,tabl

Author

Peter Kagey, Mar 07 2021

Status

approved