2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – John Habert Jan 30 '14 at 17:51
  • $\begingroup$ There usually are no such partitions. Just take $q=2$, $n=2$ and $X=2^n$. $\endgroup$ – Olivier Bégassat Jan 30 '14 at 17:51
  • 2
    $\begingroup$ You might find this helpful: en.wikipedia.org/wiki/Composition_(combinatorics) $\endgroup$ – Newb Jan 30 '14 at 17:52
  • $\begingroup$ Olivier: my bad; n(q-1) is what I meant. $\endgroup$ – Charles Fu Jan 30 '14 at 17:53
  • $\begingroup$ Newb: exactly what I needed; thanks! $\endgroup$ – Charles Fu Jan 30 '14 at 17:57
1
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ Sorry I should have mentioned that I was looking for the closed form. $\endgroup$ – Charles Fu Jan 31 '14 at 1:46
0
$\begingroup$

Turned out "Composition" (en.wikipedia.org/wiki/Composition_(combinatorics)) is the name of the concept I was looking for. Thanks to Newb for pointing it out to me.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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