Skip main navigation

Some mathematical objects: sequences, sets and collections

Some mathematical objects: sequences, sets and collections
9.1
We are not going to count the elements of any set, but just of some sets that contain some particular mathematical objects, like sequences and collections. Let us define them. First of all, let us introduce a notation. For each integer n, I-n is the set of integer numbers from one to n. And here is the notion of sequence. Let us take an integer k and n. A k-sequence of I-n is a sequence of length k that that is an element of the Cartesian product of I-n, times I-n, times I-n, k times. So, any element of this Cartesian product is of the kind X-1, X-2, X-k in a precise order where each X-i belongs to the set I-n.
73.1
And we will say that the sequence is without repetitions if the X-i are distinct. So for instance, (1,3,3,2) is a 4-sequence with repetitions because three is repeated twice of I-3. It is also a 4-sequence of I-5, of I-7. Sequences can describe many situations, and for instance, they can describe functions. Let us consider a function between I-k to I-n. Well, in order to describe this function, it is enough to know what are the values of f(1), f(2), f(k). So let us put a f(1), f(2), f(k) into a sequence. Then, this k-sequence of elements of I-n, totally describes the function f.
131.5
So the bijection principle will tell us that the number of k-sequences of I-n equals the number of functions from I-k to I-n. So it is enough, it will be enough to count the number of k sequences of I-n in order to know how many functions there are from I-k to I-n. Let us consider a distribution of four different toffees to three kids in terms of functions and in term of sequences. For a function, we can consider the four toffees as the domain of the function with values into the tree kids, 1, 2, 3. And we assign the value J to the toffee T-i if the toffee number i goes to the kid number J.
194.9
Alternatively, we can describe this distribution via a sequence, a 4-sequence of I-3 (x1, x2, x3, x4) where x1 is the child that receives toffee one, x2 is the child that receives toffee two and so on, x4 is the child that receives toffee four both sequences and functions describe perfectly this kind of distribution. A function from I-k to I-n may be injective. This means that different values goes into different values. In terms of the corresponding sequence this means that the sequence f(1), f(2), f(k) of the values of f has no repetitions.
247
And there is a correspondence between sequences, k-sequences of I-n without repetitions, and functions that are injected from I-k to I-n, and therefore the bijection principle tells us that the number of injective functions from I-k to I-n equals the number of k-sequences of I-n without repetitions. So once we will know this number, we will know the number of injective functions. Sequences have an implicit order. The sequence (1,2) is different from the sequence (2,1). When we consider sequences, we take the order into account. But there are distributions in which the order does not count.
292.3
For instance, you build a hand of five cards among 52, where the order does not count, and the mathematical objects that takes into account these kinds of elements is what is called a collection. A k-collection of I-n is a non ordered family of k elements of I-n. We will denote it with a square bracket and [x1, x2, xk] denote the elements that can be repeated inside the bracket.
331.7
So for instance, when you want to describe a packet of candies where there is no order and there are nine candies 3 of type A, 2 of type B and 4 of type C, we can describe it through a collection that contains three A, two B and four C, and we can reverse the order inside the brackets and the collection does not change differently from the sequences. When the collection has no repetitions, that is the x-i are distinct, what we obtain is a set, and instead of denoting it with a bracket, if we know that the elements are distinct, we denote it with the typical bracket with which we describe as set.
383.4
This happens for instance, if we want to describe a hand of five cards. When we take five cards from a deck, the cards are distinct, and so what we obtain is a set like that one.
401.6
Among the sequences permutations play a special role. A permutation of the sequence a-1, a-k of I-n is any other sequence that contains the same terms of the initial sequence, that is a sequence b-1, b-K, in such a way that the collection formed with the elements a-1 ,a-k is the collection formed with b-1, b-k. So we have all the terms of a-1, a-k in any other possible order. For example, the sequence (3,4,4,1) a permutation of (1,3,4,4) When we consider words, what we call anagram of a word, is actually any permutation of the sequence formed with the letters of the word.

What are the main mathematical objects that we are going to be able to count? Sequences, sets and collections will be the main characters of the MOOC.

This article is from the free online

Combinatorics: Strategies and Methods for Counting

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now