Strings as sequences

A string is a list, or sequence, of elements in a particular order.

The possible elements are called Symbols.

The combination of all different possible values of the symbols is called a Dictionary.

Alphabet is a String
Alphabet := [A,B,C, ... ,Z]

Notice that the same element can appear more than once in a string.

When no confusion results, we will usually leave out the parentheses and commas in the representation of a string.

Alphabet is a String
Alphabet := ABCDEFGHIJKLMNPQRSTUVWXYZ

The terms string, sequence, and word will be used interchangeably.

Numbers as Strings

Any positive integer can be represented by a string of digits from the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
This is the usual base 10 representation.

In the binary system, any positive integer is represented by a string of digits (called bits in this case) from the set {0, 1}.

Counting Strings

Consider all of the integers from 0 to 999.

Each one of these can be represented b ya 3-digit string using digits from 0 to 9

0 = 000
1 = 001
...

The first digit can be selected as one symbol out of ten 0..9. Same for the other symbols.

Therefore we can represent 10·10·10 = 1000 numbers.

How many numbers can we represent with 5 bits?

$2·2·2·2·2 = 2⁵ = 32$ different numbers: $0..31$

---

How many 3 letter words can there be with the standard 26 English characters?

$26·26·26 = 26³ = 17.576$ different 3 letter words.

Generally speaking, a word of $n$ symbols of length, and a dictionary of $m$ values for a character, is of the size $mⁿ$

Combinatorics of Strings

If we'd like to select a symbol only once per word, then the possible three-character words are 26·25·24 as the first character can select from the full arrange of symbols in the dictionary, but the second one can't select the already chosen, and so on.

Therefore the size of a combination of length $n$ from the set of $m$ possible symbols is

$m·(m-1)·(m-2).·.(m-n+1)$

$falling(m,n)$

$m˙ⁿ$

$\frac{m!}{(m-n)!}$

Permutation of strings

A permutation is an arrangement where all symbols are present only once in a particular order.

A string where each element appears only once.

A permutation of $m$ possible symbols is

$m!$

Product rule

In a string of length $m$, if the $i$-th term can be filled in a particular number of ways $nᵢ$ then the total number of possible strings is the product

$n₁·n₂·n₃·.·.·nₘ$
$∏nᵢ$

How many license plates can there be?

Assuming Spanish format: 7 characters divided as 4 numbers followed by 3 letters. $10·10·10·10·26·26·26$ $=175.760.000$