cp's OEIS Frontend

A351490 Irregular triangle read by rows: T(n,k) is the minimum number of alphabetic symbols in a regular expression for the k lexicographically first palindromes of odd length 2*n-1 over a binary alphabet, n >= 1, 1 <= k <= 2^n.

%I A351490 #30 Mar 26 2022 22:23:00
%S A351490 1,2,3,4,7,8,5,6,9,10,15,16,19,20,7,8,11,12,17,18,21,22,29,30,33,34,
%T A351490 39,40,43,44,9,10,13,14,19,20,23,24,31,32,35,36,41,42,45,46,55,56,59,
%U A351490 60,65,66,69,70,77,78,81,82,87,88,91,92,11,12,15,16,21,22,25,26,33,34,37,38,43,44,47,48,57,58,61,62
%N A351490 Irregular triangle read by rows: T(n,k) is the minimum number of alphabetic symbols in a regular expression for the k lexicographically first palindromes of odd length 2*n-1 over a binary alphabet, n >= 1, 1 <= k <= 2^n.
%C A351490 Following the notation in Gruber/Holzer (2021), for n >= 1 and 1 <= k <= 2^n, let P'_{n,k} denote the set containing the lexicographically first k palindromes of odd length 2n-1 over the binary alphabet {a,b}. T(n,k) is the minimum number of alphabetic symbols in any regular expression describing the set P'_{n,k}.
%H A351490 Hermann Gruber and Markus Holzer, <a href="https://doi.org/10.4230/LIPIcs.MFCS.2021.52">Optimal Regular Expressions for Palindromes of Given Length</a>, Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, Article No. 53, pp. 53:1-53:15, 2021.
%F A351490 T(n,k) = 2*n + 3*(k-1) - 2*hamming_weight(k-1)-1. See theorem 20 in Gruber/Holzer (2021).
%e A351490 Triangle T(n,k) begins:
%e A351490   1, 2;
%e A351490   3, 4,  7,  8;
%e A351490   5, 6,  9, 10, 15, 16, 19, 20;
%e A351490   7, 8, 11, 12, 17, 18, 21, 22, 29, 30, 33, 34, 39, 40, 43, 44;
%e A351490   ...
%t A351490 Flatten[Table[2n+3(k-1)-2Total[IntegerDigits[k-1,2]]-1,{n,6},{k,2^n}]] (* _Stefano Spezia_, Feb 13 2022 *)
%o A351490 (PARI) T(n,k) = 2*n + 3*(k-1) - 2*hammingweight(k-1) - 1 \\ _Andrew Howroyd_, Feb 12 2022
%Y A351490 Cf. A351489 gives the corresponding irregular triangle for even length 2*n.
%K A351490 nonn,tabf
%O A351490 1,2
%A A351490 _Hermann Gruber_, Feb 12 2022