Combinatorics question: shelving books

In a way this is a "help me with my homework" question, except it's not
the solution I'm looking for. I already have that. However, my own
formulation doesn't agree with it, and I want to find out the flaw(s)
in my reasoning. The question goes:

Twenty (20) different books are to be put on five (5) book shelves,
each of which holds at least twenty (20) books.

(a) How many different arrangements are there if you only care
about the number of books on the shelves (and not which books
is where?

(b) How many different arrangements are there if you care about
which books are where but the order of the books on the shelves
doesn't matter?

(c) How many different arrangements are there if the order on the
shelves does matter?

(This is #45 in 3.6 of Brualdi's _Introductory Combinatorics_, 4th ed.,
in case anyone wants to know.)

I have part b covered; I'm interested in part a and part c.

For part a, I imagined that I'd line up all 20 books in no particular
order, partition them into 5 partitions, then fill the book shelves
according to my partitions. The number of ways to partition p objects
in to k non-empty partitions is S(p,k), the Stirling number of the
second kind.

Since I'm not counting the case where the partitions can be empty,
S(20,5) is undercounting. However, S(20,5) is in the order of 10^20,
where as the number of arrangements in the solution is only about ten
thousand.

For part c, I reasoned similarly. There are 20! ways to arrange the
books, and for each arrangement, there are (answer to part a) ways to
partition them. So the answer is 20! * (answer to part a). I'm about
10 orders of magnitude off.

While I know my solutions are wrong, I don't know *why* they're wrong.
Any help is appreciated.

Thanks.

Julian Hsiao
ten.erosinayn@akodam

.

Relevant Pages

  • Re: OT: learning chord melody style
    ... always tended to find Jack's arrangements a bit too left-hand heavy. ... books of pop/broadway/movie standards, ... Guitar" which also seems to be OOP print now (though eBay sometimes has ...
    (rec.music.classical.guitar)
  • Re: Looking for "I Love a Piano" books (I think)
    ... Were there a lot of Shearing and McPartland arrangements? ... > books had a picture of a piano in a concert hall somewhere. ...
    (rec.music.makers.piano)
  • Re: Pop/Rock sing-a-long book recommendations
    ... >with piano only and voice, and have decent piano arrangements. ... Yesterday I bought two of Hal Leonard's Budget Books, ... Some of the Beatles tunes work particularly well. ...
    (rec.music.makers.piano)
  • Re: Best Chord Melody Guitar Books?
    ... fingerstyle solo guitar Howard Morgen has a series that teaches you to ... I think that any of the Galbraith books are gold mines. ... On the other hand Barry's arrangements seem MADE for busting open and doing it your own way if/when you see fit. ... Iconoclasm kills rock. ...
    (rec.music.makers.guitar.jazz)
  • Re: number generator
    ... The number of such partitions, Phas no known exact formula but can be computed inductively rather easily. ... This means that the problem is reduced to permutations (albeit unique permutations) which are a lot simpler to compute than partitions. ... def perm: ... The authors reference several other books as their sources. ...
    (comp.lang.python)
Quantcast