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: Basic counting principles

  1. Jan 18, 2005 #1
    1) If X is an n-element set and Y is an m-element set, how many functions are there from X to Y?

    I am not sure but I worked on this for a while and I come up with there are m^n possible functions.

    2) There are five distinct computer science books, three distinct mathematics books and two distinct art books. In how many ways can these books be arranged on a shelf if the two art books are not together?

    I get 10!-8!*9*2=2903040 possibilities.

    3) X={5,6,7,...,198,199,200} How many numbers in X consist of distinct digits?
    I cannot for the life of me figure this monster out.... :yuck:
    Please help me get started here....

    Last edited: Jan 18, 2005
  2. jcsd
  3. Jan 18, 2005 #2


    User Avatar
    Homework Helper

    I think you have the right answers for 1) and 2). For part 3, try to deal with 1 digit numbers first, then 2 digits, then 3.

    For 1 digit I get: 5 numbers (5,6,7,8,9)
    For 2 digits I get: 9*9 (the first digit can be 1-9. the second digit can be 0-9 excluding the first digit so that leaves 10-1=9).

    Try 3 digits.
  4. Jan 18, 2005 #3
    right so there is 5 for 1 digit, 9*9 for 2 digits and I think there are 8*8 for three digits. So I would have 5+81+64=....80 and 60 and 10 is 150...Do you get 150 too?

    I think that is right, thanks

  5. Jan 18, 2005 #4
    I kind of feel bad even asking this next question because it is what most would consider a difficult question. I have spent too much time on it and so now it is time to enlist the help of PF....here goes

    There are 10 copies of one book and one copy each of 10 other books. In how many ways can we select 10 books? :eek:

    I know that the correct answer is 2^10 but I cannot figure out how to work this problem out.

  6. Jan 19, 2005 #5
    For the first part, I believe the answer is equal to the number of permutations with unrestricted repetitions of size n taken from the set Y
    (which leads to the same answer as what you got)

    The second part is right.

    Third Part:
    hint break it up into three cases
    1: numbers with just one digit
    2: numbers with two digits
    3: numbers with three digits

    another hint
    as an example for the two digit case, think of this as first selecting the digit to go in the one's place, now how many choices do you have for the tens place.... think of the multiplication rule
    Last edited: Jan 19, 2005
  7. Jan 19, 2005 #6
    This is another example where its best to break the problem into cases, where each case depends upon the number of books you've chosen from the set of 10 identical books
    For example:
    the first case would be
    10 nCr 10 (where you have chosen to select 0 of the identical books )
    then add subsequent cases
    next case would be
    10 nCr 9 ( where you've chosen one of the identical books )
    and so on...
    Last edited: Jan 19, 2005
  8. Jan 19, 2005 #7

    Andrew Mason

    User Avatar
    Science Advisor
    Homework Helper

    Since a function X to Y is not necessarily one to one, one element of Y can be mapped to each element of X. So I would say that your answer is correct.

    It starts at 5?

    The brute force method: For Z<101, there are only 10 numbers that do not have distinct digits (11, 22, 33, ... 99, 100). From 101-200 there are the same 10 (+100) ie. 111, 122.. 199, 200 plus anything else with a 1 in the second digit, 110, 112...119 (another 9) plus anything with a 1 in the third digit: 101, 121, 131..191 (another 9). So I get 2(10) +2(9) = 38 It's not pretty, but that seems to be it.

  9. Jan 19, 2005 #8


    User Avatar
    Homework Helper

    Let's say the copied book is called A. There are 10 copies of A, all indistinguishable.

    The other books are numbered {1,2,3....10}. Let's call this set S. The number of ways of selecting r books from the 10 in S = [itex]10C_r[/itex]

    Let's list the possible selections (order of picking doesn't matter) :

    Selection 1 : 0 copies of A plus CHOOSE 10 (that is pick all 10) from set S ; no of possible ways = [itex]10C_{10}[/itex]

    Selection 2 : 1 copy of A plus CHOOSE 9 from set S ; no of possible ways = [itex]10C_9[/itex]

    Selection 3 : 2 copies of A plus CHOOSE 8 from set S ; no of possible ways = [itex]10C_8[/itex]


    Selection 10 : 10 copies of A plus CHOOSE zero (that is pick none) from set S ; no of possible ways = [itex]10C_0[/itex]

    Add that up, you get total no of selections N given by :

    [tex]N = 10C_0 + 10C_1 +... 10C_{10}[/tex]

    Compare that to the binomial theorem expansion of [itex](1+x)^{10}[/itex], put x = 1 and you have your answer. :smile:
    Last edited: Jan 19, 2005
  10. Jan 19, 2005 #9


    User Avatar
    Homework Helper

    For 3 digits, wouldn't it be 9*8. (first digit is 1. second digit is anything from 0-9 exept 1 so that leaves 10-1=9 possibilities for the second digit. third digit is anything from 0-9 except 1 and whatever the second digit is so that leaves 10-1-1=8).

    So I get 5+81+72=158.

    Let me know if you see a mistake in my reasoning.
  11. Jan 19, 2005 #10
    I do not think I understand what you mean here. Could you explain it for me please?

    What I did is set up an n by m matrix. So there are n rows and m columns in this matrix. now for each element of X there can be only one element from Y. So for row one there are m choices for the first element of X. For the second row there are m choices for the second element of X. But for each ordered pair from the first element of X there can be a different function depending on what the second element of X maps to. So I reason there are m*m*...*m or m^n possible functions. What do you think?

    Last edited: Jan 19, 2005
  12. Jan 19, 2005 #11
    No...yours looks right. My mistake.

    Thanks everyone who helped me out.

    Much appericated, and best regards
    Last edited: Jan 19, 2005
  13. Jan 19, 2005 #12
    Oh,,, my mistake... I meant to say Permutations not Combinations... this gives the same answer as what you got, m^n.... Sorry for the confusion
    I updated the original post...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook