Log in

No account? Create an account
10 May 2005 @ 06:48 am
Stupid brain  
I grabbed a handfull of m&ms yesterday and ended up with 15 of them with a color arangement that formed a nice pyramid (1,2,3,4,5) and i was trying to figure out what exactly the odds of that were, with the unwarranted assumption that the five colors all have equal representation in the mix.

I remember how to figure out card probabilities and other such selections from a limited set with n choose k, and i certainly remember how to figure out an ordered selection from an effectively unlimited set ((1/5)^15 in this case obviously) but how do you eliminate the repeats to get an unordered selection from an unlimited set? 6 choose 15 obviously doesn't work.

*sigh* i know my memory sucks, but i wish i could remember at least the cool things i've learned in the past
Current Mood: geekygeeky
Catbirdcatbird on May 10th, 2005 02:01 pm (UTC)
Figure out how many times they repeat.
DonAithnendonaithnen on May 10th, 2005 02:34 pm (UTC)
but how do you eliminate the repeats to get an unordered selection from an unlimited set?

Why yes, i'd figured that part out, i was kind of asking about the process :)
DonAithnendonaithnen on May 10th, 2005 02:50 pm (UTC)
And furthermore my first thought along those lines was to subtract 15! from 5^15, which clearly is not the correct process unless the act of picking 15 m&ms out of a bad is physically impossible and i just imagined it :)
Brie2gouda4u on May 10th, 2005 03:12 pm (UTC)
You should ask Levin, given that he taught discrete at Mudd...
Catbirdcatbird on May 10th, 2005 03:54 pm (UTC)
He would give a much better responce then I could.
Steuard: physicssteuard on May 10th, 2005 06:27 pm (UTC)
I think that the function you're looking for is called "multichoose". You can find a formal explanation at the Mathworld site, though you'll need to follow a couple of links there to get the whole story. (The definition of "multiset" is necessary to know what the entry is talking about at all, and the "multinomial coefficient" link contains the explicit formula for "n multichoose k" in terms of factorial functions.) The formula for "n multichoose k" is equal to "(n+k-1) choose k". There's probably a slick combinatorial proof of that, but I don't recall what it is.

Interestingly enough, my Google search for "multichoose" also turned up the abstract of a talk at a math conference entitled "Multichoosing M&M's". The abstract says that n multichoose k "can be thought of as the number of ways to pick a handful of size k from n colors of M&M's". Too bad the talk itself isn't online.
Geoff: Ichabodthegreatgonz on May 10th, 2005 07:49 pm (UTC)
I had to fall back on Scheinerman to refresh my memory, but the "slick combinatorial proof" basically goes like this: n multichoose k means "count the number of ways to choose a size-k multiset from a size-n set." You can encode any size-k multiset as a sequence of "stars and bars" (* and | symbols), where n-1 bars divide the stars into n sets, and the number of stars in each set represents the number of appearances of the corresponding symbol in the multiset so, for example, "*|*||***|*" encodes the multiset {1,2,3,3,3,4}. The encoding is 1-1 and onto, so now we just need to count possible stars-and-bars strings containing n-1 bars and k stars. That's the same as choosing k distinct locations for stars, from n+k-1 possible positions in the string, so the count is is n+k-1 choose k.
Geoff: Coyote (scorched)thegreatgonz on May 10th, 2005 07:51 pm (UTC)
I fucked up my example. "*|*||***|*" encodes {1,2,4,4,4,5}. Sorry.
Steuard: physicssteuard on May 10th, 2005 07:57 pm (UTC)
Righto, that was it. Thanks for the reminder.
DonAithnendonaithnen on May 10th, 2005 10:07 pm (UTC)
Hmmm, so if i'm doing it right that should mean 3876 different combinations for 15 m&ms of 5 colors. There should be 120 ways to get the perfect pyramid since it would just be the permutations of the 5 colors for the 5 rows of the pyramid, which would give about a 3% chance of getting a pyramid with 15 completly random m&ms, which sounds like a reasonable figure at least.

Of course in the last four or five samples i've gotten it twice, but the mix of m&ms is certainly _not_ evenly distributed so it's probably more common than the random probability would have you believe.
Ambermaggiedacatt on May 13th, 2005 03:32 am (UTC)
M&M mixes, or mixes of any multiple-colored candy, tend to be consistent, even if not perfectly even. Consistent, not necessarily equal. They tend to do a roughly-equal mix favoring the colors/flavors/whatever that are cheaper to produce.
Ambermaggiedacatt on May 13th, 2005 03:33 am (UTC)
So you could get a bunch of bags of M&Ms and do a statistical analysis of the color ratio, if you wanted.