Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

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 (x1,,xn), where xi indicates the number of repetitions of the i-th object in the selection. Evidently x1++xn=k. If we write this in unary representation, we get a sequence with k ones and n1 plusses. Every such sequence encodes a unique choice and conversely.

  • Answer

    Choices Order matters Order does not matter
    without repetition n!(nk)! \binom{n}{k}
    with repetition n^k \binom{n+k-1}{k}
Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email