# Efficient counting techniques

1. May 18, 2013

### John112

Are there efficient methods of findings the answer to combination problems like these?

The letters A, A, B and C are arranged in any order. How many DISTINCT sequences can we form?

If two letters weren't the same, then it would be simple. I can find the answer relatively easily since it's only 4 letters. Imagine if this was a sequence of 10 letters where two letters were the same. Then creating all possible combinations would be really inefficient and laboring. Is this any trick for problems where duplicate letters exist?

P.S. By the way the answer is 12. I found it by creating a tree diagram.

2. May 18, 2013

### LCKurtz

If the A's were distinct, the number of arrangements would be 4! = 24. Now for each arrangement, wherever the two different A's are, there is another arrangement that is exactly the same except the A's are swapped. These two arrangements would be indistinguishable if the A's are the same, so that cuts the number of distinct arrangements in half, which gives 12.

In general if you have n objects of which k are the same, the number of arrangements is$$\frac{n!}{k!}$$Do you see why?

3. May 19, 2013

### John112

Yeah, I saw that. I wasn't sure whether that pattern of dividing by k factorial would hold for bigger sequences. I was trying to find a proof for that. Thanks for the helpful response. By the way is there already a proof for that general formula?

4. May 19, 2013

### LCKurtz

Yes. Google permutations with some alike. One hit is:
http://dwb4.unl.edu/Chem/CHEM869N/CHEM869NMats/Permutations.html [Broken]

The idea is that the k things that are alike would have given k! permutations but only one if they were the same.

Last edited by a moderator: May 6, 2017