Sum of coefficients of high degree terms in multivariate polynomial expansion

Question

I want to expand the following multivariate polinomial $$\left(\sum_{i=1}^{m} x_i\right)^{n}$$ where $m\geq n$ are both integers. For a fixed integer $k\in\{1,...,m\}$, how to find the sum of coefficients of (Note: original post asks for the number of) terms in the expansion such that (1) has $k$ unique $x_i$'s and (2) each $x_i$ has at least power 2?

For example, if $m=2$ and $n=4$, then $$ (x_1+x_2)^4 =x_1^4 + 4x_1^3x_2 + 6x_1^2x_2^2 + 4x_1x_2^3 + x_2^4. $$ So let's say I want the coefficients for the term with two distinct $x$'s, i.e., $k=2$, I want to be able to calculate the value $6$ for the term $6x_1x_2$.

As a second example, if $m=2$ and $n=6$, then $$ (x_1+x_2)^6 =x_1^6 + 6x_1^5x_2 + 15x_1^4x_2^2 + 20x_1^3x_2^3 + 15x_1^2x_2^4 + 6x_1x_2^5 + x_2^6 $$

For $(x_1+x_2)^6$ and $k=2$, I want to calculate the sum of coefficients for all the terms with $x_1^4x_2^2$, $x_1^3x_2^3$, and $x_1^2x_2^4$, so that's $15+20+15=50$.

Here are my thoughts: For a fixed integer $k$, the terms I am interested in has the form $$ x_{q_1}^{p_1}...x_{q_k}^{p_k} $$ where the $q$'s are unique and (1) $p_1+...+p_k=n$ and (2) $p_1,...,p_k\geq 2$. This is a combinatorial problem but I don't quite know if there is a solution to it. I know that the number of non-negative integral solutions to (1) only is $n+k-1 \choose k-1$, but not quite sure how to incorporate the constraint (2).

Any help is highly appreciated! Thanks in advance.

Answer 1

I don't think your solution is correct, even without constraint $(2)$. Notice that $m$ never appears in it. I would say first that there are ${m\choose k}$ ways of determining which $k$ variables will appear, so that you have to multiply by ${m\choose k},$ but even this is not enough. When you use stars and bars, you aren't enforcing the requirement that $p_i>0$.

For the actual problem, there are ${m\choose k}$ ways to choose the variables that will appear. Then we must make the exponent of each of these equal to $2$ which leaves $n-2k$ exponents remaining to distribute among the $k$ variables. By stars and bars, we can do this in ${n-2k+k-1\choose k-1}={n-k-1\choose k-1}$ ways so the answer is $$ {m\choose k}{n-k-1\choose k-1}$$

Answer 2

Note that by using the transformation $q_i=p_i-2$, the question is equivalent to find $q_1,q_2,\ldots, q_n$ such that (1) $\sum_{i=1}^k q_i=n-2k$ and (2) $q_i\geq 0$. Thus, the number of solutions for this problem equal to $ {n-2k+k-1 \choose k-1}= {n-k-1 \choose k-1}$. Of course, you need to select $k \choose m$ to choose which $x_i$-'s will have a power of two, and thus the answer is

$$ {m \choose k} \cdot {n-k-1 \choose k-1}$$