How many ways are there of choosing $k$ distinct items from a set of $n$?

Question

Specifically, say I have the integers $1,2,3,\dots,n$ (a set of $n$ integers). I want to select numbers one after another (not at the same time) until I have $k$ distinct numbers. How many ways are there of doing this? Someone told me $nPk$ but I don't understand why. Is there another way to approach it?

Answer 1

For the first integer, you have $n$ possibilities to choose, for the second, $n-1$ and so on. So the number of possibilities is $n(n-1)(n-2)...(n-k+1)$, which is the same as $\frac{n!}{(n-k)!}\ =\ nPk$

Answer 2

From $n$ distinct elements we can choose $k$-elements in $\binom{n}{k}$ ways and after permuting them in $k!$ ways we get that there exists $$\binom{n}{k}k!=\frac{n!}{k!(n-k)!}k!=\frac{n!}{(n-k)!}$$ possibilities

Answer 3

http://en.wikipedia.org/wiki/Binomial_coefficient

Please, someone change tag to combinatorics. Additive combinatorics is not about that.