Number of A Subset of Monomials - MathOverflow

Number of A Subset of Monomials

2010-06-09T14:59:14Z

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

Answer by Steve Huntsman for Number of A Subset of Monomials

2010-06-09T15:32:56Z

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.

Answer by Diego Matessi for Number of A Subset of Monomials

2010-06-09T16:58:20Z

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.

Answer by Chris Phan for Number of A Subset of Monomials

2010-06-09T17:54:26Z

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

Answer by Vladimir Dotsenko for Number of A Subset of Monomials

2010-06-09T20:15:44Z

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

Answer by Tom Church for Number of A Subset of Monomials

2010-06-09T23:10:36Z

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

Answer by Vladimir Dotsenko for Number of A Subset of Monomials

2010-06-10T12:28:43Z

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