0

a) How many strings of 8 distinct letters can be made from the letters {a,b,c,d,e,f,g,h}?

b) How many of the strings you found in (a) do not have any of the elements of {a,b,c} next to each other?

The first part (a) is easy, it's just 8!. But I have no idea how to solve the second part. I understand what the question is asking, it wants all the permutations of the letters from the set {a,b,c,d,e,f,g,h} where ab, bc, ac, ba, cb, ca, cannot be in the permutation, but I still don't know what to do.

The answer is 5!(6 x 5 x 4).

janmarqz
  • 10,538
Dom Turner
  • 201
  • 1
  • 7
  • First pick a permutation of ${d,...,h}$ ($5!$ of them) and then pick an injective map $p: {a,b,c} \to {0,...,5}$ ($6 \cdot 5 \cdot 4$ of them). The map tells you where to place each letter. Now multiply. – copper.hat Apr 09 '20 at 06:13

1 Answers1

1

For b, how about first we create string with $5$ distinct letters which are not $a,b,c$. This is similar to part a, but now it is $5!$.

Then we insert $a,b,c$ between the 5 letters, at the beginning of the string, or at the end. $a$ has 6 options, then $b$ has 5 options left, and $c$ has 4 options left.

$5!\times 6\times 5\times 4$

acat3
  • 11,897
  • I think I almost get it, but why do you have to multiply 5! by (6x5x4)? I can't see the reason there. I can see why that way of solving the problem would give you the answer though. – Dom Turner Apr 09 '20 at 03:58
  • @DomTurner because we need to multiply the number of different string which is $5!$ and the way we insert the letters $a,b,c$ to obtain the total combination – acat3 Apr 09 '20 at 04:00
  • Is that from the multiplication principle? What about the order though? you could have "daebfcgh" or "defagbhc". It's like saying I have 3 different shirts and 2 different pants, how many outfits can I have from these 2 options? Well it's 3x2=6, but that gives me the combinations, not the permutations. You used the same concept here when you multiplied, and you only got the combinations, but this is a permutations problem. This is what is confusing me. – Dom Turner Apr 09 '20 at 04:04
  • @DomTurner yes that is from multiplication principle. Ah that is always the most confusing part of combinatorics. $6\times 5\times 4=\binom{6}{3}\times 3!$. We can also choose three place to insert $a,b,c$ which is $\binom{6}{3}$ to obtain combination as You mention. Then permutate the letter $a,b,c$ in $3!$ ways, if this helps – acat3 Apr 09 '20 at 04:17
  • I think I see how it works, is this way of thinking about it correct? What you did was first find all the permutations of the letters from {d,e,f,g,h}. Then you visualized this in your head -> d_e_f_g_h (the underscores represent the spaces between the letters). You wanted all the permutations of choosing 3 underscores (different types of spaces between the letters) from 6 underscores in order to pair each letter with a different underscore (a different type of space between the letters) so you did 6P3. This reduces the problem to a combination problem so that is why you multiplied. – Dom Turner Apr 09 '20 at 04:29
  • @DomTurner spot on! however, You are missing two underscores it should be $d_e_f_g_h$ – acat3 Apr 09 '20 at 04:31
  • I know, but for some weird reason, I put the underscores at the end of the sequence of letters but it still doesn't show up. – Dom Turner Apr 09 '20 at 04:32