Permutations with Duplicates

#1
I have been trying to find information about calculating permutations that include multiple duplicate items, but have only found programming source code on the subject so far.

For example, how many unique ways can you arrange the six letters AAABBC without counting identical arrangements? I'm not looking for an answer to this specific example, but generally how a problem like this should be approached. Is there a method to generating a formula that gives you a direct answer based on the number of duplicate items in the sample set, or is there a way to calculate just the number of duplicates to be subtracted from a simple permutation?

I don't need this for homework help of any kind. I seriously lose sleep thinking about these things ... it's in my blood. I'm not sure if it will be an easy situation to address, but if there are any resources I could be pointed to it would be greatly appreciated, either online or in a book. I plan on going to a bookstore tomorrow to see if I can find anything and may go to the library over the weekend if I don't find anything by then. Thanks for the help!
 
#2
If there are n items and r of them are alike(nondistiguishable), the different no. of arrangements of these n items will be n! / r! where n!=1.2.3...n
For example if there are four letters A,B,C,D then different no. of arrangements will be
4!=1.2.3.4=24. But if two of them are alike, ie if the letters are A,A,B,C then the different no. of arrangements will be reduced to 4! / 2! because now no need to consider the internal arrangements of two A's.
In your example, the no. of different arrangements will be 6! /(3!*2!), since there are three A's and two B's.
 
#3
Thank you very much, that does make sense :tup:

So, to make sure I understand it ... if the letters were AABCCCDD, then the unique combinations would be:

8! / (2!*3!*2!) since there are 2 A's, 3 C's and 2 D's?
 

Lark

New Member
#4
Peelman,

Just as an aside:

following Vinayan's argument this is how the formula for combinations is derived; Combination of N things taking R at a time. You divide by R! for the reason Vinayan gave: for each selection of the R items you can rearrange them R! different ways but all of these ways are the same combination so you have to divide by R!.

Lark
 
#5
Thanks for all of the help everyone.

I am also trying to find how this changes when you do not use all of the elements for the subset. For example, a permuation of unique elements when finding the unique subset of 5 elements from a sample set of 7 would be:

7!/2! or 7!/((7-5)!) = 2520

What happens when the sample set consists of one or more duplicated numbers? I am better a better programmer than statistician, so I was able to find answers I believe are correct without knowing the formula to reach them. In all of these cases I am finding all possible unique 5 element subsets from seven possible elements. I wrote a quick JAVA program using a lot of looping to find the answers, hoping I could derive a formula knowing the end result, but have not been successful so far. The sample sets I used with the suspected number of unique permutations are:

AAAAAAA = 1 (This one is obvious)
AAAAAAB = 6 (This is obvious too)
AAAAABC = 31 (I'm starting to get lost)
AAAABCD = 135 (No clue)
AAABCDE = 480
AAABBCD = 250 (Curious how multiple duplicate elements worked ... still don't know)

Any clue on how to find these numbers with pencil and paper?
 
#6
Consider AAAAAAA. This can be done in only one way.

Now AAAAAAB. You need to select five from these and these five can include B or not.

Case-1
B is not included. Then all will be A's and that can be done in only one way.
Case-2
B is included. Then tere are 4 A's and one B.
No. of arrangements will be 5! / 4! = 5 (Since four of them are alike).

Then total no. of ways=1+5=6 (Case-1+Case-2)


When the letters are AAAAABC, there will be three cases.

Case-1
All are A's and that can be done in one way.
Case-2
Four A's and B or C
No. of arrangements will be 2 * (5! / 4!)=10
Case-3
Three A's and both B and C
No. of arrangements will be 5! / 3! = 20

Total no. of arrangements will be 1+10+20=31

When the letters are AAAABCD,
Case1
Four A's and any one of B,C,D
Arrangements = 3 * (5! / 4!) = 15
Case2
Three A's and any two of B,C,D
Arrangements=3 * (5! / 3!) = 60 (Note that any two of B,C,D can be selected in 3C2=3 ways)
Case-3
Two A's and B,C,D
Arrangements =5! /2! = 60
Total no. of ways = 15+60+60=135

Similarly in case of AAABCDE, total no. of arrangements will be 120+240+120=480
and so on.

There may be more simple ways to do this, but to my limited knowledge this is the way to
find the answer and you are welocme to ask any further doubts regarding this problem.
 

Lark

New Member
#7
Peelman,

The first part of your post I do not think is right.

If I understand correctly you are asking how to calculate the number of permutations of 7 items when you choose 5 of them and rearrangements within the set of 5 are not counted as different; like when you choose cards from a deck. This is actually referred to as "a conbination of 7 things taking 5 at a time". And if you look in any prob book you will find the formula as:
nCr = n!/(r!(n-r)!); in your case: 7!/5!(7-5)! = (7*6)/2 = 21.

The derivation of the combination formula goes like this:

If you did not consider rearrangements as different (ie ABCDE and ABCED as different) then there would be 7*6*5*4*3 (because for the first choice you have 7 to choose from, then second choice you have 6 etc.). But for each combination (for ex. ABCDE) all rearrangements of these are not counted (for ex. ABCED); now there are 5! such rearrangements; therefore you have to divide by 5!. It can be shown that the combination formula accomplishes the same thing that we have just calculated.

You made a comment that you still don't know how multiple duplicates work:
for ex. AABB. It is similar to what I said above and what Vinayan said. For each set you have 2! ways of rearranging the A's that are not different combinations so you have to divide by 2! and for each one of these conbinations you have 2! different combinations by rearranging the B's so you have to divide by 2! for the B's also. If this is still not clear then write out a simple example:

Do something like this:

A1 A2 B1 B2
A1 A2 B2 B1

there should be 4*3*2 such permutations, when done see why you have to divide by 2! and again by 2! because the above 2 permutations are the same combination.

I hope you can get to sleep now, or maybe the above has already put you to sleep.

Lark
 
#8
The difference between permutation and combination is, if the selected items are distinguishable you need to use permutation nPr and if they are nondistinguishable then combination nCr is used , if there are n items and you need to select r of them.

For example if a comiittee consists of 10 persons and you need to select a president, a vice-president, a secretory and a treasurer, the no. of possible ways will be
10P4 = 10! / (10-4)!, since the selected items are distinguishable by their designation.

If you want to make a sub-comittee of 4 persons, the no. of possible ways will be
10C4 = 10! / (4! * 6!) since all selected members have the same designation.
 
#9
Vinayan's post was very beneficial in what I was actually trying to find. I do understand what the difference between combinations and permutations is, but I had not studied cases where elements were duplicated.

I meant permutations in my initial post. I originally was not aware that to find P(7,7) with n duplicate elements in the set could be found by 7!/n!. This theroem does not apply when you are not using the entire set of data, such as P(7,5). Without duplications, it would be 7!/(7! - 5!), but in the case of a set like {A, A, A, B, B, C, D}, you can not do 7!/((7!-5!)(3!)(2!)). That only comes to 210, when the actual answer is 250. Using the method Vinayan attacked the issue at, considering all of the possible cases, I was able to come to the 250 figure.

I am still working on seeing if I can find a theorem for accomplishing this directly based on a number of variables. I've brought out a lot of my discrete math, probabality and statistics books and piecing things together. Sleep was lost for one night, but I am content to wait until the weekend before putting the issue to rest entirely. I greatly appreciate the help you all have given.
 
#10
You can use combination, ie nCr only if all selected items are non-distinguishable.
If some are distinguishable and some are not, you will not get the answer by using nCr. In your intial post the case was like that. That is why I didn't mention nCr in my post.
 
#11
This is a very interesting problem, I thought about it for a while but did not come up with anything better than what had been posted by vin.

I hope that you will post anything you discover, i would enjoy reading it.

when i was an undergrad i wrote a software app that was used to find a solution to a similar (but easier) problem. I would give you the code if i still had it, but this was in the early 90's. it was based upon an algorithym written by Dr. Aurthur White of Western Michigan University that allows one to find systematically all of the permutations of n objects. This work might make a starting point for you if you continue the quest. The algorithym has been published in at least one book (i do not recall the title). if you cannot find a reference to it i believe an email to Dr. White will recieve a response, he still works a WMU and is generally very helpful to students and others interested in mathematics.

thanks and good luck,
jerry