11.6. Unordered Selection of k Elements

Now, we can define $C(n, k)$ as an unordered selection of $k$ elements from a set, and each such unordered selection is called an $k$-combination. This means if I am now selecting 2 objects out of 3 objects, then it does not matter whether I pick object 1 before object 2 or whether I pick object 2 before object 1. The arrangement $(x_1, x_2)$ will be considered the same regardless of the order.

In this chunk, we introduce the concept of combinations, focusing on the fact that the order of selection does not matter. When we talk about $C(n, k)$, we refer to the number of ways to choose $k$ elements from a total of $n$ elements without considering the arrangement. This is crucial because in practical scenarios, the order might not be significant; for example, choosing toppings for a pizza where 'cheese and pepperoni' is the same as 'pepperoni and cheese'.

Imagine you're at an ice cream shop with three flavors: chocolate, vanilla, and strawberry. If you can choose two scoops and you're asked to get a mix, what matters is the combination of flavors you pick, not the order. So choosing chocolate with vanilla is the same as vanilla with chocolate. This illustrates the definition of combinations.

We usually denote this function as $C(n, k)$. The number of combinations is given by the formula $C(n, k) = \frac{n!}{k! (n-k)!}$. This expresses the total number of ways to choose $k$ objects from $n$ distinct objects.

The formula for combinations, $C(n, k) = \frac{n!}{k! (n-k)!}$, breaks down as follows: $n!$ is the factorial of the total elements, which represents all possible arrangements; however, since order does not matter, we divide by $k!$ (the arrangements of the chosen items) and $(n-k)!$ (the arrangements of the non-chosen items). This effectively counts each grouping of items exactly once, providing a more accurate total count of combinations.

Consider you have 5 types of fruit and you want to pick 2. If we think of each fruit type as a unique item (like apples, bananas, strawberries, oranges, and grapes), calculating combinations gives us the number of unique pairs (like apple-banana or banana-apple would be the same pair). Using our formula, if 5 is $n$ and you want to choose 2, you can compute it as $C(5, 2) = \frac{5!}{2!(5-2)!} = 10$. So, there are 10 unique pairs of fruits you can choose.

The relationship between the permutation function $P(n, k)$ and the combination function $C(n, k)$ can be expressed as $P(n, k) = C(n, k) \cdot k!$. This means that the total number of ways to arrange $k$ elements from a set of $n$ is the product of the number of ways to choose the elements and the number of ways to arrange these elements.

This relationship helps us understand that while combinations account for the selection of items without regard to order, permutations consider the order. By multiplying the number of combinations by $k!$ (the number of ways we can arrange these $k$ selected elements), we derive how many unique arrays can be formed from our selection, always accommodating both selection and arrangement.

Return to the ice cream example. If you choose 2 flavors but also want to arrange them in a cone, the initial selection (combinations) is just about picking flavors (like chocolate and vanilla), while permutations will explain how many unique ways to stack those two flavors in a cone (chocolate on top or vanilla on top). Thus, if you had 5 flavors and want to choose 2, then arrange them, you'd use this combinatorial relationship to find out all possibilities.

--