1
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ [deleted earlier, over-hasty comment] $\endgroup$
    – Yemon Choi
    Commented Sep 19, 2010 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
    Commented Sep 19, 2010 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
    Commented Sep 19, 2010 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
    Commented Sep 19, 2010 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
    Commented Sep 19, 2010 at 23:46

0

Reset to default

Browse other questions tagged .