Number of A Subset of Monomials - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T20:57:53Z http://mathoverflow.net/feeds/question/27586 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27586/number-of-a-subset-of-monomials Number of A Subset of Monomials Joe Johnson 2010-06-09T14:59:14Z 2010-06-10T12:28:43Z <p>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$.</p> http://mathoverflow.net/questions/27586/number-of-a-subset-of-monomials/27590#27590 Answer by Steve Huntsman for Number of A Subset of Monomials Steve Huntsman 2010-06-09T15:32:56Z 2010-06-09T22:12:03Z <p>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 <a href="http://mathoverflow.net/questions/9477/uniquely-generate-all-permutations-of-three-digits-that-sum-to-a-particular-value/9482#9482" rel="nofollow">this stuff</a>:</p> <blockquote> <blockquote> <p>for n=1:8,for k=1:9,L=lookup(k,n);L1(k,n)=sum(sum((L==1),2)>0);end,end,L1</p> </blockquote> </blockquote> <p>L1 =</p> <pre><code> 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 </code></pre> <hr> <p>As an example, consider k=4 and n=3: MATLAB gives (I have added asterices for clarity)</p> <blockquote> <blockquote> <p>lookup(4,3)</p> </blockquote> </blockquote> <p>ans =</p> <pre><code> 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 </code></pre> <p>and visual inspection shows that the number of rows with at least one unit entry is 16, identical with the table entry.</p> http://mathoverflow.net/questions/27586/number-of-a-subset-of-monomials/27602#27602 Answer by Diego Matessi for Number of A Subset of Monomials Diego Matessi 2010-06-09T16:58:20Z 2010-06-09T17:39:50Z <p>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. </p> <p>For the number of monomials of degree n-1 in k-1 variables you can check Wikipedia, search for "monomials". </p> <p>.... i just realised this is wrong! for example $x_1 x_2^4 x_3$ would be counted twice in the way i said.</p> http://mathoverflow.net/questions/27586/number-of-a-subset-of-monomials/27605#27605 Answer by Chris Phan for Number of A Subset of Monomials Chris Phan 2010-06-09T17:54:26Z 2010-06-09T19:25:40Z <p>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|$.</p> <p>Note that for $1 \leq i_1 &lt; \dots &lt; 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 &lt; n$ and $m &lt; 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 &lt; \cdots &lt; 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), &amp; \text{if m &lt; n and m &lt; k} \cr 1, &amp; \text{if m = n \leq k} \cr 0, &amp; \text{otherwise.}\end{cases}$$</p> <p>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, &amp; \text{if k \geq n} \cr 0, &amp; \text{otherwise.}\end{cases}$$</p> http://mathoverflow.net/questions/27586/number-of-a-subset-of-monomials/27614#27614 Answer by Vladimir Dotsenko for Number of A Subset of Monomials Vladimir Dotsenko 2010-06-09T20:15:44Z 2010-06-09T20:15:44Z <p>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}.$$ </p> http://mathoverflow.net/questions/27586/number-of-a-subset-of-monomials/27623#27623 Answer by Tom Church for Number of A Subset of Monomials Tom Church 2010-06-09T23:10:36Z 2010-06-09T23:16:14Z <p>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}$.</p> <p>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</p> <p>$$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}$$</p> <p>[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.]</p> http://mathoverflow.net/questions/27586/number-of-a-subset-of-monomials/27684#27684 Answer by Vladimir Dotsenko for Number of A Subset of Monomials Vladimir Dotsenko 2010-06-10T12:28:43Z 2010-06-10T12:28:43Z <p>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}.$$</p> <p>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}$$</p>