Lesson 4

Arrangements without repetitions. Recall that a \(k\)-permutation of a set is a sequence of \(k\) elements from that set. If the original set has \(n\) elements, then there are \[n(n-1)\dotsb(n-k+1)=\frac{n!}{(n-k)!}\ .\] Indeed, the first element can be chosen in \(n\) ways, the second in \((n-1)\) ways, the third in \((n-2)\) ways, and so on. \(k\)-permutations are also known as arrangements without repetitions: these are words of length \(k\) in an \(n\)-symbol alphabet, where symbols do not repeat; these are ways to distribute \(k\) distinct balls into \(n\) distinct boxes, where no box contains more than one ball.