6
$\begingroup$

Let $D,n,d$ be three positive integers.

I am looking for the number of monomials of degree $D$ in $n$ variables where each variable appears with exponent at most $d$.

As a result of an application of inclusion/exclusion principle I found the following expression \begin{equation*} \sum_j (-1)^j \binom{n}{j} \binom{D-j(d+1)+(n-1)}{n-1} \end{equation*} where the summation runs over a set of indices where the expression makes sense: $0\leq j\leq n$, $j \leq D/(d+1)$.

However, I am looking for a more tractable formula, if there exists one.

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
3
$\begingroup$

What does "tractable mean"? You are looking for the coefficient of $x^D$ in

$$\left(\sum_{i=0}^d x^i\right)^n = \left(\frac{1-x^{d+1}}{1-x}\right)^n,$$ I believe the RHS gives something like the formula you wrote down...

Improve this answer
$\endgroup$
1
  • $\begingroup$ I am not sure of what I mean as tractable. This number comes up in a more general context and in this form I am not able to work with it; I was hoping maybe that the summation could have a more concise form. $\endgroup$
    – fulges
    Commented Oct 28, 2014 at 4:53
2
$\begingroup$

This formula has no closed form. That means it can not be written as a sum of fixed number of hypergeometric terms when $d$ is greater than $2$. The proof can be found in the book A=B by Petkovsek, Wilf and Zeilberger.

Improve this answer
$\endgroup$
0
$\begingroup$

Expanding on Igor's answer, if you search for "discrete uniform distribution" you will find lots of articles on it. For example this.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .