1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Difference between at least and exactly? combinatorics!

  1. Nov 12, 2006 #1
    Hello everyone.

    I'm revewing these 2 problems and im' not seeing how they are getting the answer for the "...exactly 4 penny's"

    Here's the 2 problems:

    (a) A large pile of coins consist of quarters, dimes, nickels, and pennies (at least 20 of each). How many different collections of 20 coins can be chosen if AT LEAST 4 pennies must be chosen?

    Well you have 4 categories, Quaters, Dimes, nickles and Pennies it says (at least 20 of each).

    I'm going to represent the categories as bars |'s and the coins as x's.
    If the problem said, if at least 4 pennies are already chosen you can assume you already put 4 x's in the penny category, now you have 16 places left to put coins, anywhere you want.

    so you could have like this:
    P N Q D
    The above ---- means the coins u distrubted, and the stuff under the --- means the coins already there.
    So if you have 4 categories thats represented by n-1 bars (3) and 16 x's. So you have a total of

    (16+3 choose 16) = 969 which is the correct answer.

    Now for the second question:
    (b) How many different collections of 20 coins can be chosen if EXACTLY 4 pennies must be chosen?

    THe work shown is, they only used 2 bars |'s and 16 x's and got:

    (16 + 2 choose 16) = (18 choose 16) = 153.

    Now why did they only have 3 categories now isntead of 4? The reason I say they only had 3 is because they had 2 bars, thus they had to have 2+1 categories.

    Why in the first problem did they have to use 4 categories, is it because they said "at least 20 of each?"

    and in the 2nd problem they only said, If you have exactly 4 penny's, how many different collections of 20 coins can be chosen?

    I thought to myself, well if only 4 penny's are allowed the minimum amount of categories to use and still put 20 coins in would be to have a category of Penny's which is going to have 4 x's, now your going to have 16 x's (coins) to put in any category you want. So why couldn't u put 4 x's in penny's and 16 in dimes?

    Then you would only have 2 categories, so 2-1 = 1 bar. Then you would have

    (16 + 1 choose 16) = (17 choose 16)

    But the answer is (16+2 choose 16) = (18 choose 16), why did they have to use 3 categories?

  2. jcsd
  3. Nov 12, 2006 #2
    The reason is this. In the first problem you choose 4 pennies, then you have 16 coins left to pick, and these coins can be any of the 4 choices (quarters, dimes, nickels, pennies). In the second problem you choose 4 pennies, then you have 16 coins left to pick, but none of these remaining 16 coins can be pennies, thus you are picking from 3 (quarters, dimes, nickels).
  4. Nov 12, 2006 #3
    Oooo hah i got it!
    thanks again matt!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook