Probably Not Permutations

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
sixes_and_sevens
Posts: 71
Joined: Thu Jun 25, 2009 3:15 pm UTC
Location: Birmingham, UK

Probably Not Permutations

Postby sixes_and_sevens » Thu Jul 15, 2010 1:08 pm UTC

I need to find the number of permutations of m objects of one type and n objects of another. So if I have m apples and n oranges, how many different ways are there of laying out all of these m+n pieces of fruit?

It looks like it should have a relatively straightforward general solution, but I can't seem to come up with one.

User avatar
Patashu
Answerful Bignitude
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

Re: Probably Not Permutations

Postby Patashu » Thu Jul 15, 2010 1:21 pm UTC

Think about it this way:

You have (m+n)! ways of re-arranging m+n distinctly labelled fruits in m+n positions.

However, they are not distinctly labelled - every apple can be interchanged with another apple, for instance. We know there are m! ways to order m apples. So, out of our (m+n)! permutations, we can group every m! of these permutations and count them as the same permutation, because they're the same but just shuffling apples into different spots.

But our oranges are not distinctly labelled either, so out of our remaining, distinct-apple-position groups, we have to group every n! of these permutations together and count them as one - they're the same but just shuffling oranges into different spots.

(m+n)!/m!n!

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Probably Not Permutations

Postby jaap » Thu Jul 15, 2010 1:24 pm UTC

sixes_and_sevens wrote:I need to find the number of permutations of m objects of one type and n objects of another. So if I have m apples and n oranges, how many different ways are there of laying out all of these m+n pieces of fruit?

It looks like it should have a relatively straightforward general solution, but I can't seem to come up with one.


You're looking for Combinations.
Think of it as: You have a row of m+n locations, and you want to choose m of those locations to place apples in. The rest of the locations are then filled by oranges. You therefore have "(m+n) choose m" possibilities, which is (m+n)!/(m!n!).

If you have 10 pieces of fruit, of which 3 are apples, then you have 10 choices for the location of the first apple, 9 for the second, and 8 for the third. It doesn't matter however which order those three locations are chosen in. So each choice of three locations could have arisen in 3 times 2 times 1 way. The final result is therefore (10*9*8) / (3*2*1), or 10!/(7!3!).

User avatar
sixes_and_sevens
Posts: 71
Joined: Thu Jun 25, 2009 3:15 pm UTC
Location: Birmingham, UK

Re: Probably Not Permutations

Postby sixes_and_sevens » Thu Jul 15, 2010 1:39 pm UTC

Well, now I feel silly.

I'd been trying to frame it in the context of permutations, because I thought order needed to be preserved. When you describe it like that it seems obvious.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Probably Not Permutations

Postby Tirian » Thu Jul 15, 2010 2:50 pm UTC

Welcome to combinatorics. If you can't solve a problem, it's because you're thinking too hard about it.


Return to “Mathematics”

Who is online

Users browsing this forum: Bloopy and 11 guests