Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Efficient counting techniques

  1. May 18, 2013 #1
    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. jcsd
  3. May 18, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
  4. May 19, 2013 #3

    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?
  5. May 19, 2013 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Efficient counting techniques
  1. Counting, kinda (Replies: 29)

  2. Proof techniques (Replies: 1)