Take the 2-minute tour ×
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.

I'm looking to find a way, for any N, to generate all the combinations (definitely not permutations) of size N, which sum to N-1, involving (including repetition) 0 to N-1, where N >= 3.

For example, for N=2, then a combination (of size 2) of just 0 and 1 that sums to 1. This was pretty simple for me, but I quickly got lost when trying to decide how many were valid for N=3 or N=4, let alone determine an algorithm or formula without just throwing a computer program at the problem and looking at the output and trying to guess one.

I'm quite confident that there are less than N^2, as there are N variables and each one can be 0 to N-1, but since I'm looking for combinations rather than permutations, some are removed. I'm also pretty confident that, at minimum, there's 1 valid combination for every solution, because you could just have 0,0,.... N-1. I'm also pretty sure that distinctly less than half of them are going to be valid, because the other half is easily going to reach over N-1, and plenty of the rest won't get up there, so instinctively, I'm going to say that for any N, it's going to be pretty small, relative to N. But I've no idea how to go about quantifying this.

Any suggestions?]

Edit: Sorry guys- I'm looking both to generate all the combinations, and, implicitly, to know how many there are (it'd be pretty hard to generate them without being able to count them).

Edit some more: OK. I've been looking at the Partition thing, and it's pretty close to what I'm looking for, but I'm still a little shaky on a couple of details.

Firstly, the partition of N is not quite the same as what I'm looking for- the range is from 1 to N, with a target of N, as opposed to 0 to N-1, with a target of N-1, and I'm only interested in partitions with a size of N. I'm thinking that the two should be convertible without too much effort- if I look for the partitions of N-1, and just pad the empty slots with zero, then I should get what I'm looking for- right?

Secondly, the Wiki page listed gives functions for approximating or calculating the number of partitions for any N. Still not completely sure about how I would go about generating the partitions. Looking at the structure of the partitions for 8, for example, it seems like it shouldn't be too difficult. I was thinking about splitting the original target down into two-component composites, e.g., from {7, 1} to {1, 7}. Then, as long as there exists a value on the right which is not 1, recursively break it down, and count as valid all those where they appear in descending sorted order left to right. This seems like it should work- opinions?

share|improve this question
    
Do you know that this is a variant of the knapsack problem? (see en.wikipedia.org/wiki/Knapsack_problem) –  Tim van Beek Jun 4 '11 at 14:03
    
@Tim: The knapsack problem is usually defined as the problem of optimizing a solution or deciding whether a solution is possible, not of counting the number of solutions or generating them all. –  joriki Jun 4 '11 at 14:09
    
At the beginning you say you're looking for a way to generate all the combinations, but the rest of the question sounds more like you want to know how many there are. Which is it, or both? –  joriki Jun 4 '11 at 14:19
    
@joriki: Sorry- I need both. –  DeadMG Jun 4 '11 at 14:23
add comment

1 Answer 1

up vote 1 down vote accepted

If different orders are not counted as different then this is in fact the Partition Function, since any partition of $N-1$ has no more than $N-1$ positive parts and you can use $0$s to fill the gaps. You have to offset, but the sequence starts 1, 1, 2, 3, 5, 7, 11, 15, ...

Added: It is easy enough to calculate the number of partitions and generate them using the R partitions package. For example (adapted for the details of this question)

> library(partitions)
> N <- 8
> P(N-1)
[1] 15
> t(rbind(parts(N-1),0))
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
 [1,]    7    0    0    0    0    0    0    0
 [2,]    6    1    0    0    0    0    0    0
 [3,]    5    2    0    0    0    0    0    0
 [4,]    5    1    1    0    0    0    0    0
 [5,]    4    3    0    0    0    0    0    0
 [6,]    4    2    1    0    0    0    0    0
 [7,]    4    1    1    1    0    0    0    0
 [8,]    3    3    1    0    0    0    0    0
 [9,]    3    2    2    0    0    0    0    0
[10,]    3    2    1    1    0    0    0    0
[11,]    3    1    1    1    1    0    0    0
[12,]    2    2    2    1    0    0    0    0
[13,]    2    2    1    1    1    0    0    0
[14,]    2    1    1    1    1    1    0    0
[15,]    1    1    1    1    1    1    1    0

If you wanted to do this yourself you could use the following algorithm for partitions of $N-1$

  1. put the numbers $1$ to $N-1$ in the first column (so $N-1$ rows initially)
  2. calculate the difference $d$ between $N-1$ and the sum of the numbers in that row
  3. if $d=0$ then fill the rest of the row with $0$s and then STOP for that row
  4. for other rows with $d>0$, replace each row with rows which are identical up to that point but with an extra number from $1$ to the lower of $d$ or the smallest number so far used in that row
  5. return to to 2
share|improve this answer
    
Ah -- that's a lot simpler than my answer :-) –  joriki Jun 4 '11 at 14:18
    
I'm not so sure that this is correct. How can the partitions of N possibly be greater than N^2? –  DeadMG Jun 4 '11 at 14:55
    
@DeadMG: You mean their number? Why shouldn't it be greater than $N^2$? From the question, it seems you believe this follows from there being $N$ variables with $N$ possible values -- but that gives $N^N$ possible combinations. –  joriki Jun 4 '11 at 14:58
    
@joriki: Ok. I see what you mean there- slight brain fart. So for N = 7, say, then there are 7^7 combinations (823543), but only 15 of them sum to 7. –  DeadMG Jun 4 '11 at 15:14
    
@DeadMG: Sorry, I was using "combinations" loosely -- I meant there are $N^N$ possible assignments of the $N$ values to the $N$ variables, but that takes order into account, so fewer "combinations" than that, even without the constraint that they sum to $7$. Another estimate is the number $\left(2N-1\atop N\right)$ of ways of distributing $N$ objects into $N$ bins, which is what you want except it takes order into account. –  joriki Jun 4 '11 at 16:32
add comment

Your Answer

 
discard

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.