cp's OEIS Frontend

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.

%I A342240 #30 Jul 09 2024 19:41:10
%S A342240 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,
%T A342240 36,145,304,315,88,1,0,8,49,246,725,1264,945,182,1,0,9,64,385,1476,
%U A342240 3725,5056,2883,364,1,0,10,81,568,2695,9036,18625,20404,8649,740,1
%N 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.
%C A342240 A bifix is a nonempty substring that is both a prefix and a suffix.
%H A342240 Peter Kagey, <a href="/A342240/b342240.txt">Antidiagonals n = 1..100, flattened</a>
%F A342240 T(n,k) = n^k - A342239(n,k).
%e A342240 Table begins:
%e A342240 n\k | 1 2  3   4    5     6      7       8        9
%e A342240 ----+----------------------------------------------
%e A342240   1 | 0 1  1   1    1     1      1       1        1
%e A342240   2 | 0 2  4  10   20    44     88     182      364
%e A342240   3 | 0 3  9  33   99   315    945    2883     8649
%e A342240   4 | 0 4 16  76  304  1264   5056   20404    81616
%e A342240   5 | 0 5 25 145  725  3725  18625   93605   468025
%e A342240   6 | 0 6 36 246 1476  9036  54216  326346  1958076
%e A342240   7 | 0 7 49 385 2695 19159 134113  940807  6585649
%e A342240   8 | 0 8 64 568 4544 36800 294400 2358728 18869824
%e A342240 For n = 2, k = 4, the A(2,4) = 10 length-4 strings over a 2-letter alphabet with a bifix are:
%e A342240 0000 with prefix and suffix 0,
%e A342240 0010 with prefix and suffix 0,
%e A342240 0100 with prefix and suffix 0,
%e A342240 0101 with prefix and suffix 01,
%e A342240 0110 with prefix and suffix 0,
%e A342240 1001 with prefix and suffix 1,
%e A342240 1010 with prefix and suffix 10,
%e A342240 1011 with prefix and suffix 1,
%e A342240 1101 with prefix and suffix 1, and
%e A342240 1111 with prefix and suffix 1.
%o A342240 (Python)
%o A342240 from itertools import product
%o A342240 def has_bifix(s): return any(s[:i] == s[-i:] for i in range(1, len(s)//2+1))
%o A342240 def T(n, k): return sum(has_bifix(s) for s in product(range(n), repeat=k))
%o A342240 def atodiag(maxd): # maxd antidiagonals
%o A342240   return [T(n, d-n+1) for d in range(1, maxd+1) for n in range(d, 0, -1)]
%o A342240 print(atodiag(11)) # _Michael S. Branicky_, Mar 07 2021
%Y A342240 Cf. A342239.
%Y A342240 Rows: A094536 (n=2), A094538 (n=3), A094559 (n=4).
%Y A342240 Columns: A000290 (k=3), A081437 (k=4).
%K A342240 nonn,tabl
%O A342240 1,5
%A A342240 _Peter Kagey_, Mar 07 2021