11.5. Combinations and Its Relation to Permutations

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 specifically to the arrangement of a set of objects where the order of selection is significant. For instance, if we have two individuals, Person 1 and Person 2, the arrangement 'Person 1 followed by Person 2' is different from 'Person 2 followed by Person 1'. This highlights that the order is crucial in permutations.

Think of a race where runners finish at different times. The order in which they cross the finish line determines their placement (1st, 2nd, and 3rd). This ranking illustrates how permutations are dependent on order.

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

A k-permutation is formulated when selecting 'k' elements from a set of 'n' distinct objects, where 'n' must be equal to or greater than 'k'. The number of ways to arrange these 'k' elements from the set is crucial in combinatorial problems. The notation used for this is P(n, k) or sometimes denoted with factorials.

Imagine you are selecting a committee of 3 members from a group of 5 people. The arrangement matters because different orders of selection (like who speaks first) can lead to different outcomes, making this a real-world example of k-permutations.

So it's easy to see that if I apply the product rule then I can derive the formula P(n, k) = n * (n − 1) * (n − 2)...(n − k + 1).

The formula for calculating k-permutations uses the product rule in counting. You start with 'n' choices for the first position, then 'n-1' choices for the second, and so on until you have placed all 'k' items. It is important that 'k' does not exceed 'n' to avoid negative results in choices.

Consider you are putting together a 3-course meal from a menu with 5 options (appetizers, main dishes, and desserts). For the first course, you have 5 options, for the second course, you have 4 options left, and for the third, you have 3 remaining options. The total combinations can be calculated using the product rule.

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

In contrast to permutations, combinations are selections where the order does not matter. This means that selecting elements from a set can lead to the same group regardless of how the elements were arranged (e.g., choosing members A, B, and C is the same as choosing C, B, and A). The formula for combinations is derived, reflecting this principle.

Think of forming a book club; the selection of books does not change the essence of the club's reading list—choosing 'Book A, Book B, and Book C' is the same as 'Book C, Book B, and Book A'. The order here is irrelevant.

My claim is that P(n, k) = C(n, k) * P(k, k).

This relationship illustrates that the total number of ordered selections of 'k' elements (permutations) can be viewed as first selecting the 'k' elements (combinations) and then ordering them. This links the two concepts, showing that by finding combinations and then arranging those combinations, you can retrieve the full set of permutations.

Consider you have a basket of fruits (apples, bananas, and cherries) and you want to create a fruit salad. First, you select several fruits (combinations), and then you can arrange them in any order within your bowl (permutations), yielding a fresh perspective on how the two concepts work together.

But we will consider the case where even in the selection the repetitions are allowed.

When repetitions in combinations are allowed, the calculation methods change significantly. The permutations and combinations now account for selecting the same item multiple times. The formula for combinations that allow repetition is derived based on this adjusted scope.

Picture a vending machine where you can choose drinks. If you want to select 3 drinks but can choose the same type (like 3 cola cans), this scenario is akin to combinations where repetitions are allowed, differing from cases where each choice must be unique.

--