All Possible Selections (Part 2)


In this lesson, I’ll derive another expression to compute the number of ways to select any number of objects from a collection of ‘n’ distinct objects. Let’s go back to color mixing one more time.

Our task was to select any number of colors from the following collection:

Blue Yellow Red

Suppose you take the white color with you and decide one by one whether you want to mix blue, yellow and red with it or not. You start moving from the left, reach blue and decide you want to select (and mix) it or not. Once you’re done, you move on to the next color and so on, till you reach the very right. Have a look at the following figure:

Blue Yellow Red

 Start Here

 DownArrow  DownArrow  DownArrow

 Selection Complete

White RightArrow

Select OR Don’t Select

Select OR Don’t Select

Select OR Don’t Select

RightArrow

MultiColor

Now at every step (or color), you have two choices, select and not select. And our task of selection is completed when we are done with each color. And since we have 3 colors in total, and we have two choices at each step, then by using the multiplication principle, the number of ways will be 2 x 2 x 2 = 23 = 8.

Note that this is the same answer as obtained in the previous lesson, obtained using an entirely different way of thinking. That’s the magic of permutations and combinations!

Now we’re in a position to write down formulas. Suppose we had n distinct objects instead of three. Then to select zero or more objects out of this lot, we’ll first lay down the objects in a row.

O1           O2           O3           …            …            …            On

Now we’ll start with an empty basket at the very left, come to each object, and decide whether we want to select it or not – two choices. Then we’ll move on to the next object, and continue in the same way, until we reach the nth object at the very right, where our selection process will be complete.

Now our task is selection of any number of objects, our subtasks are individual selections or rejections of each object. Since each subtask can be performed in two ways (selecting or not selecting) and there are n such subtasks, the number of ways, using the multiplication principle, will be 2 x 2 x 2 x … x 2 (n times) = 2n

That’s it for this lesson !

Lesson Summary

The number of ways to select any number of objects, from a collection of n different objects equals 2n

“But about the previous formula – nC0 + nC1 + nC2 + nC3 + … + nCn? This looks entirely different than 2n !”

Well, both these expressions are equal. Why don’t you verify this yourself?

See you in the next lesson.

Leave a comment