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, 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

Table of n, a(n) for n=0..67.

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

Adjacent sequences: A351488 A351489 A351490 * A351492 A351493 A351494

Keyword

nonn,easy,tabf

Author

Hermann Gruber, Feb 13 2022

Status

approved