Popular Courses
Beginner – Linear Regression
Introduction
Beginner – Decision Trees
Introduction
Beginner – Neural Networks
Introduction

Sign in to Curvingo

or

New Account     Reset Password     

Plans

Details
Permutations and Combinations
Introduction
Fundamental Principle of Counting
Practice: The Multiplication Principle
Permutations
Practice: Factorial Notation
Derivation of the Formula for nPr
Permutations When All the Objects Are Not Distinct Objects
Practice: Permutations and Arrangements
Combinations
Practice: Combinations and Selections
Miscellaneous Examples
Chapter Review: Mixed Practice
Summary
Curvingo · Made in India

Share

Send us Feedback

Please let us know if you have any feedback and suggestions, or if you find any errors and bugs in our content.

Sorry, your message couldn’t be submitted. Please try again!

Thanks for your feedback!

Reset Progress

This will delete your progress and chat data for all chapters in this course, and cannot be undone!

Glossary

Select one of the keywords on the left…

Permutations and CombinationsFundamental Principle of Counting

Reading time: ~25 min

Mohan is packing for a school trip. He has 3 pants and 2 shirts, and every shirt goes with every pant. How many different outfits — one pant and one shirt — can he put together?

Call the pants P_1, P_2, P_3 and the shirts S_1, S_2. Dress Mohan in every possible way: tap a pant, then a shirt. Each new outfit lights up one path of the tree below; the finished tree is Fig. 6.1 of your textbook.

Read the tree from left to right. The first fork has 3 branches, one for each pant. Each of them splits into 2 branches, one for each shirt. So the number of complete outfits at the right-hand end is 3 \times 2 = .

Three Choices in a Row

Sabnam carries a school bag, a tiffin box and a water bottle every day. She owns 2 bags (B_1, B_2), 3 tiffin boxes (T_1, T_2, T_3) and 2 water bottles (W_1, W_2). In how many different ways can she pack one of each?

She can pick a bag in ways. Each bag can go with any of the 3 tiffin boxes, so there are 2 \times 3 = bag-and-tiffin pairs. Each pair can go with either bottle, so the total is 6 \times 2 = .

Fig. 6.2 — every way of packing one bag, one tiffin box and one water bottle.

The tree shows the same thing: 2 bag branches, each with 3 tiffin branches, each with 2 bottle branches — and 12 outcomes at the end, from B_1T_1W_1 to B_2T_3W_2.

The Multiplication Principle

Both stories follow one pattern: a chain of choices made one after another, where the number of options at each stage does not depend on what was picked before. This pattern has a name — the fundamental principle of counting, or simply the multiplication principle.

Fundamental principle of counting. If one event can happen in m different ways, and after it a second event can happen in n different ways, then the two events, in that order, can happen in m \times n ways.

The principle is not limited to two events. If a third event can then happen in p ways, the total is m \times n \times p, and so on for any number of events. Mohan's outfits were two events in a row: 3 \times 2. Sabnam's packing was three: 2 \times 3 \times 2.

Does the order of the events matter? Mohan could just as well pick his shirt first. Then the count is 2 \times 3, which is again . You may fix any convenient order of the events and the count comes out the same. What matters is that you fix one order and count the options stage by stage.

Tip

Multiply when the choices happen one after another — this, and then that. Later in the chapter you will also add: when the outcomes split into separate cases — this, or that.

Words From ROSE

Example 1 : How many 4-letter words, with or without meaning, can be made from the letters of the word ROSE if no letter may be repeated?

Think of a word as four empty boxes to fill. Fill the boxes with the letter tiles and watch the number under each box: it shows how many letters were free when that box was filled. Complete both missions.

Solution : We need the number of ways to fill 4 places with the letters R, O, S, E, using each letter at most once. The first place can take any of the 4 letters. Once it is filled, letters remain for the second place, then 2 for the third and 1 for the last. By the multiplication principle, the number of words is

4 \times 3 \times 2 \times 1 =

Note

If letters may be repeated, every place can take any of the 4 letters, whatever was used before. Then the number of words is 4 \times 4 \times 4 \times 4 = .

Example 2 : Four flags of different colours are available. How many different signals can be made if a signal uses 2 flags, one below the other?

Solution : A signal is two places, top and bottom, filled with different flags. The top place can take any of the 4 flags; after that, the bottom place can take any of the remaining . So there are 4 \times 3 = signals.

Example 3 : How many 2-digit even numbers can be made from the digits 1, 2, 3, 4, 5 if digits may be repeated?

Here one place is fussier than the other: an even number must end in 2 or 4. The unit's place is filled first. Fill the boxes for each mission.

Solution : Start with the fussy place. The unit's place can be filled in only ways, by 2 or by 4. Since repetition is allowed, the ten's place can then take any of the 5 digits. By the multiplication principle there are 2 \times 5 = even 2-digit numbers.

Tip

When one place has a condition — even, not zero, must be a vowel — fill that place first. Its options do not depend on the other places, so the counting stays simple.

Signals of Every Length

Example 4 : Five different flags are available. How many different signals can be made by arranging at least 2 flags, one below the other, on a vertical staff?

A signal may use 2, 3, 4 or all 5 flags. These are separate cases: no signal has both 3 flags and 4 flags. So count each case, then add.

Each row below is one case, already counted with the multiplication principle. Tap the cases each mission needs; their counts add up underneath.

Solution : Signals with 2 flags fill 2 places from 5 flags: 5 \times 4 = 20. With 3 flags: 5 \times 4 \times 3 = . With 4 flags: 5 \times 4 \times 3 \times 2 = 120. With 5 flags: 5 \times 4 \times 3 \times 2 \times 1 = 120.

The cases do not overlap, so the required number of signals is 20 + 60 + 120 + 120 = .

Speed Round: Multiply, Don't Add

Each question is a chain of choices. Spot the stages, multiply their options and pick the answer. After each answer you will see the working.

Get five right to move on.

${q}
Sina