A351489 - OEIS

%I #46 Mar 26 2022 22:22:24

%S 0,2,4,4,6,10,12,6,8,12,14,20,22,26,28,8,10,14,16,22,24,28,30,38,40,

%T 44,46,52,54,58,60,10,12,16,18,24,26,30,32,40,42,46,48,54,56,60,62,72,

%U 74,78,80,86,88,92,94,102,104,108,110,116,118,122,124,12,14,18,20,26,28,32,34,42,44,48,50,56,58,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 length 2*n over a binary alphabet, n >= 0, 1 <= k <= 2^n.

%C Following the notation in Gruber/Holzer (2021), for n >= 0 and 1 <= k <= 2^n, let P_{n,k} denote the set containing the lexicographically first k palindromes of even length 2n 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 + 4*(k-1) - 2*wt(k-1), where wt(n) = A000120(n) is the sum of the binary digits of n. [Gruber and Holzer theorem 14]

%e Triangle T(n,k) begins:

%e       k=1   2   3   4   5   6 ...

%e   n=0:  0,

%e   n=1:  2,  4;

%e   n=2:  4,  6, 10, 12;

%e   n=3:  6,  8, 12, 14, 20, 22, 26, 28;

%e   n=4:  8, 10, 14, 16, 22, 24, 28, 30, 38, 40, 44, 46, 52, 54, 58, 60;

%e   ...

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

%Y Cf. A000120 (sum of binary digits), A351490 (on odd lengths).

%K nonn,easy,tabf

%O 0,2

%A _Hermann Gruber_, Feb 12 2022