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$.
6 Answers
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+n2S1}{S1}$. 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{ns1}{s1},$$ and the number of monomials you want to compute is $$\binom{k+n1}{k1}\sum_{s=1}^{k}\binom{k}{s}\binom{ns1}{s1}.$$

$\begingroup$ I don't know how to make sense of this if $k > n$. $\endgroup$ Commented Jun 9, 2010 at 22:12

2$\begingroup$ Well, the convention I would definitely like to follow is $\binom{p}{q}\ne 0$ only for $0\le q\le p$, and in this case is given by the usual formula. $\endgroup$ Commented Jun 9, 2010 at 22:55

1$\begingroup$ OK, this looks good: for $k=4$ and $n=3$ this gives $\binom{6}{3}\binom{4}{1}\binom{1}{1}\binom{4}{2}\binom{0}{1}\binom{4}{3}\binom{1}{2}\binom{4}{4}\binom{2}{3}$, which would be interpreted as $\binom{6}{3}\binom{4}{1}\binom{1}{1} = 204 = 16$, which checks out. $\endgroup$ Commented Jun 9, 2010 at 23:20

$\begingroup$ Also I guess this is the same convention as Knuth and "A=B" use... $\endgroup$ Commented Jun 9, 2010 at 23:23

1$\begingroup$ Equivalently, replace the upper limit of summation with $\min(k, \lfloor n/2\rfloor)$. $\endgroup$– JBLCommented Jun 9, 2010 at 23:58
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 $nm$ in $\mathbb{Z}[x_1, \dots, x_{km}]$. (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 inclusionexclusion, $$S_1 \cup \cdots \cup S_k = \sum_{m =1}^{\min(n, k)1} (1)^{m1} \left(\matrix{k \cr m}\right)\left(\matrix{n + k  2m  1 \cr k  m  1}\right) + (1)^{n1} \left(\matrix{k\cr n}\right)a,$$ where $$a = \begin{cases} 1, & \text{if $k \geq n$} \cr 0, & \text{otherwise.}\end{cases}$$

$\begingroup$ Not sure if I'm missing something, but the output of the following matches my protoanswer in quite a few, but certainly not all places: for n=1:8,for k=1:9,temp=0;for m=1:(min(k,n)1),temp=temp+((1)^(m1))*nchoosek(k,m)*nchoosek(n+k2*m1,km1);end,L2(k,n)=temp+(k>=n)*(1)^n;end,end,L2 $\endgroup$ Commented Jun 9, 2010 at 18:33

$\begingroup$ In particular, it gives 27 for n=k=4, whereas my table and visual inspection suggests that the proper value is 25. Other values differ by more than 2, so it's not the last term that causes this. $\endgroup$ Commented Jun 9, 2010 at 18:41

$\begingroup$ But above the diagonal, the outputs of both commands agree... $\endgroup$ Commented Jun 9, 2010 at 18:42

1$\begingroup$ I had forgotten a binomial coefficient! Should be correct, now. $\endgroup$– PersonXCommented Jun 9, 2010 at 19:26

1$\begingroup$ I get 16: The $m=1$ term is: ${4 \choose 1} {4 \choose 2} = 24$. The $m=2$ term is: ${4 \choose 2} {2 \choose 1} = 12$. The last term (as $k \geq n$) is: ${4 \choose 3} = 4$. We have $24  12 + 4 = 16$. $\endgroup$– PersonXCommented Jun 10, 2010 at 11:09
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{n1}{\ell1}$ by starsandbars. The number of monomials involving all $\ell$ variables at least twice (the invalid monomials), dividing by $x_1\cdots x_\ell$, is $\binom{n\ell1}{\ell1}$. Thus $A_\ell=\binom{n1}{\ell1}\binom{n\ell1}{\ell1}$.
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{n1}{\ell1}\binom{k}{\ell}\binom{n\ell1}{\ell1}\binom{k}{\ell}$$ $$=\binom{n+k1}{n}\sum_{0\leq \ell\leq k}\binom{n\ell1}{\ell1}\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.]

1$\begingroup$ I have a feeling that the disagreement might come from the fact that computer software systems, being fed this formula for $k=n$, encounter the summand $\binom{1}{k1}$ which they evaluate as $(1)^{k1}$ (which is not what you and me assume), hence the discrepancy. $\endgroup$ Commented Jun 9, 2010 at 23:20

1$\begingroup$ For example, Mathematica evaluates a lot of binomial coefficients that in your sum are meant to be 0. On can rectify this by replacing the upper limit of summation with something like $\min(k, \lfloor n/2\rfloor)$. $\endgroup$– JBLCommented Jun 9, 2010 at 23:58
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}{1t}\right)^k=\left(\frac{1t+t^2}{1t}\right)^k=\left(\frac{1+t^3}{1t^2}\right)^k.$$ The latter is equal to $$ \sum_{i=0}^k\binom{k}{i}t^{3i}\sum_{l\ge0}\binom{k+l1}{k1}t^{2l}, $$ so the number of ``unwanted monomials'' is $$ \sum_{\substack{0\le i\le k, \\ 2l+3i=n}}\binom{k}{i}\binom{k+l1}{k1}= \sum_{\substack{l\ge 0,\\ 3\mid(n2l)}}\binom{k}{\frac{n2l}{3}}\binom{k+l1}{k1} $$ (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+n1}{k1}\sum_{\substack{l\ge 0,\\ 3\mid(n2l)}}\binom{k}{\frac{n2l}{3}}\binom{k+l1}{k1}. $$
A funny consequence of that is an otherwise weird identity $$ \sum_{\substack{l\ge 0,\\ 3\mid(n2l)}}\binom{k}{\frac{n2l}{3}}\binom{k+l1}{k1}=\sum_{s=1}^{k}\binom{k}{s}\binom{ns1}{s1} $$
Chris Phan's comment sounds right to me, but you may be able to do this more quickly, though OEIS doesn't seem to have any details on rows or columns of the below array except that they're (at least often) multinomial coefficients. I have computed these numbers in MATLAB using this stuff:
for n=1:8,for k=1:9,L=lookup(k,n);L1(k,n)=sum(sum((L==1),2)>0);end,end,L1
L1 =
1 0 0 0 0 0 0 0
2 1 2 2 2 2 2 2
3 3 7 9 12 15 18 21
4 6 16 25 40 58 80 106
5 10 30 55 101 165 255 375
6 15 50 105 216 391 666 1071
7 21 77 182 413 819 1520 2646
8 28 112 294 728 1568 3144 5881
9 36 156 450 1206 2802 6030 12051
As an example, consider k=4 and n=3: MATLAB gives (I have added asterices for clarity)
lookup(4,3)
ans =
0 0 0 3
0 0 1 2 *
0 0 2 1 *
0 0 3 0
0 1 0 2 *
0 1 1 1 *
0 1 2 0 *
0 2 0 1 *
0 2 1 0 *
0 3 0 0
1 0 0 2 *
1 0 1 1 *
1 0 2 0 *
1 1 0 1 *
1 1 1 0 *
1 2 0 0 *
2 0 0 1 *
2 0 1 0 *
2 1 0 0 *
3 0 0 0
and visual inspection shows that the number of rows with at least one unit entry is 16, identical with the table entry.

$\begingroup$ This table is very close but not quite the same as Vladimir's formula above. For instance, for n=7, k=6 both give 666, but for n=7, k=7 we have 1519 vs 1520. What's up? $\endgroup$ Commented Jun 9, 2010 at 21:52

$\begingroup$ I don't know...Here is why I believe my table to give the exact answer: the function "lookup" returns a lexicographically rowordered array of multiindices with $k$ components and weight/degree $n$. The blurb "sum(sum((L==1),2)>0)" can be decomposed as follows: "(L==1)" returns the array of the same size as L, with ones where L equals unity and zeros elsewhere. "sum((L==1),2)" sums this array over the rows, returning a column whose nonzero entries are those multiindices have at least one unit entry. "sum(sum((L==1),2)>0)" therefore returns the total number of such nonzero entries. $\endgroup$ Commented Jun 9, 2010 at 22:00

1$\begingroup$ @Pietro: I believe my formula gives 1520 as well: $17167\cdot 121\cdot 435\cdot3=1520$. $\endgroup$ Commented Jun 9, 2010 at 22:52

2$\begingroup$ oh I see: for n=k=7 in your sum Maple counts a last term, for s=7, binomial(1,6)=1, while we humans agree it's zero, or in any case not in the sum :) $\endgroup$ Commented Jun 10, 2010 at 7:24
Isn't it k times the number of monomials of degree n1 in k1 variables? Since in such a monomial you have x_j followed by a degree n1 monomial in the other variables.
For the number of monomials of degree n1 in k1 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.
$(x_1 \cdots x_k)$
but not$(x_1 \cdots x_k)^2$
. So just take the number of degree $nk$ monomials and subtract off the number of degree $n2k$ monomials $\endgroup$