A351489 -id:A351489 - 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.

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

Offset: 1

Hermann Gruber, Feb 12 2022

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}.

			Triangle T(n,k) begins:
  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, 39, 40, 43, 44;
  ...

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.

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

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

T(n,k) = 2*n + 3*(k-1) - 2*hammingweight(k-1) - 1 \\ Andrew Howroyd, Feb 12 2022

T(n,k) = 2*n + 3*(k-1) - 2*hamming_weight(k-1)-1. See theorem 20 in Gruber/Holzer (2021).

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.

Original entry on oeis.org

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

Hermann Gruber, Feb 13 2022

Analogous to A351489 (which is the corresponding sequence for palindromes over binary alphabet).

			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;
  ...

Hermann Gruber and Markus Holzer, Optimal Regular Expressions for Palindromes of Given Length. Extended journal version, in preparation, 2022.

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.

Cf. A053735 (ternary sum of digits), A351489 (for binary alphabet).

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]

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula