11.2. Definition of k-Permutation

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 of arranging a set of objects where the order in which the objects are arranged is crucial. For example, if we consider two people, person 1 and person 2, their arrangement as 'person 1 followed by person 2' is different from 'person 2 followed by person 1'. This highlights that the sequence or order is important in permutations.

Think of a race where the first person's finish is crucial. If person A finishes before person B, that is a different outcome than if person B finishes before person A. The order of finishers is what we call permutations in the context of race placements.

So we define what we call as k-permutation and k-permutation is nothing but an ordered selection of k elements from a set. So you are given a set which has a certain number of elements, of course, it should have k or more number of elements.

A k-permutation refers to selecting 'k' elements from a total of 'n' distinct elements, where the order of selection matters. This means that picking elements in different sequences will result in different permutations. To calculate the total number of k-permutations from a set of n distinct elements, we will denote this quantity as P(n, k).

Imagine you have 5 different colored balls (red, blue, green, yellow, and purple), out of which you want to choose 3 to display in a row. The different ways you could arrange these 3 balls (like red-blue-green vs. blue-red-green) are all considered different k-permutations.

The number of such k-permutations from a set consisting of n distinct elements is denoted by this quantity or this permutation function P(n, k). So for instance, if I consider n = 3 and k = 2 then P(3, 2) = 6.

To calculate the number of k-permutations, you can use the formula P(n, k) = n! / (n-k)!, where 'n!' denotes the factorial of 'n'. In the case of 3 distinct items and selecting 2, the permutations can be meticulously calculated. You get 3 choices for the first item and then 2 remaining choices for the second item, leading to 3 x 2 = 6 total arrangements.

Back to our colored balls, if you have 3 colors (red, blue, yellow) and you want to pick and arrange 2, you can have combinations such as red and blue or blue and red. These arrangements help demonstrate how the permutation works - every different order counts as unique.

If I apply the product rule then I can derive the formula P(n, k) = n * (n-1) * (n-2)...(n-k + 1).

The product rule states that if you have a number of sequences, the total number of arrangements can be found by multiplying the number of options available at each step. When selecting a k-permutation, you first have 'n' options, then 'n-1' for the next item, and so on, until you have filled 'k' slots.

Imagine planning a dinner menu where you need to select 3 dishes from 5 available options. For the first dish, you can select any of the 5 options, for the second dish you’ll have 4 options left, and for the third dish, there are only 3 options left. Thus, the combinations follow a similar path of choices decrementing as you select.

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

P(n, 0) equals 1 because there's only one way to arrange a non-selection: to select nothing. This definition acts as a base case in permutations, showing that arranging zero items results in just one arrangement, that of doing nothing.

Consider getting ready for a party but choosing not to wear any accessories. The act of not wearing any is still a choice you made, representing one way to not select anything.

So if I unify these 2 values I get that P(n, k) = n! / (n - k)!.

The final formula P(n, k) consolidates the understanding of permutations into a single expression, providing a quick method to calculate the number of ways to arrange 'k' selections from 'n' total items. This formula reflects how many times we can choose distinct items while respecting order.

Imagine again you have 5 different ball colors to choose from, and you want to display only 3. The formula simplifies obtaining the exact number of unique displays while keeping the order in mind, making it feasible for quick assessments.

--