Number of Laurent monomials of n variables with degree at most d

Question

Introduction: We have a question of how to calculate the number of $n$-variables Laurent monomials of degree at most $d$.

For example: If $n=2$, $d=2$ then we have 19 monomials, which are: $x^{-2}$, $x^{-2}y$, $x^{-2}y^2$, $x^{-1}y^{-1}$, $x^{-1}$, $x^{-1}y$, $x^{-1}y^2$, $y^{-2}$, $y^{-1}$, 1, $y$, $y^{2}$, $xy^{-2}$, $xy^{-1}$, $x$, $xy$, $x^2y^{-2}$, $x^2y^{-1}$, $x^2$. They correspond to the following 19 pairs of powers: $(-2,0)$, $(-2,1)$, $(-2,2)$, $(-1,-1)$, $(-1,0)$, $(-1,1)$, $(-1,2)$, $(0,-2)$, $(0,-1)$, $(0,0)$, $(0,1)$, $(0,2)$, $(1,-2)$, $(1,-1)$, $(1,0)$, $(1,1)$, $(2,-2)$, $(2,-1)$, $(2,0)$.

So how about, e.g., $n=4$, $d=4$ ?

Formulation: Let $n,d\in\mathbb N$. Let \begin{align*} \Omega(n,d) &= \{\alpha\in\mathbb N^n: \alpha_1+\dotsb+\alpha_n \leq d\},\\ \Gamma(n,d) &= \Omega(n,d) + \Omega(n,d),\\ \Delta(n,d) &= \Omega(n,d) - \Omega(n,d). \end{align*} Then, the elements of $\Delta(n,d)$ correspond to the tuples of powers of the monomials.

The cardinality of $\Omega(n,d)$ is well-known to be $\binom{n+d}{n}$. The cardinality of $\Gamma(n,d)$ can be shown to be $\binom{n+2d}{n}$. However, is there a formula to compute the cardinality of $\Delta(n,d)$ ?

Some results: We did some attempts and got that \begin{align*} |\Delta(n,1)| &= n(n+1)+1,\\ |\Delta(1,d)| &= 2d+1,\\ |\Delta(2,d)| &= (2d+1)^2 - d(d+1),\\ |\Delta(3,d)| &= (2d+1)^3 - \frac{7}{3}d(d+1)(2d+1),\\ |\Delta(4,d)| &= (2d+1)^4 - \frac{1}{12}d(d+1)(157d^2+157d+46). \end{align*} We still haven't found a way to calculate $|\Delta(n,d)|$ in general. By definition of $\Delta(n,d)$ as above, I think we may have a geometric approach. An orientable suggestion would be nice.

Answer 1

One such formula is $$\sum_{p=0}^n \binom{n}{p} \binom{d}{p} \binom{d+n-p}{n-p}.$$ To derive this, let $P \subseteq [n]$ be the set of variables with positive exponents and let $p = |P|$. There are $\binom{n}{p}$ ways to choose $P$. After choosing $P$, we must choose a monomial in $\{ x_i \}_{i \in P}$ of degree $\leq d$ where each variable has degree $\geq 1$; there are $\binom{d}{p}$ ways to do this. And we must choose a monomial in $\{ x_i \}_{i \in [n] \setminus P}$ of degree $\leq d$ where each variable has degree $\geq 0$; there are $\binom{d+n-p}{n-p}$ ways to do this. I think this is equivalent to Ira Gessel's formula in the comment below.

My previous answer is preserved below the line:

---

One such formula is $$\sum_{\substack{0 \leq p,q \leq d\\ p+q \leq n}} \binom{n}{p,q} \binom{d}{p} \binom{d}{q}$$ where $\binom{n}{p,q}$ is the trinomial coefficient $\tfrac{n!}{p! q! (n-p-q)!}$.

To see this, let $P$ and $Q \subset [n]$ be the sets of variables whose exponents are positive and negative. To choose a monomial in your set, first choose the index sets $P$ and $Q$, which we can do in $\binom{n}{|P|,|Q|}$ ways. Then choose two monomials, one in the variables $\{ x_i \}_{i \in P}$, and one in the variables $\{ x_j \}_{j \in Q}$, where each variable occurs to degree $\geq 1$ and the total degree is $\leq d$. The number of monomials in $p$ variables where each variable occurs to degree $\geq 1$ and the total degree is $\leq d$ is $\binom{d}{p}$. (Note that this is even correct when $d<p$.)

This isn't a particularly nice formula, but I don't see how to simplify it more. (EDIT: But Ira Gessel did; see his comment below.) Note that it is manifestly a polynomial in $d$, for fixed $n$.