1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics, alphabet/bitstrings

  1. Oct 29, 2014 #1
    1. The problem statement, all variables and given/known data
    1)How many bitstring of length 11 contain three more 0's than 1's?

    2)How many string of 5 lowercase letters from the Latin alphabet contain:
    a) the letter c?
    b) the letters c and d?
    c) the letters c and d in consecutive positions with c preceding d and all letters distinct?
    d) the letters c and d, when c is somewhere to the left of d in the string and all letters are distinct?


    3. The attempt at a solution

    For 1) I got 11C4

    2a) I got 26^5 - 25^5
    b) 26^5 - 24^5
    c) 4C1*2!*24*23*22/2!... I am not sure at all about this one, my logic is that I take away c and d from the sample size, then divide by 2! to get the arrangement where c is infront of d.
    d) 5C2*2*1*24*23*22/2! I am not sure about this one either, I am basically choosing two positions for c and d, subtracting 2 from 26, then multiplying 2*1 to choose from the c and d, then randomly choosing letters for the remaining spots, then dividing by 2! to get the arrangement where c is to the left of d.

    Can you guys point out which ones are right and which ones are wrong? Thank you so much.
     
    Last edited: Oct 29, 2014
  2. jcsd
  3. Oct 29, 2014 #2

    RUber

    User Avatar
    Homework Helper

    For 2a and 2b what are you using or your formula?
    I would normally look at 5c1*25^4+5c2*25^3+.,.
    For 1 C, 2 C's and so on to 5 C's.
    If you are using a streamlined formula I would be interested to know more.
     
  4. Oct 29, 2014 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    In 2a, Panphobia is simply subtracting those that do not contain c from all possible strings of 5 letters.
    Panphobia, 2b is wrong. 24^5 is the number that contain neither c nor d, so subtracting from 26^5 yields the number containing ... what?
    I agree with your answers to 2c and 2d, though you could have avoided the *2/2 by thinking about it slightly differently: having chosen the two spots for c and d, their individual positions are fixed by the ordering condition.
     
  5. Oct 29, 2014 #4
    Then 2b could the answer be 5C2*2*24*23*22
     
  6. Oct 29, 2014 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, why do you think it could be that? The 24*23*22 looks like distinct letters, which is not a condition here.
    (Hint: principle of inclusion and exclusion.)
     
  7. Oct 29, 2014 #6
    Oh yea I was looking at a completely different problem sorry haha. Also why is 26^5 - 24^5 wrong? Wait is it because that will give strings of length 5 that have either c or d or both? (I am kind of guessing now) I am thinking it is 2*(26^5-25^5)-(26^5-24^5)
     
    Last edited: Oct 29, 2014
  8. Oct 29, 2014 #7

    RUber

    User Avatar
    Homework Helper

    That's right , so you would just have to add back in the cases with c and not d and d and not c.
     
  9. Oct 29, 2014 #8
    Is the answer 2*(26^5-25^5)-(26^5-24^5)
    Since if AUB = A + B - A∩B so A∩B = A + B - AUB = (26^5-25^5) + (26^5-25^5) - (26^5 - 24^5)

    Also is my answer to 1) correct?
     
    Last edited: Oct 29, 2014
  10. Oct 29, 2014 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, though using the inclusion/exclusion formula you can just write down 26^5 - 2*25^5 + 24^5. In words: those using 26 letters, minus thus not using c, minus those not using d, plus those using neither c nor d (because we've subtracted those twice).
     
  11. Oct 30, 2014 #10
    My teacher says 2b is wrong he says it is 5C1*4C1*26^3 why is mine wrong?
     
  12. Oct 30, 2014 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I'm afraid your teacher is wrong. I can see what he is doing: pick one of five to be a C, pick one of the remaining four to be a D, then fill in the rest. But this counts some patterns more than once. E.g. CDCAA gets counted twice, first by picking the first position to place a C and later filling in CAA arbitrarily in the last 3 positions; and again picking the third position to be a C then filling in the 1st, 4th and 5th positions arbitrarily.
    Stick with the answer you have.
    If your teacher is unpersuaded, try it with a simpler set-up, a three letter alphabet and three positions. Sequences containing A and B:
    AAB, ABA, BAA, ABB, BAB, BBA, plus the six permutations of ABC = 12 = 33-2.23+13, not 3C1.2C1.31 = 18.
     
  13. Oct 30, 2014 #12
    Yea same with the first one, he put 5C1*26^4 but that is wrong by your logic too, I tried going up to him in class but he didn't understand fully the way I did I so he told me to email him.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics, alphabet/bitstrings
  1. Combinatorics problem (Replies: 2)

  2. Basic Combinatorics (Replies: 3)

  3. Combinatorics Question (Replies: 7)

Loading...