Collections with repetitions

In the previous article, we discussed what is meant by collections, we looked that the order does not matter in collections and how to compute the total possible number of collections when the repetition is not allowed.

In this article, we discuss the collections when the repetitions of the elements are allowed. Let’s get started.

Say we want to make a sequence of ‘k’ characters from a given ’n’ characters then the formulas are as follows:

Image for post
Image for post

For collections, we discussed those problems where the elements could not repeat for example the total number of handshakes case, there, of course, we need 2 different people to have a handshake. Similarly, when packing shirts in a suitcase, once we have selected a shirt and put it in the suitcase, we can not choose the same shirt again, so again by design, the problem was such that the repetition was not allowed. The same is the case with the line segment and triangle example, if we have to choose two points to draw a line segment we can not choose the same point again, and similarly, when we are choosing points for a triangle, we can not repeat the points.

So, turns out that all the problems that we have discussed so far on collections, the repetition was not allowed and we derived the formula for counting the total possible number of collections when the repetition is not allowed:

Image for post
Image for post
Image for post
Image for post

Let’s discuss the case when the repetition is allowed and how do we compute the total number of collections in such cases:

Image for post
Image for post

Say we are in a restaurant that serves 10 different items and we have to select 5 items and we can repeat the items meaning we take the same item 5 different times.

Image for post
Image for post

So, the question is how many combos are possible:

Let’s imagine that all these 10 items are on a counter in the restaurant and to begin with, there is just one serving of each of these items, say we select the first item as Idli(sequence does not matter here, we are picking up the items and placing it in our plate), now that counter is empty because, to begin with, there was only one idli

Image for post
Image for post

Now we want to order 1 more idli and since the items can repeat, the moment the container for the Idli is empty, the manager has to add more idli’s in that container or put a new container with Idli in it

Image for post
Image for post

And now we can select the Idli again and that’s what we do

Again the container containing the idli is empty, now the manager must again fill in the container with idli or put in one more container containing idli or in general containing the dish that we have just selected

Image for post
Image for post

This time we select ‘Poha’, so Poha is now out of the collection and the moment that happens, the manager has to open a new counter/place a new container that serves Poha

Image for post
Image for post

And again we select Poha from the new container and the manger now puts in one more container containing Poha

Image for post
Image for post

And now this time say we select Vada, and Vada is gone from the counter, this time the manager does not have to do anything because we have selected a maximum of 5 dishes and assuming that there is just 1 customer, the manager does not need to refill the container

Image for post
Image for post

Let’s see again how we approach this problem, to begin with, we had 10 counters, the moment we selected a dish, a new container arrives containing the exact same dish that we selected and the manager had to provide with these new containers 4 times (5–1) and not 5 times(because as soon as we select the 5th dish, we can not select anymore and the manager does not have to fill in that container/provide with new container).

We can say that instead of the original 10 counters, we had a total of 14 counters and the problem boils down to selecting 5 items from a given set of 14 items.

The problem is how do we know what these extra 4 containers should contain, for example, if we order a Parantha and the 11th container must contain parantha and if we choose something else than the 11th container must contain that item, so we are not sure of the items in the 4 containers we add on the counter.

So, it does not actually matter what dishes we select, all that matters is that the manager should provide with the item that the customer selected, and no matter what the customer selected, in this case, we’ll always have a total of 14 (10 + 5–1) counters from which we need to select items from 5 counters.

So, we have a total of (n+k-1) counters from which we need to select the items from ‘k’ counters.

Image for post
Image for post
Image for post
Image for post

In summary, we have formulas for computing the total possible ways of sequences, collections when the repetition is allowed, is not allowed as below:

Image for post
Image for post

Collections + multiplication principle

Let’s take one example wherein we need to use the knowledge to collections and the multiplication principle. So, here is the problem statement:

Image for post
Image for post
Image for post
Image for post

We can break this problem in two parts, the first part could be: given a set of 7 boys, select 2 boys who are going to be in the committee and the second part is to select 2 girls who are going to be a part of the committee from a total of 8 girls.

Once we have the number of ways for these steps, then by multiplication principle, the total number of ways of forming a committee is going to be the product of these two numbers

So, the total number of ways of forming a committee is given as:

Image for post
Image for post

Let’s look at another example and then we can derive the general formula for such problems:

Say the Indian captain has to form a team of 11 players from a total of 16 players

Image for post
Image for post

And say the captain wants at least a specific number of players from each category:

Image for post
Image for post

So, we can think of it as a more advanced version of the problem we saw before were in we had to form a committee, so just as we did that problem by solving each problem intermittently and then combining them, we are going to do the same thing here i.e we select 5 batsmen from a total of 7 batsmen, 1 wicket-keeper from a total of 2 wicket-keepers and so on:

Image for post
Image for post

So, given a total of ’n’ items of ‘i’ different types wherein we have m₁ items of the first type, m₂ items of the second type, and all the way up to mᵢ items of iᵗʰ type and we want to select a total of ‘k’ elements such that we have to select k₁ of the first type, k₂ items of the second type all the way up to kᵢ items of the iᵗʰ type

Image for post
Image for post

Collection + subtraction principle

Image for post
Image for post
Image for post
Image for post

So, we have 5 different types of specialists in a hospital and the count(of doctors) of each specialty is also given and we want to form a committee that contains at least one gynecologist.

As we have the at least constraint, we know that it’ll a little tricky to solve this using the multiplication principle, so we try to solve this using the subtraction principle.

We convert the problem to a standard problem wherein we have three sets A, B, and C:

Image for post
Image for post

We have the total possible ways of forming set A as the following(we want to select 4 doctors from a total of 4 doctors)

Image for post
Image for post

For set C, we want committees that have no gynecologist that means we can not use the 5 gynecologists in my committee, which means that we have to choose a 4 member committee from a total of 16 doctors

Image for post
Image for post

And now that we have the counts corresponding to set A and C, we can count the value of set B as the difference between the two:

Image for post
Image for post

In this article, we discussed how to count the total number of possible collections when the repetition of the elements and how to leverage the multiplication and subtraction principle when forming collections with repetitions.

References: PadhAI

Written by

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store