login
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.
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.
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 antidiagonals
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
KEYWORD
nonn,tabl
AUTHOR
Peter Kagey, Mar 07 2021
STATUS
approved