Number of A Subset of Monomials I need to count the number of monomials of degree $n$ in $k$ variables, $x_1,\ldots ,x_k$, that contain at least one variable with a power of 1.  The monomials need not include all the variables.  Their powers just need to some to $n$ and they must be divisible by $x_i$, but not $x_i^2$, for some $i$.
 A: Let $S_i$ be the set of monic monomials $m \in \mathbb{Z}[x_1, \dots,
x_k]$ which are divisible by $x_i$ but not $x_i^2$. If I am reading
your question correctly, you are looking for $|S_1 \cup \cdots \cup
S_k|$.
Note that for $1 \leq i_1 < \dots < i_m \leq k$, the intersection
$S_{i_1} \cap \cdots \cap S_{i_m}$ is the set of monomials of degree
$n$ divisible by $x_{i_1} \cdots x_{i_m}$ but not by $x^2_{i_1} \cdots
x^2_{i_m}$. If $m < n$ and $m < k$, then there is a bijection between
$S_{i_1} \cap \cdots \cap S_{i_m}$ and the set of monic monomials of
degree $n-m$ in $\mathbb{Z}[x_1, \dots, x_{k-m}]$. (If $m = n \leq k$,
then the intersection has one element, $x_{i_1} \cdots x_{i_m}$. In
any other case, the intersection is empty.) Hence, for $1 \leq i_1 <
\cdots < i_m \leq k$,
$$|S_{i_1} \cap \cdots \cap S_{i_m}| = \begin{cases} \left(\matrix{n +
k - 2m -1 \cr k - m - 1}\right), & \text{if $m < n$ and $m < k$} \cr
1, & \text{if $m = n \leq k$} \cr 0, & \text{otherwise.}\end{cases}$$
So, by the principle of inclusion-exclusion,
$$|S_1 \cup \cdots \cup S_k| = \sum_{m =1}^{\min(n, k)-1} (-1)^{m-1}
\left(\matrix{k \cr m}\right)\left(\matrix{n + k - 2m - 1 \cr k - m -
1}\right) + (-1)^{n-1} \left(\matrix{k\cr n}\right)a,$$
where $$a = \begin{cases} 1, & \text{if $k \geq n$} \cr 0, &
\text{otherwise.}\end{cases}$$
A: Another formula (almost without alternating signs) can be obtained as a variation of the comment of David Speyer. Namely, for each $S\subset\{1,\ldots,k\}$ we can consider the set of all monomials that depend precisely on all $x_k$ with $k\in S$ and \emph{do not satisfy the property we are studying}. Such a monomial is divisible by $\prod_{k\in S}x_k^2$, so the number of such monomials is $\binom{|S|+n-2|S|-1}{|S|-1}$. The number of choices for $S$ is $\binom{k}{|S|}$, so altogether the number of ``unwanted'' monomials
is $$\sum_{s=1}^{k}\binom{k}{s}\binom{n-s-1}{s-1},$$ 
and the number of monomials you want to compute is
$$\binom{k+n-1}{k-1}-\sum_{s=1}^{k}\binom{k}{s}\binom{n-s-1}{s-1}.$$ 
A: Let $A_\ell$ be the number of monomials of degree $n$ on $\ell$ variables, which involve all $\ell$ variables and satisfy the condition (this will necessarily be 0 for $\ell>n$). The number of monomials involving all $\ell$ variables is $\binom{n-1}{\ell-1}$ by stars-and-bars. The number of monomials involving all $\ell$ variables at least twice (the invalid monomials), dividing by $x_1\cdots x_\ell$, is $\binom{n-\ell-1}{\ell-1}$. Thus $A_\ell=\binom{n-1}{\ell-1}-\binom{n-\ell-1}{\ell-1}$.
Each monomial is supported on a unique subset of the variables. For a fixed subset of size $\ell$, the monomials supported there are counted by $A_\ell$. There are $\binom{k}{\ell}$ subsets of size $\ell$. So if $N_k$ is the answer to the problem, I believe we have the formula
$$N_k=\sum_{0\leq \ell\leq k} A_\ell \binom{k}{\ell}=\sum_{0\leq \ell\leq k}\binom{n-1}{\ell-1}\binom{k}{\ell}-\binom{n-\ell-1}{\ell-1}\binom{k}{\ell}$$ $$=\binom{n+k-1}{n}-\sum_{0\leq \ell\leq k}\binom{n-\ell-1}{\ell-1}\binom{k}{\ell}$$
[Edit: I now see that this argument was already given by Vladimir Dotsenko. There seems to be some disagreement about his answer though, so I will leave this here as independent confirmation.]
A: It just crossed my mind that there is another way to compute the cardinality of the complement (and I decided to post it as well to demonstrate the power of generating functions): it is the coefficient of $t^n$ in 
$$\left(1+\sum_{p\ge 2}t^p\right)^k=\left(1+\frac{t^2}{1-t}\right)^k=\left(\frac{1-t+t^2}{1-t}\right)^k=\left(\frac{1+t^3}{1-t^2}\right)^k.$$
The latter is equal to
 $$
\sum_{i=0}^k\binom{k}{i}t^{3i}\sum_{l\ge0}\binom{k+l-1}{k-1}t^{2l},
 $$
so the number of ``unwanted monomials'' is
 $$
\sum_{\substack{0\le i\le k, \\ 2l+3i=n}}\binom{k}{i}\binom{k+l-1}{k-1}=
\sum_{\substack{l\ge 0,\\ 3\mid(n-2l)}}\binom{k}{\frac{n-2l}{3}}\binom{k+l-1}{k-1}
 $$
(if we adopt the convention I mentioned in a comment here that $\binom{p}{q}$ is nonzero only for $0\le q\le p$),
and the number in question is 
 $$
\binom{k+n-1}{k-1}-\sum_{\substack{l\ge 0,\\ 3\mid(n-2l)}}\binom{k}{\frac{n-2l}{3}}\binom{k+l-1}{k-1}.
 $$
A funny consequence of that is an otherwise weird identity
 $$
\sum_{\substack{l\ge 0,\\ 3\mid(n-2l)}}\binom{k}{\frac{n-2l}{3}}\binom{k+l-1}{k-1}=\sum_{s=1}^{k}\binom{k}{s}\binom{n-s-1}{s-1}
 $$
A: Isn't it k times the number of monomials of degree n-1 in k-1 variables? Since in such a monomial you have x_j followed by a degree n-1 monomial in the other variables. 
For the number of monomials of degree n-1 in k-1 variables you can check Wikipedia, search for "monomials". 
.... i just realised this is wrong! for example $x_1 x_2^4 x_3$ would be counted twice in the 
way i said.
