# Section2.1Strings: A First Look¶ permalink

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\}\text{.}$ 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\text{.}$ 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\text{,}$ $s(2)=x_2\text{,}$ …, $s(n)=x_n\text{.}$

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\text{,}$ so the $i^{\text{th} }$-term of $s$ can be denoted $s_i$ rather than $s(i)\text{.}$ 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\text{.}$

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\}\text{.}$

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\text{,}$ a string can be considered as an element of the cartesian product $X_1\times X_2\times \dots\times X_n\text{,}$ 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]\text{.}$

##### 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\text{.}$ How many license plates are possible?

Solution

In the case that $X=\{0,1\}\text{,}$ an $X$-string is called a $0$–$1$ string (also a binary string or bit string.). When $X=\{0,1,2\}\text{,}$ 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\text{.}$ Thus, there are $2$ options for each of $32$ positions to fill, making the number of such strings $2^{32} = 4\,294\,967\,296\text{.}$ In general, the number of bit strings of length $n$ is $2^n\text{.}$

##### 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