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

Homework Help: Combinatorics (sorry for long thread)

  1. Jun 23, 2004 #1

    1. In baseball, there are 24 different "base-out" configurations (ruuner out first - two outs, bases loaded - none out and so on). Suppose that a new game, sleazeball, is played where there are seven bases (excluding home plate) and each team gets five outs an inning. How many base-out configurations would be possible in sleazeball?

    Where I got stuck: [WIGS] I don't about baseball very much... what does that base-out configs mean? How will I relate that to the sleazeball (which is more unfamiliar to me) and what does "where there are seven bases (excluding home plate) and each team gets five outs an inning" mean?

    2. Residents of a condominium have an automatic garage door opener that has a row of 8 buttons. Each garage door has been programmed to respond to a particular set of buttons being pushed. If the condo. houses 250 families, can residents be assured that no two garage doors will open on the same signal? If so, how many additional families can be added before the eight-button code becomes inadequate? Note that the order in which the buttons are pushed is irrelevant.

    [WIGS]: Is it possible that if I pushed only one of the buttons, one of the garage doors will open? Am I allowed to press a button twice or three times? I feel vague about this problem bec. that particular set of buttons is not specific in detail...

    3. In international morse code, each letter in alphabet is symbolized by a series of dots and dashes. WHat is the maximum number of dots and/or dashes needed to represent any letter in the english alphabets?

    [WIGS]: I know that the answer is 4. The problem is how can I show through permutations or technique in combinatorics that the answer is indeed 4?

    4. Proteins are chains of molecules chosen (w/ repetition) from some 20 different amino acids. In a living cell, proteins are synthesized through the genetic code. The four key nucleotides are adenine, guanine, cytosine and uracil. Assuming A,G, C or U can appear any number of times in a nucleotide chain and that all sequences are physically possible, what is the minimum length the chains must attain to have the capability of encoding the entire set of amino acids? Note: Each sequence in the genetic code must have the same number of nucleotides.

    [WIGS]: My friends told me, and I agree that the answer is 3. (Same problem as to #3)
  2. jcsd
  3. Jun 23, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Number 4:
    For each member of the chain, you have 4 possibilities.
    Hence, n members allow [tex]4^{n}[/tex] different configurations.
    clearly, n=3 is the least number, since 16<20-30<64
  4. Jun 23, 2004 #3


    User Avatar
    Science Advisor
    Homework Helper

    The "base-out" configuration is not a real baseball term, I don't think anyone uses it, it is just in your book. What they mean is a specific combination of how people are on the bases, and how many outs there are. For example, if you have two dice and three coins, the number of "die-coin" configuraitons would be (6x6)x(2x2x2) = (36)(8) = 288. This assumes that the order of the dice matter, i.e. a {1,6} is different from a {6,1} (maybe one die is black and one is not. Of course, it also assumes that the order of the coins matter as well. Now, the configuration of the runners on the bases is independent of the number of outs, so the number of "base-out" configurations is equal to the number of base configurations, times the number of out configurations. There are three out configurations: 0 outs, 1 out, and 2 outs. There are 8 base configurations:
    bases empty
    runner on 1st
    ".........." 2nd
    ".........." 3rd
    runners on 1 and 2
    "............" 1 and 3
    "............" 2 and 3
    bases loaded

    This is equal to 3-choose-0 + 3-choose-1 + 3-choose-2 + 3-choose-3. Why is it "choose?" Because 3-choose-2 essentially gives us the number of ways we can choose 2 bases, and we'll say these two bases have runners on them. And it makes no difference in saying we have runners on 1st and 2nd versus runners on 2nd and 1st. If we have n bases, this is represented as:

    [tex]\sum _{k=0} ^n {n\choose k}[/tex]

    This gives us 8 for baseball, and we multiply by 3 (the number of "out" configurations) and get 24. For any similar sport, let B represent the number of bases, and O represent the number of outs per inning. The number, N, of base-out configurations is:

    [tex]N = O \times \sum _{k=0} ^B {B\choose k}[/tex]
    Me too. I would think there's no rule saying you can't push a button 90000 times, so you can pretty much come up with any combination you want. It is a vague question.
    Each letter is a permuatation of dots and dashes. The first symbol can be a dot or a dash. If we were to only go with 1 symbol for letters, we could have 2 letters (either dot or dash). Now, the second symbol can also be a dot or dash. With two symbols, we can have 2 x 2 = 4 letters. With three symbols, we can have 2 x 2 x 2 = 8 letters. Of course, if you're using 2 symbols, you don't have to use 2 symbols, i.e. you can use 1 or 2 symbols. In this case, with 2 symbols you have 2 + 4 = 6 letters. With three symbols, you have 2 + 4 + 8 = 14 letters. Now, this is assuming you can't have one with 0 symbols. Now, basically, you want to find the smallest whole number value possible for n such that:

    [tex]\sum _{k=1} ^n 2^k \geq 26[/tex]

    You already know it's not 3. If 4 fits the equation, you've found your answer.
  5. Jun 23, 2004 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    2. Since the order is irrelevant, we are interested in combinations, not permutations. Also it appears that different lengths of codes can be used by different residents. Also, (otherwise you can get an infinite number of combinations), I shall disallow multiple pushes of any button. If codes are n buttons long, there are C(8,n) such codes. So, the total number of distinguishable codes that can be made are

    [tex]\sum _{n=0..8} C(8,n) [\tex]

    This kind of sum is very common. You must know what it is. From here, it's just plugging in numbers...
  6. Jun 23, 2004 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    3. Consider a combination that is n characters long. So imagine n boxes and into each box, you can put in a dot or a dash - 2 possibilities for each box. Thus for the n-box combination there are 2^n different possibilities. Now if n is the maximum length required, then you can also make combinations that use fewer than the n boxes. For a single box case, there are 2 (or 2^1) possibilities. For the 2-box case, there are 4(2^2) possibilities. So, with a maximum of n boxes, you can make 2^1 + 2^2 + ...+2^n different letters. At what n does this sum exceed 26 ?
  7. Jun 24, 2004 #6
    Hello Gokul43201, what is "[tex]\sum _{n=0..8} C(8,n) [\tex]"? By the way, thanks for the help. Thanks AKG and arildno
  8. Jun 24, 2004 #7


    User Avatar
    Science Advisor
    Homework Helper

    He meant:

    [tex]\sum _{n=0} ^8 {8\choose n}[/tex]

    That's the sum from n=0 to n=8 of [itex]{8\choose n} = \frac{8!}{n!(8-n)!}[/itex]. If you make Pascal's Triangle, it is equivalent to finding the sum of the numbers in the eighth row.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook