Results 1 to 8 of 8

Math Help - permutation/combination problem

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    76

    permutation/combination problem

    I'm really stuck on this problem.

    It says,how many numbers between 1 and 999,999 contains each of the digit 1,2 and 3 at least once.(Hint : for each i = 1,2,3 A_i be the set of all integers from 1 to 999,999 that do not contain the digit i)

    I really need help with this one.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie Arch_Stanton's Avatar
    Joined
    Nov 2008
    Posts
    21
    We have six digit-number* and we need to place in it digits 1, 2 and 3 in free order. We can do it in 6*5*4 ways, the remaining 3 places may include any digit, so it gives us 6*5*4*10*10*10 different numbers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1582
    Awards
    1
    We want to calculate 10^6 - 1 - \left| {A_1 \cup A_2 \cup A_3 } \right|.
    The minus 1 accounts for the 000000.

    Now \left| {A_1 \cup A_2 \cup A_3 } \right| = \left| {A_1 } \right| + \left| {A_2 } \right| + \left| {A_3 } \right| - \left| {A_1 \cap A_2 } \right| - \left| {A_1 \cap A_3 } \right| - \left| {A_2 \cap A_3 } \right| + \left| {A_1 \cap A_2 \cap A_3 } \right|.

    \left| {A_1 } \right| = 9^6 - 1\,,\,\left| {A_1 \cap A_2 } \right| = 8^6 - 1\,\& \,\left| {A_1 \cap A_2 \cap A_3 } \right| = 7^6 - 1.

    Can you put it all together?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2008
    Posts
    76
    Thanks for your help Plato.I only understand parts of it.Like,

    A(1) = the number of integers that contain a 1 as one of it's digit.

    A(2) = the number of integers that contain a as one of it's digit.
    and so is A(3).

    now A(1) = _ _ _ _ _ _

    and each of these blanks cna be filled with a any of the digits between 0 to 9
    i.e we have 10 choices

    so if it's 0 0 0 0 0 1
    0 1 9 9 4 5

    and so on
    so,A(1) has to have a digit 1 in it.

    _ _ _ _ _ _ = 1 * 10 * 10 * 10 * 10 * 10



    isn't it? how do u say it's 10 ^6 -1 then?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1582
    Awards
    1
    I was using the hint given in the problem.
    A_1 is the number of numbers from 1 to 999999 that have no 1ís.
    That is 9^6-1: you can use any of the other nine digits, subtract 1 to account for 000000.
    A_1 \cap A_2 is the number of numbers from 1 to 999999 that have no 1ís nor 2ís.
    That is 8^6 -1 so forth.
    The total number of numbers from 1 to 999999 is 10^6-1.

    Now use inclusion/exclusion to get what you want.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie Arch_Stanton's Avatar
    Joined
    Nov 2008
    Posts
    21
    Try shorter way: number xxxxxx has to include each of 1, 2 and 3 digits, they can be placed in V^3_6=120 different ways:
    xxx321
    xx3x21
    x3xx21
    3xxx21
    xxx231
    xx32x1
    x3x2x1
    3xx2x1
    xx2x31
    xx23x1
    ...
    1x32xx
    13x2xx
    1x2xx3
    1x2x3x
    1x23xx
    132xxx
    12xxx3
    12xx3x
    12x3xx
    123xxx
    Each x may be replaced by any other digit, so each of 120 different cases represent 10 different numbers, that's why we get
    V^3_6*10^3=4*5*6*10*10*10=120 000
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1582
    Awards
    1
    Quote Originally Posted by Arch_Stanton View Post
    Try shorter way: number xxxxxx has to include each of 1, 2 and 3 digits, they can be placed in V^3_6=120 different ways:
    Each x may be replaced by any other digit, so each of 120 different cases represent 10 different numbers, that's why we get V^3_6*10^3=4*5*6*10*10*10= \color{red}120 000
    That happens to be a great overcount.
    The correct answer is 74,460.
    In the reply above, the overcount comes by allowing any other digit to be used in each case.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie Arch_Stanton's Avatar
    Joined
    Nov 2008
    Posts
    21
    You're right, some numbers appear more than once.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combination and Permutation problem.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 2nd 2011, 08:58 PM
  2. Replies: 2
    Last Post: July 9th 2009, 02:14 PM
  3. Permutation/Combination Problem Help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 18th 2008, 08:32 PM
  4. Permutation and Combination problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 27th 2008, 07:29 PM
  5. Combination/Permutation problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 18th 2008, 10:15 AM

Search Tags


/mathhelpforum @mathhelpforum