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
Examples
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.
Links
- Peter Kagey, Antidiagonals n = 1..100, flattened
Crossrefs
Programs
-
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
Formula
T(n,k) = n^k - A342239(n,k).
Comments