Not a homework question, promise. I'm studying for the LSATs (the Law School Admissions Test), which has a section of logic games that are basically set-covering / mapping problems. They're not designed to be solved completely, and instead rely on you making quick deductions to limit the number of possibilities to answer a multiple choice question about a particular contingency.

Very frequently, a problem will be set up along the lines of: "Exactly six piano classes are given sequentially, in which nine students are taught," and you'll have to sort out the possible sequences of students, keeping in mind that some students may be taught simultaneously. This therefore gives rise to a number of possibilities, among them:

  • 1 class contains 4 students and 5 classes contain 1 student. (4-1-1-1-1-1)
  • 1 class contains 3 students, 1 class contains 2 students, and the rest contain 1 student (3-2-1-1-1-1), etc.

It would be nice to be able to calculate exactly how many options exist without having to count them by hand. It seems like the best way to formulate the problem is:

How many unique ways are there to express a whole number n as the sum of m nonzero whole numbers?

I'm not a math student, and I could be tagging this incorrectly. I'd appreciate any help in solving the problem, or pointers to similar problems that may have already been posted.

Thanks, Aaron


closed as off topic by Steve Huntsman, Qiaochu Yuan, Sergei Ivanov, Victor Protsak, Gjergji Zaimi Sep 19 '10 at 21:50

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ [deleted earlier, over-hasty comment] $\endgroup$ – Yemon Choi Sep 19 '10 at 21:07
  • 5
    $\begingroup$ This question is not quite at the right level for MathOverflow. You would have better luck asking it at math.stackexchange.com. $\endgroup$ – Qiaochu Yuan Sep 19 '10 at 21:22
  • 3
    $\begingroup$ I agree with Qiaochu, but this is unusually well-presented. First, your emphasized question (how many ways to partition a number into a sum of m numbers) is relatively complex (en.wikipedia.org/wiki/Partition_%28number_theory%29). This isn't really what you're asking, because presumably the order matters in your question. In that case, you're asking how to place 5 partitions among 9 students: .|...|.|.|.|.. represents 1,3,1,1,1,2. There are 9 choose 5 ways to do this. Read en.wikipedia.org/wiki/Binomial_coefficient and you will have your answer. $\endgroup$ – Eric Tressler Sep 19 '10 at 21:53
  • 1
    $\begingroup$ P.S. I infer that order matters because of the term "sequentially" and the fact that I've seen LSATs before, and the easier question seems more appropriate. 9 choose 5 is (9!)/(5!4!) = 126, so if that's not the answer given, I've misinterpreted you. $\endgroup$ – Eric Tressler Sep 19 '10 at 21:53
  • 1
    $\begingroup$ Thanks for the pointers -- I'll read up a little more on integer partitions before I repost the question at stackexchange. That said, in my question order does NOT matter -- ie, [1-1-3] == [3-1-1]. That's what makes this slightly different than a binomial coefficient. As usual, it seems like knowing the name of the problem category is a good first start! $\endgroup$ – awenner Sep 19 '10 at 23:46