Number of A Subset of Monomials

Question

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 1

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 2

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 3

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 4

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

Answer 5

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 6

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.