I wonder how to count the number $N_{t,k}$ of terms in the following product (when we expand it as a sum of monomials) where all variables is of degree at least two: $$ \left(\sum_{i=1}^t a_i\right)^k$$
For example, when $t=2$, $k=5$, the answer would be 22: $a_1^5, a_2^5$, ten terms of various permutations of $a_1^2 a_2^3$, and ten other terms equivalent to $a_1^3 a_2^2$.
I know I can write the number of terms as a huge sum using inclusion-exclusion, but that formula is hard to evaluate. If it is hard to calculate the exact number, any ideas on bounding this number will be appreciated too!
It seems like all the terms in $a_1^3a_2^2$ should combine into one. You should just have one term for each power of $a_1$ as $a_2$ then comes with five minus that power, so six terms. You are missing $a_1^4a_2$ and $a_1a_2^4$. If you don't allow the $a$s to commute, it is just $2^5=32$ terms in your example and $t^k$ in general.
Added: You want to expand the product without allowing commutivity between the $a_i$. We want the number of terms where there is not $a_i$ to the power $1$, but power $0$ or higher powers are allowed. If we ignore the restriction of avoiding first powers there are $t^k$ terms, so that is an upper bound.
Let us define $A(t,k)$ as the number of terms in your sum that do not have one variable only once. This is the same as the number of strings of length $k$ from an alphabet of size $t$ that do not have one letter exactly once. A string of $k$ terms that has every letter at least twice can be a string of $k-1$ terms that we add one more letter that matches a previous one, or it can be a string of $k-2$ terms that we put two of a new letter in, one of which goes at the end. Let $B(t,k)$ be the number of strings of length $k$ on $t$ letters where every letter is represented at least twice. Then $$B(t,k)=tB(t,k-1)+(k-1)B(t-1,k-2)$$ because you can start with a string of $t-1$ letters from an alphabet of $k$ and add one or you can start with a string of $t-2$ letters from $k-1$ and add one somewhere and another at then end. Then $$A(t,k)=\sum_{t'=1}^t{t \choose t'}B(t',k)$$ because we just sum over the number of letters that are there weighted by the number of ways to choose the letters represented from our alphabet.