> [!NOTE] Theorem > Let $A$ be a [[Finite Set|finite set]] with [[Cardinality|cardinality]] $n\in\mathbb{N}^{+}.$ Let $k\in\mathbb{N}^{+}$ such that $k\leq n.$ Then the number of [[Partial Permutation of n Letters (Ordered Selection)|k-permutations]] of $A$ is given by ${}^{n} P_{k} = \frac{n!}{(n-k)!}$where $n!$ denotes the $n$th [[Factorial|factorial]]. ###### Proof We pick the elements of $A$ in any arbitrary order. There are $n$ elements of $A$, so there are $n$ options for the first element. Then there are $n-1$ elements left in $A$ that we haven't picked, so there are $n-1$ options for the second element. Then there are $n-2$ elements left, so there are $n-2$ options for the third element. And so on, to the $k$th element of our selection: we now have $n-k+1$ possible choices. By the [[Product Rule for Counting (Fundamental Counting Principle)]], the total number of ordered selections from $A$ is $n(n-1)\cdots (n-r+1) = \frac{n!}{(n-k)!}.$ # Applications See [[Number of Permutations of n Letters]]. **Examples**: > [!Example] > If there are $30$ people in a room, what is the probability of at least two of them to have the same birthday? (Assume that no one is born on February $29$ and that any day has the same chance of being anyone’s birthday). > > Solution: First, we compute the probability that no two people have the same birthday, corresponding to event $B,$ where $B$ is the set of ordered selections of 30 from a set of cardinality $365.$ Thus $\mathbb{P}(B) = \frac{|B|}{|\Omega|}= \frac{365\times \cdots \times (365-30+1)}{365^{30}} \approx 0.29$ A related result is [[Enumerating surjections between finite sets]].