Results 1 to 10 of 10

Math Help - Couting Questions

  1. #1
    Newbie
    Joined
    Jan 2008
    Posts
    15

    Couting Questions

    Hi all,

    I have a couple of questions regarding counting, so it will be fantastic if you can help me out. Thanks in advance!

    Qns 1:
    Consider strings of length n over the set {a,b,c,d}. How many such strings contain at least one pair of adjacent characters that are the same?

    My comments:
    By adjacent do they mean (a,b) in length n, etc? Is the combination (b,a) allowed or equivalent to (a,b)?

    Qns 2:
    How many integers from 1 through 999999 contain each of the digits 1,2 and 3 at least once? (Hint: For each i let A_{i} be the set of integers from 1 through 999999 that do not contain the digit i)

    My comments:
    The solution asked me to use the inclusion and exclusion method, so how do i know when to use this?

    Qns 3:
    If n=p_{1}p_{2}p_{3}p_{4}p_{5} where p_{i} are distinct primes, in how many ways can n be expressed as a product of 2 positive integers? (n=ab and n=ba are considered the same)
    What is the answer if n=p_{1}p_{2}...p_{k}?

    My comments:
    From the solution, they mentioned the number of ways to choose a is 2^{5} which i understand. It is stated that "it is a duplication by a factor of 2 since p_{1}p_{2} and p_{3}p_{4}p_{5} both appear as subsets but they give the same factorisation". I do not understand where the duplication is, can somehow show me an example?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,678
    Thanks
    610
    Hello, shaoen01!

    3) If n=p_1p_2p_3p_4p_5 where p_i are distinct primes,
    In how many ways can n be expressed as a product of 2 positive integers?
    ( n=ab\text{ and }n=ba are considered the same)

    What is the answer if n=p_1p_2\hdots p_k?

    My comments:
    From the solution, they mentioned the number of ways to choose a is 2^{5} which i understand.
    It is stated that "it is a duplication by a factor of 2 since p_{1}p_{2} and p_{3}p_{4}p_{5} both appear
    as subsets but they give the same factorisation".

    I do not understand where the duplication is.
    Can somehow show me an example?

    Suppose n \:=\:30 \:=\:2\cdot3\cdot5

    With three factors to choose from, there are: 2^3 = {\bf8} possible subsets.

    They are: . \{\;\},\;\{2\},\;\{3\},\;\{5\},\;\{2,3\},\;\{3,5\}  ,\;\{2,5\},\;\{2,3,5\}

    But the question is: how many two-set partitions are there?

    There are four: . \begin{array}{cc}\{\;\} &\{2,3,5\} \\ \{2\} & \{3,5\} \\ \{3\} & \{2,5\} \\ \{5\} & \{2,3\} \end{array}\quad \text{ The products are: }\begin{Bmatrix}1\cdot30 \\ 2\cdot15 \\ 3\cdot10 \\ 5\cdot6\end{Bmatrix}

    The partition \{2\}\;\;\{3,5\} is the same as \{3,5\}\;\;\{2\}
    . . because 2\cdot15\text{ and }15\cdot2 are the same factoring.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by shaoen01 View Post
    Qns 1:
    Consider strings of length n over the set {a,b,c,d}. How many such strings contain at least one pair of adjacent characters that are the same?
    My comments:
    By adjacent do they mean (a,b) in length n, etc? Is the combination (b,a) allowed or equivalent to (a,b)?

    Qns 2:
    How many integers from 1 through 999999 contain each of the digits 1,2 and 3 at least once? (Hint: For each i let A_{i} be the set of integers from 1 through 999999 that do not contain the digit i
    I have no gotten a clear model for question #1. But I think that it is clear that you would allow neither ‘ab’ nor ‘ba’. I am pretty sure that one counts these with recursion.

    Question #2 is lengthy but straightforward.
    If T=999999 is the total number then we need to remove <br />
\left( {A_1  \cup A_2  \cup A_3 } \right), that is removing any number that fails to contain a 1, 2, or 3.
    You know that:
    \# \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_3  \cap A_2 } \right) + \# \left( {A_1  \cap A_2  \cap A_3 } \right).

    I will help with one of those: \# \left( {A_1  \cap A_2 } \right) = 8^6  - 1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2008
    Posts
    15
    Quote Originally Posted by Soroban View Post
    Hello, shaoen01!


    Suppose n \:=\:30 \:=\:2\cdot3\cdot5

    With three factors to choose from, there are: 2^3 = {\bf8} possible subsets.

    They are: . \{\;\},\;\{2\},\;\{3\},\;\{5\},\;\{2,3\},\;\{3,5\}  ,\;\{2,5\},\;\{2,3,5\}

    But the question is: how many two-set partitions are there?

    There are four: . \begin{array}{cc}\{\;\} &\{2,3,5\} \\ \{2\} & \{3,5\} \\ \{3\} & \{2,5\} \\ \{5\} & \{2,3\} \end{array}\quad \text{ The products are: }\begin{Bmatrix}1\cdot30 \\ 2\cdot15 \\ 3\cdot10 \\ 5\cdot6\end{Bmatrix}

    The partition \{2\}\;\;\{3,5\} is the same as \{3,5\}\;\;\{2\}
    . . because 2\cdot15\text{ and }15\cdot2 are the same factoring.

    Hi Soroban:

    Thank you for your reply. So for example, 3x10 is also equivalent to 10x3 right? So this kind of repeated value is not allowed. If i use your example, i can't seem to get the answer of 2^{4}=16. And must n=p_{1}p_{2}p_{3}p_{4}p_{5} be consecutive values? For example, 1 to 5?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2008
    Posts
    15
    Quote Originally Posted by Plato View Post
    I have no gotten a clear model for question #1. But I think that it is clear that you would allow neither ‘ab’ nor ‘ba’. I am pretty sure that one counts these with recursion.

    Question #2 is lengthy but straightforward.
    If T=999999 is the total number then we need to remove <br />
\left( {A_1  \cup A_2  \cup A_3 } \right), that is removing any number that fails to contain a 1, 2, or 3.
    You know that:
    \# \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_3  \cap A_2 } \right) + \# \left( {A_1  \cap A_2  \cap A_3 } \right).

    I will help with one of those: \# \left( {A_1  \cap A_2 } \right) = 8^6  - 1.
    Hi Plato:

    Thank you for your reply.
    Qns 1:
    Should i use the unordered and no repetition method to calculate this? Do you have any clues or hints to give me?

    Qns 2:
    But i am curious to know how did you get the value <br />
\left( {A_1 \cap A_2 } \right) = 8^6 - 1<br />
. I do know the inclusion/exclusion rule you written above, the thing is i do not know how to get the value like how you did.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by shaoen01 View Post
    I do not know how to get the value like how you did.
    The set A_1 is the set of all integers 1 to 999999 that do not contain the digit 1. Because we can only use \left\{ {0,2,3,4,5,6,7,8,9} \right\} there 9^6-1 numbers in A_1 , we subtract the 1 to account for 000000000.
    Last edited by Plato; March 23rd 2008 at 05:55 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,678
    Thanks
    610
    Hello, shaoen01!

    Plato's approach to #2 is correct . . .
    I would further assume that an integer does not begin with zero.


    2) How many integers from 1 through 999999
    contain each of the digits 1,2 and 3 at least once?

    My comments:
    The solution asked me to use the inclusion-exclusion method,
    so how do i know when to use this?

    It is used when counting the items which are not in the set
    is easier than counting the items that are in the set.
    There are 999,999 integers.
    How many do not contain at least {1,2,3} ?

    Let n(i') = number of integers that do not contain an i.

    We want:
    n(1' \,\cup \,2' \,\cup \,3') \;=\;n(1') \,+\, n(2') \,+ \,n(3') \,-\, n(1' \,\cap \,2') \,- \,n(2' \,\cap \,3') \,- \,n(1' \,\cap \,3') \,+ n(1' \cap 2' \cap 3')



    Consider n(1')

    1-digit numbers: 8 choices . (It must not be 0 or 1.)
    2-digit numbers: 8\cdot9 choices.
    3-digit numbers: 8\cdot9^2 choices.
    4-digit numbers: 8\cdot9^3 choices.
    5-digit numbers: 8\cdot9^4 choices.
    6-digit numbers: 8\cdot9^5 choices.

    There are: . 8(1 + 9 + 9^2 + \hdots + 9^5) \;=\;8\,\frac{9^5-1}{9-1} \;=\;59,048 such numbers.

    The same reasoning holds for n(2')\text{ and }n(3')

    . . Hence: . n(1') \:=\:n(2') \:=\:n(3') \:=\:59,048



    Consider n(1' \cap 2')

    1-digit numbers: 7 choices. .(It must not be 0, 1, or 2.)
    2-digit numbers: 7\cdot8 choices.
    3-digit numbers: 7\cdot8^2 choices.
    4-digit numbers: 7\cdot8^3 choices.
    5-digit numbers: 7\cdot8^4 choices.
    6-digit numbers: 7\cdot8^5 choices.

    There are: . 7(1 + 8 + 8^2 +\hdots+8^5) \:=\:7\,\frac{8^5-1}{8-1} \:=\:32,767 such numbers.

    The same reasoning holds for n(2'\cap3')\text{ and }n(1'\cap3')

    . . Hence: . n(1'\cap2') \:=\:n(2' \cap 3') \:=\:n(1' \cap 3') \:=\:32,767



    Consider n(1' \cap 2' \cap 3')

    1-digit numbers: 6 choices. .(It must not be 0, 1, 2, or 3.)
    2-digit numbers: 6\cdot7 choices.
    3-digit numbers: 6\cdot7^2 choices.
    4-digit numbers: 6\cdot7^3 choices.
    5-digit numbers: 6\cdot7^4 choices.
    6-digit numbers: 6\cdot7^5 choices.

    There are: . 6(1 + 7 + 7^2 + \hdots + 7^5) \:=\:6\,\frac{7^5-1}{7-1} \:=\:16,806 such numbers.

    . . Hence: . n(1' \cap 2' \cap 3') \:=\:16,806



    Then: . n(1' \cup 2' \cup 3') \:=\:3(59,048) - 3(32,767) + 16,806 \:=\:95,649


    Therefore: . n(1 \cap 2\cap 3) \;=\;999,999 - 95,649 \;=\;\boxed{904,350}



    But check my work and my reasoning . . . please!
    .
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by Soroban View Post
    I would further assume that an integer does not begin with zero. But check my work and my reasoning . . . please!
    But in the case "assume that an integer does not begin with zero", how would account for 234?
    That contains no 1's but has the form 000234.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by shaoen01 View Post
    Qns 1:
    Consider strings of length n over the set {a,b,c,d}. How many such strings contain at least one pair of adjacent characters that are the same?

    My comments:
    By adjacent do they mean (a,b) in length n, etc? Is the combination (b,a) allowed or equivalent to (a,b)?
    I take this to mean that they are looking for strings of n letters (each letter being a, b, c or d) in which the same letter occurs twice in succession somehwere in the string. So for example if n=6 then caddba would be allowed (because there are two adjacent d's), but cadbcd would not (because the same letter never appears twice in succession)

    If that interpretation of the question is correct, then the answer is quite easy. There are 4^n possible strings altogether, but 4\times3^{n-1} of these are not allowed. (For a string not to be allowed, its first letter can be any one of the four, but each subsequent letter must be different from its predecessor, so there are only three choices for it.) Thus the number of allowable strings is 4(4^{n-1} - 3^{n-1}).
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Soroban View Post
    There are: . 8(1 + 9 + 9^2 + \hdots + 9^5) \;=\;8\,\frac{9^5-1}{9-1} \;=\;59,048 such numbers.
    Bit of slippage here, I think! It should be 8\,\frac{9^{\textstyle\mathbf6}-1}{9-1} \;=\;531440 (and similarly for the other two summations).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. high/low card couting system
    Posted in the Statistics Forum
    Replies: 0
    Last Post: October 29th 2008, 04:46 PM
  2. Replies: 4
    Last Post: July 19th 2008, 07:18 PM
  3. Couting and probability
    Posted in the Statistics Forum
    Replies: 2
    Last Post: March 26th 2008, 08:44 PM
  4. Couting Techniques
    Posted in the Statistics Forum
    Replies: 3
    Last Post: March 8th 2008, 09:42 AM
  5. Replies: 3
    Last Post: August 1st 2005, 01:53 AM

Search Tags


/mathhelpforum @mathhelpforum