Sequence

A sequence (from Latin sequentia "a following") is a function whose domain is a subset of N. For example, the natural numbers or the Fibonacci sequence.

Contents

1   Properties

The number of elements is called the length.

Sequences may be finite or finite.

A sequence with a single repeated element is called a constant sequence.

A sequence with 1 and -1 repeated is called an oscillating sequence.

1.1   Subsequences

A subsequence of a sequence A is a sequence that can be derived from A by removing some elements without changing the order of the remaining elements. For example, the prime numbers of a subsequence of the positive integers.

The set of all subsequences of a given sequence can be found like so:

def get_subsequences(sequence):
  """
  >>> list(get_subsequences([1, 2, 3, 4]))
  [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]
  """
  for i in xrange(len(sequence) + 1):
    for j in xrange(i+1, len(sequence) + 1):
      yield sequence[i:j]

This doesn't actually give all subsequences - it gives all "subsets". It does for example include [1, 3]

2   Classification

The Taylor series:

1 + x + x^2 + x^3 + ... + x^n + ... = 1 / (1 - x)

2.1   Tuple

A tuple is a sequence that is finite.

A tuple with k-elements is a k-tuple. A 2-tuple is also called a pair.

2.2   Stream

A stream is a sequence that is infinite.

3   Representation

We do not typically think of a sequence as a set of ordered pairs; instead, we think of it as a series.

Even though a sequence is a function, the usual function notation is rarely used for sequences. Instead of denoting the value of the sequence a at index n by \(a(N)\), we denote it by \(a_n\).

static/images/Fencepost_error.svg

Indices may start at 0 or 1 depending on what is being counted. Say you're counting the length of a fence, so you are numbering the posts. It's preferable to number the posts starting at zero, because after having numbered N posts, you know the length of the fence is N. On the other hand, if you are counting the posts themselves, you would want to say "one!" after the first post, as you have just counted one post. In this case, the number you assign the post is the number of posts counted after encountering it. Otherwise you end up having to +1 at the end. (This is also why rulers start with 0 - a ruler isn't about counting the marks, it's about measuring the space between the marks.)


To denote the subsequence of natural numbers 1, 2, ..., 10 without the pernicious three dots, four conventions are open to us:

1 <= i <  11
0 <  i <= 10
1 <= i <= 10
0 <  i <  11

The best of these is the first for two reasons. First, it does not require using unnatural numbers to write a subsequence including 0 unlike the second and forth option. Second, it can represent the empty sequence naturally (0 <= i < 0) unlike the third option (a closed range, 1 <= i <= 0). [1]

As a consequence, we assign to the starting element of a sequence of length N the subscript value of 0, not 1, since, adhering to our convention, this has the advantage that the subscript range 0 <= i < N is nicer than 1 <= i < N + 1. [1]

4   Prefix sums

A prefix sum is the consecutive total of the first n elements of a sequence. Prefix sums allow us to calculate the total of any slice of a sequence in constant time. This is useful for instance if you want to calculate the sum of every slice of a sequence.

We can calculate the prefix sums in O(n) time:

def prefix_sums(nums):
    return reduce(lambda sums, num: sums + (sums[-1] + num,),  nums, 0,)

Similarly, we can calculate suffix sums, which are the totals of the last k values.

5   Ordered Pair

For any two objects, a and B, the ordered pair (a, b) is a notation specifying the two objects a and b, in that order.

For any two objects, a and b, the ordered pair (a, b) is defined to be the set { {a}, {a, b} }.

Many mathematicians view the concept of ordered pairs as an undefined primitive notion.

There are two important properties of ordered pairs.

  1. You can form the ordered pair of any two objects whatsoever
  2. The familiar condition for equality of ordered pairs: (a, b) = (c, d) <-> a = c & b = d

6   References

[1](1, 2) Edsger W. Dikjstra. August 11, 1982. EWD381: Why numbering should start at zero. https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html