# Subsets and Sequences

I just want someone to confirm:

to find the number of sequences of length k (without repetitions) from a set of n items the general formula is:

$\frac{n!}{(n-k)!}$

and to find the number of subsets of size k of a set of n items the general formula is:

$\frac{n!}{k!(n-k)!}$

True?

• Both of your statements are true. – corindo Oct 16 '15 at 6:16

Yes that's true. To choose a sequence without repetitions from $S$ with $|S|=n$, for the first entry, we have $n$ possibilities, for the second one $(n-1)$ (as one element has already been choosen and we do not allow repetitions), and so on, finally for the $k$-th entry, we have $(n-k+1)$ possibilities, giving altogether
$$n \cdot (n-1) \cdots (n-k+1) = \frac{n!}{(n-k)!}$$
To count the number of subsets of size $k$, we just compute how many of the sequences correspond to the same subset. As the $k$ elements of the subset can be arranged in $k!$ to give a sequence without repetition, there are $k!$ as many sequences as there are subsets. Hence the number of $k$-subsets of $S$ is
$$\frac 1{k!} \cdot \frac{n!}{(n-k)!} = \frac{n!}{k!(n-k)!} = \binom nk$$