Number of terms that does not contain single powers in a multivariable binomial expansion

Question

Consider $(x_1+x_2+\dots+x_p)^{r}$. I am looking for the number of terms of type $x_{i_1}^{\alpha_{1}}x_{i_2}^{\alpha_2}\dots x_{i_k}^{\alpha_k}$ in the expansion where $k$ is not fixed and $\alpha_{j}\geq 2$ for each $j\in\{1,2,\dots,k\}$. Any help is appreciated.

Answer 1

Count words of length $r$ on alphabet $\{1,\dots,p\}$ in which no letter appears exactly once. One way to do this is to apply the principle of inclusion-exclusion, where the $p$ properties to be avoided are that letter $j$ appears exactly once: $$\sum_{i=0}^p (-1)^i \binom{p}{i}\binom{r}{i}i!(p-i)^{r-i}$$ Here, $i$ represents the number of properties that are not avoided, $\binom{p}{i}$ selects the $i$ properties, $\binom{r}{i}$ selects the positions of the $i$ letters that appear once, $i!$ permutes them, and $(p-i)^{r-i}$ populates the remaining $r-i$ positions in the word from among the remaining $p-i$ letters.

As a sanity check, the case $(p,r)=(2,4)$ yields $8$, as expected: $$(x_1+x_2)^4 = \color{red}{1}x_1^4 + 4x_1^3 x_2 + \color{red}{6}x_1^2 x_2^2+ 4x_1 x_2^3+ \color{red}{1}x_2^4$$