Q.A boy is to walk from P to Q. However, he can take a right step or an upward step, but not necessarily in the order shown in given figure. Find the number of possible paths he can take.

Permutations: Arranging Things in Order

Imagine you have three different books — a Physics book, a Chemistry book, and a Maths book — and you want to place them on a shelf. How many different ways can you arrange them?

You could put Physics first, then Chemistry, then Maths. Or Physics, Maths, Chemistry. Or Chemistry, Physics, Maths. And so on. Each distinct ordering is called a permutation of the three books.

Building the Intuition: The Multiplication Principle

Let's count the arrangements for those three books. For the first position on the shelf, you have 3 choices (any of the three books). Once you place one, for the second position you have 2 choices left. For the third position, only 1 choice remains.

So the total number of arrangements is:

This is the multiplication principle at work: the number of ways to do a sequence of tasks is the product of the number of choices at each step.

The General Formula

Now suppose you have $n$ distinct objects and you want to arrange all of them in a row. By the same logic:

• 1st position: $n$ choices
• 2nd position: $n-1$ choices
• 3rd position: $n-2$ choices
• …
• Last position: $1$ choice

The total number of permutations of $n$ distinct objects taken all at once is:

This product has a special name — factorial — written as $n!$ (read "n factorial").

For example, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.

What If You Don't Arrange All Objects?

Often you have $n$ objects but only want to arrange $r$ of them (where $r \leq n$). For instance, from 10 students, how many ways can you choose a first, second, and third prize winner?

• 1st prize: 10 choices
• 2nd prize: 9 choices
• 3rd prize: 8 choices

Total: $10 \times 9 \times 8 = 720$

In general, the number of permutations of $n$ distinct objects taken $r$ at a time is:

This product has exactly $r$ factors, starting from $n$ and decreasing. …