Choice from a set of objects
Task number: 3448
We choose \(k\) objects from a set of \(n\). Fill the number of possible choices into the following table:
| Choices | Order matters | Order does not matter |
|---|---|---|
| without repetition | ||
| with repetition |
Solution
If order matters, we can describe our choice as a mapping \(f\), where \(f(i)\) indicates the object selected in the \(i\)-th round. So we have a mapping from the set of sequence numbers \(\{1,…,k\}\) to the set of objects.
If objects may not be repeated, we must have an injective mapping. If they may be repeated, any mapping is possible.
If order does not matter and objects may not be repeated, we choose a \(k\)-element set from an \(n\)-element set.
If objects may be repeated, we write our choice as an \(n\)-tuple \((x_1,…,x_n)\), where \(x_i\) indicates the number of repetitions of the \(i\)-th object in the selection. Evidently \(x_1+… +x_n=k\). If we write this in unary representation, we get a sequence with \(k\) ones and \(n-1\) plusses. Every such sequence encodes a unique choice and conversely.
Answer
Choices Order matters Order does not matter without repetition \(\frac{n!}{(n-k)!}\) \(\binom{n}{k}\) with repetition \(n^k\) \(\binom{n+k-1}{k}\)
