Palabra de parámetro

En el estudio matemático de la combinatoria de palabras , una palabra de parámetro es una cadena sobre un alfabeto dado que tiene cierto número de caracteres comodín . ^[1] El conjunto de cadenas que coinciden con una palabra de parámetro determinada se denomina conjunto de parámetros o cubo combinatorio . Se pueden componer palabras de parámetros para producir subcubos más pequeños de un cubo combinatorio dado. Tienen aplicaciones en la teoría de Ramsey y en informática en la detección de código duplicado .

Formalmente, una palabra de parámetro de longitud , sobre un alfabeto dado , es una secuencia de caracteres, algunos de los cuales pueden extraerse y otros son caracteres comodín distintos . Se requiere que cada carácter comodín aparezca al menos una vez, pero puede aparecer varias veces, y los caracteres comodín deben aparecer en el orden dado por sus índices: el primer carácter comodín en la palabra debe ser , el siguiente que sea diferente de debe ser ${\ Displaystyle k}$ ${\ Displaystyle n}$ ${\ Displaystyle A}$ ${\ Displaystyle n}$ ${\ Displaystyle A}$ ${\ Displaystyle k}$ ${\ Displaystyle * _ {1}, * _ {2}, \ ldots, * _ {k}}$ ${\ Displaystyle * _ {1}}$ ${\ Displaystyle * _ {1}}$ ${\ Displaystyle * _ {2}}$ , etc. Como caso especial, una palabra sobre el alfabeto dado, sin ningún carácter comodín, se dice que es una palabra de parámetro 0. Para palabras de 1 parámetro, los subíndices pueden omitirse, ya que no hay ambigüedad entre los diferentes caracteres comodín. El conjunto de todos los -parámetro palabras más , de longitud , está denotado . ^[1] ${\ Displaystyle k}$ ${\ Displaystyle A}$ ${\ Displaystyle n}$ ${\ Displaystyle A {\ tbinom {n} {k}}}$

A -parámetro palabra representa un conjunto de cadenas (palabras 0 de parámetros), obtenido mediante la sustitución de un símbolo de para cada carácter comodín. Este conjunto de cadenas se denomina conjunto de parámetros de cubo combinatorio y se denomina dimensión. Un cubo combinatorio unidimensional se puede llamar línea combinatoria . ^[1] ${\ Displaystyle k}$ ${\ Displaystyle | A | ^ {k}}$ ${\ Displaystyle A}$ ${\ Displaystyle k}$