Parameter word

In the mathematical study of combinatorics on words, a parameter word is a string over a given alphabet having some number of wildcard characters. The set of strings matching a given parameter word is called a parameter set or combinatorial cube. Parameter words can be composed, to produce smaller subcubes of a given combinatorial cube. They have applications in Ramsey theory and in computer science in the detection of duplicate code.

Definitions and notation

Formally, a

k

{\displaystyle k}

-parameter word of length

n

{\displaystyle n}

, over a given alphabet

A

{\displaystyle A}

, is a sequence of

n

{\displaystyle n}

characters, some of which may be drawn from

A

{\displaystyle A}

and the others of which are

k

{\displaystyle k}

distinct wildcard characters

∗

1

,

∗

2

,

…

,

∗

k

{\displaystyle *_{1},*_{2},\ldots ,*_{k}}

. Each wildcard character is required to appear at least once, but may appear multiple times, and the wildcard characters must appear in the order given by their indexes: the first wildcard character in the word must be

∗

1

{\displaystyle *_{1}}

, the next one that is different from

∗

1

{\displaystyle *_{1}}

must be

∗

2

{\displaystyle *_{2}}

, etc. As a special case, a word over the given

alphabet, without any wildcard characters, is said to be a 0-parameter word. For 1-parameter words, the subscripts may be omitted, as there is no ambiguity between different wildcard characters. The set of all

k

{\displaystyle k}

-parameter words over

A

{\displaystyle A}

, of length

n

{\displaystyle n}

, is denoted

A

(

n

k

)

{\displaystyle A{\tbinom {n}{k}}}

.

A

k

{\displaystyle k}

-parameter word represents a set of

|

A

|

k

{\displaystyle |A|^{k}}

strings (0-parameter words), obtained by substituting a symbol of

A

{\displaystyle A}

for each wildcard character.