In: Advanced Math
What is the number of ordered sequences of length k where each
digit is
taken from a set of size n?
What is the number of ordered sequences of length k where each
digit is
taken from a set of size n without repetition?
What is the number of subsets of size k of a set of size n?
FIRST PART:
There are choices for each of the
places.
Therefore, number of ordered sequences of length where each digit is
taken from a set of size
SECOND PART:
Since repetition is not allowed, the first place has choices, the
second place has
remaining choices,
and so on.
Finally, the last place has
choices.
Therefore, number of ordered sequences of length where each digit is
taken from a set of size
without repetition
THIRD PART:
Finding number of subsets of size is same as finding
number of unordered sequences of length
where each digit is
taken from a set of size
without repetition.
By previous calculations, number of such ordered sequences
But order of elements does not matter in a set.
i.e., for every subset
, any permutation is also the same subset.
There are such permutations
for every set.
So, number of such unordered sequences
i.e., number of subsets of size