## Choice from a set of objects

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.

without repetition $$\frac{n!}{(n-k)!}$$ $$\binom{n}{k}$$
with repetition $$n^k$$ $$\binom{n+k-1}{k}$$