Lesson 1

Arrangements with repetitions. The number of sequences (words) of length \(k\) over an alphabet of \(n\) symbols is \(n^{k}\). This follows directly from the multiplication rule: any of the \(n\) symbols can go in the first position, and the same is true for the second, and so on. These combinations are called arrangements with repetitions: in each of the \(k\) positions, we arrange one of the \(n\) symbols, and the same symbol can be reused (i.e., repeated) later. Arrangements with repetitions can also be defined as all ways to distribute \(k\) distinct balls into \(n\) distinct boxes.