Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How many unique ordered lists of $N$ integers - $(q_1, ..., q_N)$ - can I form if $q_i \in [0, M]$, and we have the restriction that $\sum_{i=0}^{N} q_i \geq k$?

share|cite|improve this question
What is $Q$? Perhaps that should be removed, as well as "possible unique". – leonbloy Dec 24 '12 at 13:41
@leonbloy Q is an ordered set of integers, for example, when N=3, we have: {q1, q2, q3}. – TLi Dec 24 '12 at 13:42
@leonbloy I have made the requested changes. Hopefully this should be better? – TLi Dec 24 '12 at 13:45
Ok. Two more clarifications: the order must be strict? (no equal integers? in this case the problem could be stated in combinatoric terms). Second: the notation $q_i \in [0, M]$ is equivalent to $q_i= 0, 1\cdots M$? – leonbloy Dec 24 '12 at 13:48
@leonbloy Integers may be equal, however {10, 5} must be counted as distinct from {5, 10}, for example. Yes, regarding the second point. – TLi Dec 24 '12 at 13:51

The number of such lists is the sum of the coefficients of $x^r$ for $r \ge k$ in the expansion of $$(1+x+...+x^M)^N.$$ There may be a clever way to extract the given sum of coefficients, but I don't see it. Anyway if you have a specific case to calculate, and can use maple or other CAS, the count can be found; maple for example has a function to extract a coeffient of a power of $x$ from an expanded polynomial, and one could code up a function to sum those for $r\ge k$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.