tag:blogger.com,1999:blog-264226589944705290.post3625503378653239216..comments2023-09-29T02:57:42.471-07:00Comments on God Plays Dice: Enumerating multiset partitionsMichael Lugohttp://www.blogger.com/profile/15671307315028242949noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-264226589944705290.post-91871908594809614272007-10-30T16:07:00.000-07:002007-10-30T16:07:00.000-07:00Brent,I don't know if I'd say that's a reasonable ...Brent,<BR/><BR/>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.<BR/><BR/>By "strip down" I actually <I>meant </I> "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...Michael Lugohttps://www.blogger.com/profile/15671307315028242949noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-26220342341275522422007-10-30T15:51:00.000-07:002007-10-30T15:51:00.000-07:00Isabel,Well, the fascicles are quite reasonable (o...Isabel,<BR/><BR/>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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-6667196334389685652007-10-30T11:26:00.000-07:002007-10-30T11:26:00.000-07:00Brent,unfortunately my library doesn't seem to hav...Brent,<BR/><BR/>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. <BR/><BR/>It seems like it would be difficult to write down a <I>formula</I> 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.)<BR/><BR/>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.Michael Lugohttps://www.blogger.com/profile/15671307315028242949noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-23355522987997885752007-10-30T10:56:00.000-07:002007-10-30T10:56:00.000-07:00I should point out that Knuth approaches this ques...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).<BR/><BR/>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!<BR/><BR/>Also, you should learn Haskell. =) (As a pure functional language, it's particularly easy for mathematicians to pick up.)Anonymousnoreply@blogger.com