Total Number of Possible Combinations

  1. Hi,

    I have some queries that I'm hoping you can help me with. Actually these are probably fairly straight forward for this forum but it's been a long time since I've done any formal math so some help would be appreciated.

    First query: suppose I have 4 objects: A, B, C and D. I want to know how many possible combinations there are that I can arrange them into, e.g. ABCD, ABDC, DACB etc etc.

    If I've remembered this correctly, this is a problem that can be solved using a factorial function? I.e. there are 4 objects, so the total number of possible combinations that they can be arranged in is 4! = 4 x 3 x 2 x 1 = 24.

    I think this is right but can someone confirm?

    Secondly, suppose I have the same 4 objects and I can assign them a value of either 1 or 0, making them variables with two possible states. I need to know the formula for working out how many possible combinations of states there are. I have done this manually by simply creating a table/matrix and have come up with an answer of 15 different possible states but I don't know the formula for working it out, it was just trial and error and 15 seems a bit of an odd number, personally I would have thought 16 (4^2) would make more sense but I cannot find any other combination other than the 15 I've already got.

    ABCD
    1000
    0100
    0010
    0001
    1100
    1010
    1001
    0110
    0101
    0011
    1110
    1101
    1011
    0111
    1111

    However this method is a total ball-ache, even with just 4 numbers so it would obviously be much easier if I could just apply a formula. Note that in this case I don't want to change the ABCD order, just the value of each variable, 1 or 0, and then to know how many different combinations of states there are altogether.

    Thanks in advance for any help.
    -Rob
     
    Last edited: Mar 16, 2007
  2. jcsd
  3. You are correct about the use of factorials. Since for the first letter you have a choice of 4, for the second of 3, then of 2 and 1, it is only natural. As for the second question, look at it this way: you have 4! different arrangements. Now, for each of these arrangement, you have some number of possible 1 and 0 combinations. How would you proceed to calculate this number? Look at how many choices you have for each digit, and construct a vein diagram. Look at the first steps:


    ..................1...............................................0
    .........../............\................................./................\
    .........1...............0..............................1..................0
    ......./...\............/...\........................../..\.............../...\
    ......1....0..........1.....0.......................1....0............1.....0
     
    Last edited: Mar 16, 2007
  4. Thanks for the quick response but I don't think I made myself clear on the second query. The state of the variables ABCD can be either 1 or 0 but the order they are in for the second case will always be ABCD. I think in your response you assume that the order ABCD can change as well as the state (1 or 0).

    Thanks
    -Rob
     
  5. That doesn't change much :tongue2:. Actually, I showed how to find the number of possible "states", so to speak. Is this homework or just curiosity? Because if it's the former, I am afraid the rules of the boards do not allow me to tell you much more.
     
    Last edited: Mar 16, 2007
  6. It's in relation to work, not school - I'm 32 years old! :D
     
  7. Here's a small hint.

    Include 0000 in your list.
     
  8. Well then:

    Since you have four digits, and for each you have to choices, the number is 2^4 = 16. Look for the simpler case of two digits:

    you have 2 choices for the first digit; either 0 or 1.
    you have 2 choices for the second digit; either 0 or 1.

    Now, say you have something of the form 1 x, where x is the second digit. We have either x = 0 or x = 1. Therefore, if 1 is the first digit, there are two possibilities: 10 and 01. Now, same goes with 0 as the first digit: 01 and 00. In total, you have 2^2 = 4 possibilities. Now, for three digits, look what happens:

    You have something of the form abx. Now consider ab alone. We already showed that there are 4 possibilities for ab. Let's name them A, B, C and D. abx is then equivalent to either one of those

    Ax
    Bx
    Cx
    Dx

    Since x is either 0 or 1, we have as the set of all possibilities:

    A0, A1
    B0, B1
    C0, C1
    D0, D1

    Which has 2^2 * 2 = 2^3 = 8 terms. Now can you see that when adding more and more digits, we always end up with 2^n as the number of possibilities?
     
  9. Makes sense, thanks for the help. :)

    -Rob
     
    Last edited: Mar 16, 2007
  10. This is all very helpful!

    I have a similar question for work:

    Say I have 5 patents going into trial. All, one, none, or any combination of them may be found to infringe (so 2 options per patent - either it infringes or it doesn't).

    How many possible outcomes/combinations are there?
     
  11. Is it 2^5 = 32 , or am I wrong?
     
  12. Hello? can anyone let me know if I'm on the right track with the answer of 32 combinations? PPPLLLEEEAAASSSEEE :-)
     
  13. Yes. That's correct.
     
  14. I have a similar question. i need to work out how many possible combinations i can make out of the following: using all leters and numbers. length must be 5. and it must start with an F.

    E.g.

    F0001, FA001, F03V4 etc....

    how can i work this out? or even simpler what is the final number?

    Thank you for your time.
     
  15. HallsofIvy

    HallsofIvy 40,767
    Staff Emeritus
    Science Advisor

    1) Don't get upset if you don't get a response within 2-3 hours. People don't just sit here waiting for questions to answer.

    2) Don't "hijack" other people's threads to ask a new question- start your own thread.

    arcintl, all of these problems are based on "the fundamental counting principle"- if there are "m" ways of doing one thing and, independently, "n" ways of doing another, there are mn ways of doing both.

    Since you require that the 5 letters start with "F" there is only 1 way of choosing the first letter. But there are then 26+ 10= 36 letters or digits (You say "numbers", but if a single number could be say 1000000000000, there is no finite answer) for each of the remaining 4 symbols: there are (1)(36)(36)(36)(36)= 364 ways to make "combinations of 5 letters or digits, starting with F".
     
  16. What you guys are talking about are Combinations and Permutations.

    They are very similar, but with Permuations, order matters. In other words, the combination AB is the same as combination BA, whereas with permutations, they are different.

    The formula for permutations is
    [tex]P(n,k)=\frac{n!}{(n-k)!}[/tex]

    The formula for combinations is
    [tex]C(n,k)=\frac{P(n,k)}{k!}=\frac{n!}{k!(n-k)!}[/tex]

    where n = the number of items to choose from
    and k = the number of items selected

    In the original question, we were trying to find out how many ways we could rearrange 4 items. That means, given 4 items (n=4) how many ways can we arrange them into groups of 4 (k=4). This is a permutation, so the formula is
    [tex]P(4,4)=\frac{4!}{(4-4)!}=\frac{4!}{0!}[/tex]

    Note that 0! = 1, therefore you have
    [tex]P(4,4)=\frac{24}{1}[/tex]

    Wheneve n=k, you'll have
    [tex]P(n,n)=\frac{n!}{(n-k)!}=\frac{n!}{0!}=\frac{n!}{1}=n![/tex]

    If we wanted to know how many ways to rearrange the letters A, B, C, & D into groups of 2 letters (AB, AC, AD, etc.), you would use n=4 (4 items to choose from) and k=2 (the number of items selected) and
    [tex]P(4,2)=\frac{4!}{(4-2)!}=\frac{4!}{2!}=\frac{24}{2}=12[/tex]


    With the second part of the question, what we're looking at is a 4-digit binary number. In this case each digit can be one of 2 possible states (n=2), but we are only going to select one at a time (k=1). You should notice that any time k=1, then the permutation will be equal to the combination; P(n,1) = C(n,1)

    Therefore, for any single digit, we have 2! = 2 possibilities (obviously, since it could only be a 0 or a 1). The difference here is that we have 4 binary digits, each with 2 possibilities. This results in
    [tex]2\times2\times2\times2=2^4=16[/tex]
     
  17. This question deals with combinations (not permutations), since order doesn't matter here (Patent #1 and Patent #2 both infringing is the same as Patent #2 and Patent #1 infringing).

    This is actually the sum of 6 different combinations.
    1) the combination where none of 5 patents infringes (n=5, k=0)
    2) 1 of 5 infringes (n=5, k=1)
    3) 2 of 5 (n=5, k=2)
    4) 3 of 5 (n=5, k=3)
    5) 4 of 5 (n=5, k=4)
    6) 5 of 5 (n=5, k=5)

    So the total number of combinations is

    [tex]C(5,0) + C(5,1) + C(5,2) + C(5,3) + C(5,4) + C(5,5)[/tex]

    [tex]= 1 + 5 + 10 + 10 + 5 + 1 = 32[/tex]
     
  18. But the sum of all combinations IS 2^n.
     
  19. Yes, no argument there. I was showing how to determine the answer via combinations and permutations ...
    there's more than one way to skin a cat!
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?