2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Both of your statements are true. $\endgroup$ – corindo Oct 16 '15 at 6:16
4
$\begingroup$

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)!} $$

sequences.

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 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.