giving the p(5) = 7 factorizations of p5. An integer of the form p1p2...pn has Bn factorizations (the nth Bell number); for example, 2310 = (2)(3)(5)(7)(11) has fifty-two factorizations. But what about, say, an integer of the form p3qr? How many factorizations does it have? Naturally, this associates an integer with each partition; from the number p5 we get the partition 5 and the number of factorizations 15; from the number p1p2p3p4p5 we get the partition 1 + 1 + 1 + 1 + 1 we associate 52.
Unfortunately, I don't really follow Yorgey's work because I don't know Haskell. And I don't know a general way to compute these yet, except in the trivial cases. But, for example, p2 q has four factorizations:
(p2q) = (p2)(q) = (p)(pq) = (p)(p)(q)
and so we associate to 2 + 1 the number 4; this is intermediate between p(3) (which is 3) and B3 (which is 5). This makes sense; in general p(n) counts the number of partitions of {1, ..., n} when no elements are distinguishable, and Bn when all elements are distinguishable. Multiset partitions interpolate between integer partitions and set partitions.
(Yorgey says that the problem is also solved in Volume 4, Fascicle 3 of Knuth, which I may track down. But I want the pleasure of working this out for myself, to some extent.)
Yorgey also says that he found the problem via Project Euler, which gives a couple hundred examples of problems that can, in general, be solved by ridiculously inefficient brute force methods or by elegant methods that require not so much computation.
4 comments:
I should point out that Knuth approaches this question from a computational point of view, just as I did: he gives an algorithm for generating multiset partitions, but not any formulas for computing how many there are. He does, however, cite some other references which might have such formulas (although I haven't looked). I'll be very interested to see what you come up with! I still have no idea how to count multiset partitions (other than generating them and seeing how many you get, which is rather silly when all you care about is how many there are).
Thanks for the mention -- I've greatly enjoyed reading your blog for a number of months now, and it was a fun surprise to see my name appear!
Also, you should learn Haskell. =) (As a pure functional language, it's particularly easy for mathematicians to pick up.)
Brent,
unfortunately my library doesn't seem to have the fascicles to volume 4 of Knuth, only the completed first three volumes. And it does seem ridiculously inefficient to list them if you just want to know what they are.
It seems like it would be difficult to write down a formula for the number of multiset partitions -- but at the same time writing an algorithm to compute that number shouldn't be too difficult. (It might be possible to take the algorithm for generating the list of them and strip it down somehow, but I haven't thought too hard about it.)
I did try to read the Haskell in your article, and it sort of made sense to me. And you're not the first person that has said vaguely interesting-sounding things about Haskell in my direction. So maybe I will.
Isabel,
Well, the fascicles are quite reasonable (only about $20 each). But at any rate, in case you're interested, here are the references he gives: P. A. McMahon, Philosoph. Trans. 181 (1890), 481-536; 217 (1917), 81-113; Proc. Cambridge Philos. Soc. 22 (1925), 951-963 (apparently the first person to publish on multipartitions), and M. S. Cheema and T. S. Motzkin, PRoc. Symp. Pure Math. 19 (Amer. Math. Soc., 1971), 39-70 which is apparently a summary of other work on multipartitions.
I think you're right, one could quite easily "strip down" the generation algorithm to just do counts instead of generating a whole list of partitions. Maybe I'll look into that once my NSF graduate fellowship application is done. =) But such a stripped-down algorithm would still be doing the same amount of work (in an asymptotic sense) as the full generation algorithm, so I still think there should be a better way. The idea would be to write the stripped-down algorithm in the form of some sort of recurrence relation and try to find a closed (or at least, more closed) form. But that might be very difficult, I'm not sure.
Brent,
I don't know if I'd say that's a reasonable price for the fascicles (since they're also quite short). I've heard that MacMahon did this sort of thing.
By "strip down" I actually meant "evaluate the recurrence", which seemed easy when I was walking home just now, but may not be once I actually try to write it down...
Post a Comment