# Partition of integer with size constraint

A rather straightforward combinatorial question:

Given numbers $X, q, n$ such that $0 \leq X \leq n(q-1)$, what are the total number of ways to express $X$ as sum of $n$ numbers, where each summand is between $0$ and $q-1$ and the order does matter (e.g. $1+2$ and $2+1$ are considered different)?

I'd assume that there is an established formula for this but I couldn't find it via Google. If someone can give me a pointer to the result it would be much appreciated.

Thanks!

• You might try starting with this. Order doesn't matter there plus there is not extra limit to the numbers you can use like you have but it is a starting point. – John Habert Jan 30 '14 at 17:51
• There usually are no such partitions. Just take $q=2$, $n=2$ and $X=2^n$. – Olivier Bégassat Jan 30 '14 at 17:51
• You might find this helpful: en.wikipedia.org/wiki/Composition_(combinatorics) – Newb Jan 30 '14 at 17:52
• Olivier: my bad; n(q-1) is what I meant. – Charles Fu Jan 30 '14 at 17:53
• Newb: exactly what I needed; thanks! – Charles Fu Jan 30 '14 at 17:57

You can form a recurrence. Add $1$ to all the summands to get rid of the zeros. Now we want the number of compositions of $X+n$ into $n$ parts of maximum size $q$. Let $N(X+n,n)$ be the desired number of compositions of $X+n$ into $n$ parts of size at most $q$. Then $$N(i,n)=\begin {cases} 0 & i \lt n\\ 1& i=n\\ \sum_{j=1}^q N(i-j,n-1) & i \gt n\end {cases}$$