Lesson 9

Let \(n_{1}, n_{2}, \dotsc, n_{t} \in \mathbb{Z}_{\ge 0}\). The polynomial (or multinomial) coefficient \[\binom{n_1+n_2+\dotsb+n_t}{n_1, n_2, \dotsc, n_t}\] is defined as the coefficient of \(x_{1}^{n_1}x_{2}^{n_2}\dotsb x_{t}^{n_t}\) in the polynomial \((x_{1}+x_{2}+\dotsb+x_{t})^{n}\), where \(n=n_{1}+n_{2}+\dotsb+n_{t}\):

\[(x_{1}+x_{2}+\dotsb+x_{t})^{n}=\sum\limits_{\substack{n_1, n_2, \dotsc, n_t \in \mathbb{Z}_{\ge 0} \colon \\n_1+n_2+\dotsb+n_t=n}}\binom{n_1+n_2+\dotsb+n_t}{n_1, n_2, \dotsc, n_t}x_{1}^{n_1}x_{2}^{n_2}\dotsb x_{t}^{n_t}\ .\]

Polynomial coefficients satisfy the formula generalizing \(\binom{n}{k}=\frac{n!}{k!(n-k)!}\): \[\binom{n_1+n_2+\dotsb+n_t}{n_1, n_2, \dotsc, n_t}=\frac{(n_1+n_2+\dotsb+n_t)!}{n_1!n_2!\dotsb n_t!}\ .\] It is easy to see that this coefficient equals the number of ways to split an \(n\)-element set into \(t\) parts of sizes \(n_{1}, n_{2}, \dotsc, n_{t}\) (the order of the parts matters): the coefficient of the monomial \(x_{1}^{n_1}x_{2}^{n_2}\dotsb x_{t}^{n_t}\) is the number of ways to divide our \(n\) multiplicands into parts of the required size (from the first part, we choose \(x_{1}\), from the second — \(x_{2}\), and so on). And, of course, it is also equal to the number of words of length \(n\) in the alphabet \(\{1, 2, \dotsc, t\}\), where exactly \(n_{1}\) positions contain the digit one, \(n_{2}\) positions — the digit two, and so on. All these words are called permutations with repetitions.