In the mathematical study of
combinatorics on words
Combinatorics on words is a fairly new field of mathematics, branching from combinatorics, which focuses on the study of words and formal languages. The subject looks at letters or symbols, and the sequences they form. Combinatorics on words ...
, a parameter word is a
string over a given
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
having some number of
wildcard character
In software, a wildcard character is a kind of placeholder represented by a single character, such as an asterisk (), which can be interpreted as a number of literal characters or an empty string. It is often used in file searches so the full na ...
s. 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
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...
and in computer science in the detection of
duplicate code In computer programming, duplicate code is a sequence of source code that occurs more than once, either within a program or across different programs owned or maintained by the same entity. Duplicate code is generally considered undesirable for a n ...
.
Definitions and notation
Formally, a word of length
, over a given alphabet
, is a sequence of
characters, some of which may be drawn from
and the others of which are
distinct wildcard characters
. 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
, the next one that is different from
must be
, 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 words over
, of length
, is
A word represents a set of
strings (0-parameter words), obtained by substituting a symbol of
for each wildcard character. This set of strings is called a parameter set of combinatorial cube, and
is called its dimension. A one-dimensional combinatorial cube may be called a combinatorial line.
In a combinatorial cube, each copy of a particular wildcard character must have the same replacement. A generalization of parameter words allows different copies of the same wildcard character to be replaced by different characters from the alphabet, in a controlled way. If
is an alphabet and
is a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
with an
action
Action may refer to:
* Action (narrative), a literary mode
* Action fiction, a type of genre fiction
* Action game, a genre of video game
Film
* Action film, a genre of film
* ''Action'' (1921 film), a film by John Ford
* ''Action'' (1980 fil ...
on
, then a parameter word is a word together with an assignment of a group element to each wildcard character in the word. The first occurrence of each wildcard character must be assigned the
identity element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
of the group. Then, the strings represented by a labeled parameter word are obtained by choosing a character of
for each wildcard character, and substituting the result of combining that character with the group element labeling each copy of that character. The set of all words over
, of length
, is
Example
In the game of
tic-tac-toe
Tic-tac-toe (American English), noughts and crosses (Commonwealth English), or Xs and Os (Canadian or Irish English) is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with ''X'' or ''O''. T ...
, the cells of the game board can be given two integer coordinates
from the alphabet
. Concatenating these two coordinates produces a string representing each cell, one of the nine strings
or
. There are seven one-parameter words of length two over this alphabet, the words
and
. The corresponding combinatorial lines form seven of the eight lines of three cells in a row of the tic-tac-toe board; for instance, the one-parameter word
corresponds to the combinatorial line
, and the one-parameter word
corresponds to the combinatorial
However, one of the eight winning lines of the tic-tac-toe game is missing from this set of combinatorial lines: the
antidiagonal
In linear algebra, the main diagonal (sometimes principal diagonal, primary diagonal, leading diagonal, major diagonal, or good diagonal) of a matrix A is the list of entries a_ where i = j. All off-diagonal elements are zero in a diagonal matrix. ...
It is possible to obtain this line as a combinatorial line (without including any other combinations of cells that would be invalid for tic-tac-toe) by using a group with two elements, and an action in which the non-identity element swaps the alphabet letters
and
while leaving the element
in place. There are eight labeled one-parameter words of length two for this action, seven of which are obtained from the unlabeled one-parameter words by using the identity label for all wildcards. These seven have the same combinatorial lines as before. The eighth labeled word consists of the word
labeled by the identity element for its first
and the reversing non-identity element for the second
; its combinatorial line is the final winning line of the tic-tac-toe board,
Composition
For three given integer parameters
, it is possible to combine two parameter words,
and
, to produce another parameter word
. To do so, simply replace each copy of the
th wildcard symbol in
by the
th character in
. This will necessarily produce a word of length
that uses each of the wildcard symbols in
at least once, in ascending order, so it produces a valid word of length
. This notion of composition can also be extended to composition of labeled parameter words (both using the same alphabet and group action), by applying the group action to the non-wildcard substituted characters and composing the group labels for the wildcard substituted characters. A subset of a combinatorial cube is a smaller combinatorial cube if it can be obtained by a composition in this way.
Combinatorial enumeration
The number of parameter words in
for an alphabet of size
is an
-
Stirling number of the second kind
In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of ''n'' objects into ''k'' non-empty subsets and is denoted by S(n,k) or \textstyle \lef ...
. These numbers count the number of partitions of the integers in the range