SOLUTION: how many strings can be formed by ordering the letters ABCDE if: (1pt each) a.) A appears before D; b.) Contains either the substring DB or the substring BE or both

Algebra ->  Permutations -> SOLUTION: how many strings can be formed by ordering the letters ABCDE if: (1pt each) a.) A appears before D; b.) Contains either the substring DB or the substring BE or both       Log On


   

Question 1183064: how many strings can be formed by ordering the letters ABCDE if: (1pt each)
a.) A appears before D;
b.) Contains either the substring DB or the substring BE or both
Found 2 solutions by ikleyn, math_tutor2020:
Answer by ikleyn(52778) About Me  (Show Source):
You can put this solution on YOUR website!
.

            In my response,  I will answer part  (a),  ONLY,  because it is really good entertainment problem/question,
            while the part  (b)  is rather technical   -   so,  the two parts differ by their style. 


The answer is  5%21%2F2 = %281%2A2%2A3%2A4%2A5%29%2F2 = 120%2F2 = 60 strings,


because exactly half of all 120 permutations have A appeared before D, 
while the other half of the 120 permutations have A appeared after D.


Part (a) is answered.



Answer by math_tutor2020(3816) About Me  (Show Source):
You can put this solution on YOUR website!

Part (a)

I'll break things up into cases.
  • Case 1: the letter A is in slot 1
  • Case 2: the letter A is in slot 2
  • Case 3: the letter A is in slot 3
  • Case 4: the letter A is in slot 4
  • Case 5: the letter A is in slot 5
Conveniently, the case number and the slot number line up perfectly.

If case 1 happens, then we have 4 letters to permute (B,C,D,E) in four slots. That gives us 4! = 24 different permutations in this case.
Since we'll refer to this later, I'll make A = 24.

If case 2 occurs, then D must go in the three remaining slots to the right of A. That consequently means that we have 3 choices for the first slot (B, C or E)
So we have...
  • 3 choices for slot 1 (either B, C or E)
  • 1 choice for slot 2 (the letter A)
  • 3 choices for slot 3 (D plus any of {B,C,E} such that we don't pick whatever was in slot 1)
  • 2 choices for slot 4
  • 1 choice for slot 5
Once we arrive at slots 3 through 5, we have this countdown going on (3,2,1)
Overall, we have 3*1*3*2*1 = 18 different permutations to satisfy case 2.
Let B = 18 so we can use it later.

Now onto case 3.
We have
  • 3 choices for slot 1 (B, C or E)
  • 2 choices for slot 2 (B, C, or E but we cannot reuse whatever is in slot 1)
  • 1 choice for slot 3 (the letter A)
  • 2 choices for slot 4 (D, plus whatever isn't already taken)
  • 1 choice for slot 5 (whatever letter hasn't been used yet)
We therefore have 3*2*1*2*1 = 12 permutations here.
Let C = 12

Then case 4 would have...
  • 3 choices for slot 1 (B, C, or E)
  • 2 choices for slot 2 (same as before but we cannot reuse a letter)
  • 1 choice for slot 3 (same idea but now we cannot reuse those two letters)
  • 1 choice for slot 4 (the letter A goes here)
  • 1 choice for slot 5 (the letter D must go here to be to the right of A)
We have 3*2*1*1*1 = 6 permutations for case 4.
Let D = 6.

Lastly, we consider case 5.
There are no permutations possible such that A is in slot 5 and D is to the right of letter A.
So E = 0.

Add up the results we found
A+B+C+D+E = 24+18+12+6+0 = 60

Interestingly, this value is exactly half of 5! = 120. I'll let you decide if that's a coincidence or not.

Answer: 60

===================================================================================================
Part (b)

Again we consider various cases
Case 1: The string contains DB
Case 2: The string contains BE
Case 3: both cases 1 and 2 happen simultaneously

The sample space of letters to pick from is {A,B,C,D,E}
That reduces to {A,C,E} when we kick out D and B. This is because D and B must be together, so we "glue" them together to form the "megaletter" DB.
In other words, we get this new set: {A,C,E,DB} where again DB is treated as one item.

There are 4 letters in that new set so there are 4! = 24 permutations.
You should find that there are 24 permutations of {A,C,D,BE} as well.

So the number of strings in case 1 and case 2 are 24 items each.

For case 3, we consider the set {A,C,DBE} where now we treate "DBE" as one item.
This is because we want DB and BE to happen at the same time. So they must share that common B as the glue or bridging letter.

There are 3! = 6 permutations here

The question is now: How many strings are there such that we have DB, BE, or both?
That would be 24+24-6 = 42 strings

We simply add up the counts for cases 1 and 2, then subtract off the count for case 3.
Case 3 is the overlapping portion between cases 1 and 2. When adding cases 1 and 2, we are double-counting that overlapped portion.
For more info, see the inclusion-exclusion principle.
https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

Or you could think of it like this
n(A or B) = n(A) + n(B) - n(A and B)

Answer: 42

===================================================================================================

To verify either answer, you can use this handy permutation calculator to generate all 5! = 120 strings (admittedly it sounds like a lot of strings but a computer can do this very quickly and you can use a search feature to pick out the items you want)
https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html
You can also take advantage of the pattern search tool on that same link to quickly filter out the stuff you don't want.