## Footnotes: Mathematics

### Natural numbers and integers

A natural number is any element of the set  0 1 2 3 4 …   An integer is any element of the set  … −4 −3 −2 −1 0 1 2 3 4 …

### Positive and negative

The word positive is often somewhat ambiguous: does it mean  > 0  or  ≥ 0?  Something similar goes for the word negative.

In this site, a number x is considered positive if  x ≥ 0  and strictly positive if  x > 0.  (We may occasionally use the redundant expression positive or null for emphasis.)

Similarly, a number x is negative if  x ≤ 0  and strictly negative if  x < 0.

### Sequences and sets

A sequence is characterized by the order of its elements: there is a first element, a second element, etc., a last element.  (Example: the sequence of digits of a phone number.)  To specify the elements of a sequence, write them, in order, wrapped in parentheses:  (a, b, c, …).  If this does not cause confusion, you may omit the parentheses and commas and write simply  a b c

A set has no order. There is no first element and no last element.  (Example: the set of numbers in a lottery result.)  As a consequence, a set has no repeated elements.  To specify the elements of a set, write them, in any order, wrapped in curly braces:  {a, b, c, …}.

We shall use the notation  a . . b  to designate the set of integers {a, a+1, a+2, … , b}.  Depending on the context, this notation can also designate the sequence (a, a+1, a+2, … , b).

Sequences are represented by arrays or by linked lists.  Sets may are represented by strictly increasing arrays or strictly increasing linked lists.

### Increasing order

A sequence (v0, v1, … , vn−1) is increasing  (or is in increasing order)  if  v0 v1 … ≤ vn−1.  The sequence is strictly increasing if we have  <  in place of  .  The concepts of decreasing and strictly decreasing are defined similarly.

Analogous definitions apply to arrays and to linked lists.

Caution:  Some books say  nondecreasing  where we say  increasing.  They also say  increasing  where we say  strictly increasing.

### Permutations

A permutation of a finite sequence is any sequence that has the same elements in a possibly different order.  For example,  2 1 4 2 3  is a permutation of  1 2 2 3 4 .  A sequence with n elements has exactly  n!  different permutations.

### Lexicographic order

The lexicographic order between sequences of integers is defined roughly as follows: a sequence  s  is lexicographically smaller than a sequence  t  if the first element of s that differs from the corresponding element of t is smaller than that element of t.

A precise definition can be stated as follows. Given two different sequences s = (s1, s2, … , sm) and t = (t1, t2, … , tn) of integers, we say that s is lexicographically smaller than t if

• sk < tk for the smallest k such that sktk  or
• m < n and there is no k such that sktk.

Under the same conditions we say that t is lexicographically greater than s.

(See one of the exercises in chapter Enumeration algorithms.)

The lexicographic order is transitive (i.e., if s is lexicographically smaller than t and t is lexicographically smaller than u then s is lexicographically smaller than u).  Moreover, the lexicographic order is total (i.e., for any two different sequences s and t, either s is lexicographically smaller than t, or s is lexicographically greater than t).

Now consider a sequence of sequences, also known as a list of sequences. We say that the list is in lexicographic order if each sequence in the list is lexicographically smaller than (or equal to) each of the subsequent sequences in the list.  The following example shows a list of sequences (one sequence per line) in lexicographic order:

• 65 66 65 67 85 83
• 65 66 79 85 84
• 65 66 79 86 69
• 65 66 83 79 76 85 84 69
• 65 83 72
• 65 85 84 72 79 82
• 65 85 84 72 79 82 73 84 89
• 66 65 76 68
• 66 65 82
• 66 69 65 82

Lexicographic order for strings.  A string is a sequence of bytes. Since each byte represents a positive integer in binary notation, the lexicographic order between strings follows from the lexicographic order between sequences of integers. (See the section Lexicographic order in chapter String manipulation.)

A list of strings is in lexicographic order if each string in the list is lexicographically smaller than (or equal to) each of the subsequent strings. In the case of ASCII strings, the lexicographic order is analogous to the order in which words appear in a dictionary (except that it puts all the uppercase letters before all the lowercase).  Here is an example of a list of strings in lexicographic order:

```A B A C U S
A B O U T
A B O V E
A B S O L U T E
A S H
A U T H O R
A U T H O R I T Y
B A L D
B A R
B E A R
```

### Subsequences

A subsequence is what is left after some terms of a sequence are deleted.  More precisely, a subsequence of a sequence  (a1, a2, … , an)  is any sequence  (b1, b2, … , bk)  such that

b1 = ai1b2 = ai2,  … ,  bk = aik

for some sequence  i1 < i2 < … < ik  of indices.  For example,  (2, 3, 5, 8)  is a subsequence of  (1, 2, 3, 4, 5, 6, 7, 8)  but not a subsequence of  (1, 2, 3, 8, 4, 5, 6, 7).  (See the Subsequence exercise in the Arrays chapter.)

Just as sequences are represented by arrays, subsequences are represented by subarrays. A subarray of an array  a[1 .. n]  is any array  b[1 .. k]  such that  b[1] = a[i1], b[2] = a[i2], … , b[k] = a[ik]  for some sequence  i1 < i2 < … < ik  of indices.

### Segments

A segment of a sequence is a continuos subsequence. In other words, a segment is what is left after some of the initial terms and some of the final terms of the sequence are deleted.  (In some contexts, a segment is referred to as a run.)  More precisely, a segment of a sequence  (a1, a2, … , an)  is any sequence of the form  (ai, ai+1, ai+2, … , ak)  where  1 ≤ i and kn.  For example,  (2, 3, 4, 5)  is a segment of  (1, 2, 3, 4, 5, 6, 7, 8).

Similarly, a segment of an array  a[1 .. n]  is any array of the form  a[i .. k]  where  1 ≤ i and kn.  If i > k, the expression a[i .. k] represents the empty segment.

### Prefixes and suffixes

A prefix of a sequence is a segment that contains the first term of the sequence.  A suffix of a sequence is a segment that contains the last term of the sequence.

### Partitions

A partition of a set X is any collection P of nonempty subsets of X endowed with the following property:  every element of X belongs to one and only one of the elements of P.  Each element of P is a block of the partition.

Example:  {{1,3},{2,4,7},{5},{6,8}}  is a partition of  {1,2,3,4,5,6,7,8}.  The set {6,8} is one of the blocks of the partition.  (Please do not say the set {6,8} is a partition of {1,2,3,4,5,6,7,8}.)

### Floor and ceiling

The floor of a real number x is the result of rounding x down. In other words, the floor of x is the only integer i such that

i  ≤  x  <  i + 1 .

For example, the floor of 3.99 is 3.  The floor of x is denoted by

⌊ x ⌋ .

In C, the floor of a real number is given by the function  floor  from the math library.

The ceiling of a real number x is the result of rounding x up. In other words, the ceiling of x is the only integer j such that

j − 1  <  x  ≤  j .

For example, the ceiling of 3.01 is 4.  The ceiling of x is denoted by

⌈ x ⌉ .

### Base 2 logarithms

Our logarithms are always taken in base 2.  Hence,   log n   is a shorthand for  log2 n,  that is,  the real number x such that  2x = n.  (By the way: the correct notation is  log2n,  not  log 2 n,  not  log 2n,  and not  log2n.)

Therefore, log n is essentially equal to the number of bits in the binary representation of n, i.e., approximately 3.3 times the number of digits in the decimal representation of n.

(Our notation is in conflict with the notation of the math library of C, where the function  log  produces the natural logarithm, that is, the logarithm in base e = 2.71828…)