Permutations & Combinations – All Possible Selections (Part 1)


This lesson will extend the concept of selections and, in particular, will talk about the number of ways to select any number of objects from ‘n’ distinct objects.

Let’s go back to color mixing! Suppose you have the following three colors with you:

Blue Red Yellow

And you wish to make as many different colors as possible by mixing (in equal proportions) some, all or none of the above colors with white

White

How many different colors can be formed this time?

Let’s list out all the possibilities:

White WhiteBlue WhiteRed WhiteYellow WhiteBlue

Red

WhiteBlue

Yellow

WhiteRed

Yellow

WhiteBlue

Red

Yellow

A total of 8. To make a new color, all we had to do was select any number of colors from the given set of three colors. (and of course mix them)

Can we derive a formula for this kind of a problem? In how many ways can we select any number of objects from a collection of n different objects?

Recall that the number of ways to select exactly r objects out of n distinct objects was nCr. In this situation, we have a choice. Either select no object, or select one object, or select two objects, and so on till selecting all objects.

Selecting no object can be done in nC0 or 1 way.

Selecting one object can be done in nC1 ways.

Selecting two objects can be done in nC2 ways.

And, so on, selecting all the objects can be done in nCn ways.

Now since our ‘task’ will be over if we do any of the above selections, i.e. there is a choice of doing any of above sub tasks, we’ll use the addition principle to arrive at the final answer.

The required number of ways will therefore be: nC0 + nC1 + nC2 + nC3 + … + nCn

Let’s check our earlier answer by using this formula. In case of all possible selections from 3 different colors, we get the required number as 3C0 + 3C1 + 3C2 + 3C3 = 1 + 3 + 3 + 1 = 8. Great!

Lesson Summary

  1. The number of ways to select any number of objects, from a collection of n different objects equals nC0 + nC1 + nC2 + nC3 + … + nCn

 

“But wait a minute! What if the objects were identical? And what if only some of them were identical?”

That’s what is coming up next!

But before that, I’ll derive another nice looking formula for the case covered in this lesson. See you there.

Leave a comment