Lesson 10

Let's prove this formula for words. We need to count the number of words in which exactly \(n_{i}\) positions contain the digit \(i\). Take any such string and write out all \(n!\) permutations of its characters. Among all the resulting words, the required number of characters will be present, but due to repeated characters, each word will appear multiple times. For example, all permutations of the word \(\texttt{121}\) look like this: \[\texttt{ 1\(_{1}\)2\(_{2}\)1\(_{3}\) 1\(_{1}\)1\(_{3}\)2\(_{2}\) 2\(_{2}\)1\(_{1}\)1\(_{3}\) 2\(_{2}\)1\(_{3}\)1\(_{1}\) 1\(_{3}\)2\(_{2}\)1\(_{1}\) 1\(_{3}\)1\(_{1}\)2\(_{2}\) }\] Here, we assign indices to each letter in the original word to distinguish them. If we now forget these indices, all permutations will look like this: \[\texttt{ 121 112 211 211 121 112 }\] It is clear that each word appears multiple times. This will also be true in the general case. How many times does a specific word appear among all \(n!\) permutations? It turns out to be exactly \(n_{1}!n_{2}!\dotsb n_{t}!\) times. Indeed, the symbol 1 can be rearranged in \(n_{1}!\) ways, symbol 2 — in \(n_{2}!\) ways, and so on.