login
A351491
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 ternary alphabet, n >= 0, 1 <= k <= 3^n.
0
0, 2, 4, 6, 4, 6, 8, 12, 14, 16, 20, 22, 24, 6, 8, 10, 14, 16, 18, 22, 24, 26, 32, 34, 36, 40, 42, 44, 48, 50, 52, 58, 60, 62, 66, 68, 70, 74, 76, 78, 8, 10, 12, 16, 18, 20, 24, 26, 28, 34, 36, 38, 42, 44, 46, 50, 52, 54, 60, 62, 64, 68, 70, 72, 76, 78, 80, 88
OFFSET
0,2
COMMENTS
Analogous to A351489 (which is the corresponding sequence for palindromes over binary alphabet).
REFERENCES
Hermann Gruber and Markus Holzer, Optimal Regular Expressions for Palindromes of Given Length. Extended journal version, in preparation, 2022.
LINKS
Hermann Gruber and Markus Holzer, Optimal Regular Expressions for Palindromes of Given Length, Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, Article No. 53, pp. 53:1-53:15, 2021.
FORMULA
Let SumOfDigitsInBase(m,b) denote the digit sum of nonnegative integer m in base b. Then the general formula for alphabet size q reads as
T(n,k) = 2*n + (2*q*(k-1))/(q-1) - (2*SumOfDigitsInBase(k-1,q))/(q-1). [Gruber and Holzer 2022 theorem 27]
EXAMPLE
Triangle T(n,k) begins:
k=1 2 3 4 5 6 ...
n=0: 0,
n=1: 2, 4, 6;
n=2: 4, 6, 8, 12, 14, 16, 20, 22, 24;
n=3: 6, 8, 10, 14, 16, 20, 22, 24, 26, 32, 34, 36, 40, 42, 44, 48, 50, 52, 58, 60, 62, 66, 68, 70, 74, 76, 78;
...
CROSSREFS
Cf. A053735 (ternary sum of digits), A351489 (for binary alphabet).
Sequence in context: A098793 A083220 A085896 * A107701 A293812 A011176
KEYWORD
nonn,easy,tabf
AUTHOR
Hermann Gruber, Feb 13 2022
STATUS
approved