11.1. Introduction to Permutations

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

Permutations are all about the different ways we can arrange a set of items where the order matters. For example, if we have two people, Person 1 and Person 2, having them in the order of (Person 1, Person 2) is different from (Person 2, Person 1). This fundamental concept illustrates that in permutations, the arrangement significantly influences the outcome.

Imagine you have a set of colored marbles: red and blue. If you arrange them in a line, the combination of red first and then blue is distinct from blue followed by red. This simple example highlights how order affects the arrangement.

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

An n-permutation involves selecting 'n' elements from a larger set of distinct elements, while considering the order of selection. For example, if we have a set of three different fruits: apple, banana, and cherry, and we want to pick two, the sequences (apple, banana) and (banana, apple) are counted as different permutations.

Think about how you can arrange your favorite toppings on a pizza. If you have three options—cheese, pepperoni, and mushrooms—and you want to choose two, the arrangement of cheese first followed by pepperoni is different from the reverse. The ordering in pizza topping arrangement affects the final product!

So you are given a set with n distinct objects and we want to find out how many k-permutations I can have from this set.

To calculate k-permutations from a set of n distinct items, we use the permutation function denoted as P(n, k). The formula P(n, k) = n * (n - 1) * (n - 2) ... * (n - k + 1) shows how the choices decline with each selection. The critical point here is that we multiply the available choices for each successive slot since the order of arrangement matters.

Consider you are selecting books to read from a library. If you have 5 books and choose 2, for the first slot, you have 5 options. If you pick one, for the second slot, only 4 books remain. This sequential reduction highlights how we arrive at the total count of permutations.

Now, we will consider the case where even in these selections, the repetitions are allowed.

In cases where repetitions are allowed, calculating permutations becomes simpler. If we have a set of n distinct items and we want to form k-permutations with repetitions, we can fill each of the k slots with any of the n items.

Think about choosing toppings for ice cream cones where you can use the same topping more than once. You can create combinations like chocolate, chocolate or vanilla, vanilla. Every selection allows for a repeat since each drop counts equally, leading to a higher number of possible arrangements.

So now we have the value of P(n, k) where k is non-zero and in the range 1 to n and we have the value of P(n, 0).

By understanding the values of P(n, k) and P(n, 0), we can situate ourselves in various permutation scenarios. P(n, 0) is defined as 1, meaning there is one way to select zero items. This inclusion helps us solidify the concept of permutations within both non-empty and empty cases.

Visualize a menu at a restaurant. If you decide to order nothing (which is one way of ordering), that's similar to saying there's one way to pick no items. In contrast, ordering something represents selecting from the permutations of what's available.

--