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$.

-
Combine the "stars and bars" counting method with the inclusion-exclusion principle. – Chris Phan Jun 9 2010 at 15:30
Easier: this is the number of monomials divisible by $(x_1 \cdots x_k)$ but not $(x_1 \cdots x_k)^2$. So just take the number of degree $n-k$ monomials and subtract off the number of degree $n-2k$ monomials – David Speyer Jun 9 2010 at 15:34
Wait, are we requiring the monomial to be divisible by $x_1 \cdots x_k$? I thought we just wanted the monomial divisible by $x_i$ but not $x_i^2$ for some $i$. – Chris Phan Jun 9 2010 at 15:43
Oh, sorry. I thought all the variables had to be in there, but I guess they don't. At that point, we definitely need to do some inclusion exclusion. – David Speyer Jun 9 2010 at 17:09
I think "stars and bars" is a good term, - I've never heard of it before, but I was able to guess immediately what it was referring to among things I know, and that's a sign of a very good term! – Vladimir Dotsenko Jun 10 2010 at 12:31

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}.$$

-
I don't know how to make sense of this if $k > n$. – Steve Huntsman Jun 9 2010 at 22:12
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. – Vladimir Dotsenko Jun 9 2010 at 22:55
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} = 20-4 = 16$, which checks out. – Steve Huntsman Jun 9 2010 at 23:20
Also I guess this is the same convention as Knuth and "A=B" use... – Steve Huntsman Jun 9 2010 at 23:23
Equivalently, replace the upper limit of summation with $\min(k, \lfloor n/2\rfloor)$. – JBL 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 $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}$$

-
Not sure if I'm missing something, but the output of the following matches my proto-answer 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)^(m-1))*nchoosek(k,m)*nchoosek(n+k-2*m-1,k-m-1);end,L2(k,n)=temp+(k>=n)*(-1)^n;end,end,L2 – Steve Huntsman Jun 9 2010 at 18:33
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. – Steve Huntsman Jun 9 2010 at 18:41
But above the diagonal, the outputs of both commands agree... – Steve Huntsman Jun 9 2010 at 18:42
I had forgotten a binomial coefficient! Should be correct, now. – Chris Phan Jun 9 2010 at 19:26
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$. – Chris Phan 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{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.]

-
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}{k-1}$ which they evaluate as $(-1)^{k-1}$ (which is not what you and me assume), hence the discrepancy. – Vladimir Dotsenko Jun 9 2010 at 23:20
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)$. – JBL 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}{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}$$

-

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.

-
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? – Pietro Majer Jun 9 2010 at 21:52
I don't know...Here is why I believe my table to give the exact answer: the function "lookup" returns a lexicographically row-ordered 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. – Steve Huntsman Jun 9 2010 at 22:00
@Pietro: I believe my formula gives 1520 as well: $1716-7\cdot 1-21\cdot 4-35\cdot3=1520$. – Vladimir Dotsenko Jun 9 2010 at 22:52
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 :-) – Pietro Majer Jun 10 2010 at 7:24

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.

-