Strings: A First Look

Let \(n\) be a positive integer. Throughout this text, we will use the shorthand notation \([n]\) to denote the \(n\)-element set \(\{1,2,\dots,n\}\). Now let \(X\) be a set. Then a function \(s\colon[n]\rightarrow X\) is also called an \(X\)-string of length \(n\). In discussions of \(X\)-strings, it is customary to refer to the elements of \(X\) as characters, while the element \(s(i)\) is the \(i^{\text{th} }\) character of \(s\). Whenever practical, we prefer to denote a string \(s\) by writing \(s=\) \(x_1x_2x_3\dots x_n\) , rather than the more cumbersome notation \(s(1)=x_1\), \(s(2)=x_2\), , \(s(n)=x_n\).

There are a number of alternatives for the notation and terminology associated with strings. First, the characters in a string \(s\) are frequently written using subscripts as \(s_1,s_2,\dots,s_n\), so the \(i^{\text{th} }\)-term of \(s\) can be denoted \(s_i\) rather than \(s(i)\). Strings are also called sequences, especially when \(X\) is a set of numbers and the function \(s\) is defined by an algebraic rule. For example, the sequence of odd integers is defined by \(s_i=2i-1\).

Alternatively, strings are called words, the set \(X\) is called the alphabet and the elements of \(X\) are called letters. For example, \(aababbccabcbb\) is a \(13\)-letter word on the \(3\)-letter alphabet \(\{a,b,c\}\).

In many computing languages, strings are called arrays. Also, when the character \(s(i)\) is constrained to belong to a subset \(X_i\subseteq X\), a string can be considered as an element of the cartesian product \(X_1\times X_2\times \dots\times X_n\), which is normally viewed as \(n\)-tuples of the form \((x_1,x_2,\dots,x_n)\) such that \(x_i\in X_i\) for all \(i\in [n]\).

In the case that \(X=\{0,1\}\), an \(X\)-string is called a \(0\)\(1\) string (also a binary string or bit string.). When \(X=\{0,1,2\}\), an \(X\)-string is also called a ternary string.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.