\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section2.1Strings: 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]\).

Example2.1

In the state of Georgia, license plates consist of four digits followed by a space followed by three capital letters. The first digit cannot be a \(0\). How many license plates are possible?

Solution

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.

Example2.2

A machine instruction in a \(32\)-bit operating system is just a bit string of length \(32\). Thus, there are \(2\) options for each of \(32\) positions to fill, making the number of such strings \(2^{32} = 4\,294\,967\,296\). In general, the number of bit strings of length \(n\) is \(2^n\).

Example2.3

Suppose that a website allows its users to pick their own usernames for accounts, but imposes some restrictions. The first character must be an upper-case letter in the English alphabet. The second through sixth characters can be letters (both upper-case and lower-case allowed) in the English alphabet or decimal digits (\(0\)–\(9\)). The seventh position must be `@' or `.'. The eighth through twelfth positions allow lower-case English letters, `*', `%', and `#'. The thirteenth position must be a digit. How many users can the website accept registrations from?

Solution