Collections

So far, we have seen the multiplication principle, sequences with repetitions of digits, alphabets, sequences with some constraints, subtraction principle. In this article, we discuss the Collections.

In a sequence, the order of the elements matters so the sequence ‘cat’ is not the same as the sequence ‘act’

In a collection, the order does not matter, so all the possible words formed using permutations on the characters {a, b, c} are the same:

In the previous articles, we discussed how to form a sequence of ‘k’ characters from a given ’n’ characters and we also derived the general formula for the same:

Now we are interested in knowing the total possible number of collections of 3 letter words that we can form from a given ’n’ characters(in a collection, ‘act’, ‘cat’ and all other possible permutations that can be formed using {‘a’, ‘c’, ‘t’} would count as 1):

To do this, let’s break down the problem of creating sequences in two steps. In the first step, we finalize the 3 letters to be used in the word/sequence, so this is the collection we are creating(say we select the alphabets {‘a’, ‘c’, ‘t’}

And once we have selected the 3 letters, in this case, we know that there are a possible of 3! sequences we can form from it.

We are interested only in the first step to compute the total number of possible collections we can form using the three alphabets.

Let’s say we have ’N’ ways of selecting ‘k’ elements from a given ’n’ elements and once we have selected the ‘k’ elements, then we know that there are ‘k!’ ways of re-arranging those ‘k’ elements.

Then we can say that the total number of sequences we can get is represented by the product of these two numbers i.e ‘N * k!’. These are two independent decisions(the choice that we make in the first step does not affect the choice that we make in the second step) we are taking one after the another and we also know from our earlier discussion that this can be represented as ‘ (n!) / (n-k)!’, so by equating these two terms we can get the value of ‘N’

So, when computing the total number of possible collections, ‘k!’ comes into the denominator of the formula to compute the number of possible sequences.

For each collection(set of 3 words in this case), we have a ‘k!’ possible arrangements(each collection is getting counted ‘k!’ time) which we do not want to count, so we divide the total possible number of sequences by ‘k!’.

Let’s understand this with an example:

So, here we have to select 3 characters from a possible of 5 characters (‘a’, ‘e’, ‘i’, ‘o’, ‘u’).

Say we fix the first two characters as ‘a’ and ‘e’ respectively, then we can have any of the remaining 3 characters for the third slot and we get possible of 3 collections(‘aei’, ‘aeo’, ‘aeu’) by fixing the first two letters.

Then we fix the first two characters as ‘a’ and ‘i’, and the possible sequence we can make here are: ‘aie’, ‘aio’, ‘aiu’ but ‘aie’ has the same letters(though in a different order) as ‘aei’ which was already accounted for and since in collections, the order does not matter which means ‘aei’ is essentially the same as ‘aie’ and we count them as 1 in collections.

Similarly, we form the next possible combination of the first two characters and we can count the total number of ways of forming a collection.

So, from the above table, we can say that there are 10 possible collections of 3 vowels that we can form from a given set of 5 vowels.

Let’s see the number of sequences we can form:

We can take any of the entry from the 10 possible collections and for each entry/collections, we can re-arrange the collection in 3! ways(we have 3 elements in the collection) and since the order does not matter in sequences, we can actually re-arrange the elements.

So, any of the entries from the set of 10 collections gives rise to 3! re-arrangement or sequences. Therefore, the number of sequences is given as ‘10 * 3!’.

Number of collection * Permutations possible(within any of the collection) = Number of sequences

We can count the number of sequences also using the standard formula:

n! / (n-k)!

And using that value we can count the number of collections in this case as:

which again gives the value as 60.

Let’s take one more example:

The first thing is to be sure about if we are trying to form a sequence or a collection, sequence means we are arranging things in specific slots, collection means no specific order. So, this looks like a problem where we just have to form a committee, all four members are equal, there is no 1st member, 2nd member, and so on.

Earlier when we looked at this problem when discussing the multiplication principle, there were name/numbered slots

But in this case, we don’t have any special numbering/post names, they are all members and forms a part of the collection

So, earlier when we had the name slots and suppose we selected 4 people (A, B, C, D) from a group of 15 people and we also arranged those 4 people and each arrangement would give us a new sequence

Now that we are creating a collection, all these 4! different arrangements would get counted as 1 because they are essentially the same 4 people as the order does not matter in the collection.

And we can use the standard formula to compute the number of sequence first and divide it by 4! in this case to get the number of collections.

This is also termed as combinations.

Let’s look at one more example:

Let’s first see how is this related to collection, we are just given a set of 10 people.

For a handshake, we need 2 people, once we choose 2 people there can be a handshake between them, so this problem boils down to the problem of selecting 2 people from a given set of 10 people.

And note that in a handshake, the order does not matter, so person ‘A’ shaking hands with person ‘B’ is the same as person ‘B’ shaking hands with person ‘A’. So, this is not a sequence, we are not trying to arrange people in a particular order of 2, there is no slot 1 and slot 2, we are just going to select two people and they are going to shake hands so order does not matter.

And we can compute the total possible collections/handshakes, in this case, using the standard formula:

Let’s look at another example:

So, there are 10 different things available to us, and this is again a problem of collection because we have to put things in a suitcase and there is no order there, we just need to pick any 3 elements and put them in the suitcase. And we can use the standard formula to get the required answer:

Let’s take one more example:

This is related to collections because to create a line segment we need 2 points, so the problem boils down to selecting 2 points from given 6 points and we can again use the standard formula to compute the required value:

Let’s take one more example:

Let’s say we have a polygon of 8 sides, then there are multiple triangles possible here

To form a triangle, we need 3 vertices, so the problem essentially is to select 3 of the 8 vertices of a polygon and the number of triangles can be computed using the standard formula;

In this article, we discussed what is meant by collections, how a collection is different from a sequence, how to compute the total number of possible collections in a given scenario.

References: PadhAI