11. Permutation and Combination

So to begin with, what is a permutation of a set of objects? As the name suggests, it is an ordered arrangements of objects and when I say the ordered arrangement of the objects, that means the ordering of the objects matter here.

A permutation refers to the different ways in which a set of objects can be arranged in order. The main point to understand is that the specific sequence in which the elements appear makes a difference. For example, if we have two people, person 1 and person 2, the arrangement 'Person 1 followed by Person 2' is different from 'Person 2 followed by Person 1'. This concept is crucial when it comes to permutations because it relates to the order of selection.

Imagine you have two distinct flavored ice creams, vanilla and chocolate. If you put vanilla in a cone first and then chocolate, that’s different from putting chocolate first and then vanilla. The order of scoops matters—just like in permutations!

We define what we call as r-permutation and an r-permutation is nothing but an ordered selection of r elements from a set.

An 'r-permutation' refers specifically to the selection of r elements out of a larger set of n distinct elements, with the order of the selection being important. To denote the number of r-permutations of n elements, we use the notation P(n, r). This formula calculates how many ways we can arrange r selected items from a group of n distinct items.

Consider a race with three runners: Alice, Bob, and Charlie. If we want to find out in how many different ways they can finish in 2nd and 3rd place—their placements matter. The arrangements can be: 'Alice finishes 2nd, Bob finishes 3rd', or 'Bob finishes 2nd, Alice finishes 3rd', resulting in distinct outcomes.

The number of such r-permutations from a set consisting of n distinct elements is denoted by the permutation function P(n, r).

The calculation involves the product rule, which is used to derive the formula for P(n, r): P(n, r) = n × (n-1) × (n-2) × ... × (n-r+1). This formula accounts for the fact that once an element has been chosen, it cannot be selected again. This is why the choices reduce as we fill each successive position.

Imagine you have 4 medals and you want to award them to only 3 athletes. For the 1st medal, you have 4 choices. After handing over that medal, you only have 3 left for the 2nd medal, and 2 remaining options for the last one. Thus, the ways you can award these medals follow the permutation formula.

We define P(n, 0) = 1, namely, no way of permuting 0 objects.

When we talk about permutations, if you have a set of n objects but decide not to choose any (0 objects), there is exactly one way to do that: by simply not choosing anything at all. This principle helps in establishing the foundation of the permutation function.

Think about choosing toppings for a pizza. If you decide to have no toppings (0 toppings), there is only one way to do that: just order the plain pizza. You’re not adding anything, so only one way exists!

Now, we can define C(n, r), which represents unordered selections.

While permutations focus on the order of arrangement, combinations concern themselves with whether elements are selected together without regard to order. C(n, r) marks the number of ways to choose r objects from n distinct objects when the order does not matter, ensuring the focus is on the selection rather than arrangement.

Consider a fruit salad. If your basket includes apples, bananas, and oranges, selecting an apple and a banana counts as the same choice as choosing a banana and then an apple. Here, only the chosen fruits matter, not the order in which they are picked.

The relation between the permutation and combination functions is C(n, r) = P(n, r) / r!.

This relationship arises because every combination can appear in multiple arrangements. Thus, the number of permutations of r chosen items (P(n, r)) would be divided by the number of ways to arrange these same r items (r!), providing the combination count. This illustrates the connection and the mathematical relation between the two concepts of arrangement.

Think of creating a team from a group. If you can choose 3 out of 10 players to form a basketball team, selecting 'Player A, Player B, Player C' is the same as 'Player B, Player C, Player A'. When counting teams, we only list unique combinations, not the rearrangements.

--