login
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.
1

%I #30 Mar 26 2022 22:23:00

%S 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 39,40,43,44,9,10,13,14,19,20,23,24,31,32,35,36,41,42,45,46,55,56,59,

%U 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 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 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 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 T(n,k) = 2*n + 3*(k-1) - 2*hamming_weight(k-1)-1. See theorem 20 in Gruber/Holzer (2021).

%e Triangle T(n,k) begins:

%e 1, 2;

%e 3, 4, 7, 8;

%e 5, 6, 9, 10, 15, 16, 19, 20;

%e 7, 8, 11, 12, 17, 18, 21, 22, 29, 30, 33, 34, 39, 40, 43, 44;

%e ...

%t Flatten[Table[2n+3(k-1)-2Total[IntegerDigits[k-1,2]]-1,{n,6},{k,2^n}]] (* _Stefano Spezia_, Feb 13 2022 *)

%o (PARI) T(n,k) = 2*n + 3*(k-1) - 2*hammingweight(k-1) - 1 \\ _Andrew Howroyd_, Feb 12 2022

%Y Cf. A351489 gives the corresponding irregular triangle for even length 2*n.

%K nonn,tabf

%O 1,2

%A _Hermann Gruber_, Feb 12 2022