Efficient counting techniques

  • Thread starter John112
  • Start date
  • #1
19
0

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,551
761
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.
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
19
0
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?

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
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,551
761
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?
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:

Related Threads on Efficient counting techniques

Replies
20
Views
1K
Replies
3
Views
633
  • Last Post
Replies
7
Views
17K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
3K
Replies
11
Views
14K
Top