Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - Two Enumeration Questions

  1. #1
    Junior Member
    Joined
    Nov 2010
    Posts
    40

    Two Enumeration Questions

    1. Find an enumeration of the set of all odd integers
    I know x/2 when x is even and -(x+1)/2 when x is odd represent natural numbers I just cannot turn this into odd numbers only.

    when x is even the numbers I need are {2,6,10,14...}
    when x is odd the numbers are {1,5,9,13...}

    each are separated by 4 but when put together {1,2,5,6,9,10,13,14,...} I cannot find something that works like this.

    2. Find an enumeration of the set of all rational numbers that have a terminating decimal representation.
    (E.g. 17=10 = 1:7 and 17=8 = 2:125 are in this set, but 17=9 = 1:88888 : : : is
    not.)
    I'm not sure how to do this one
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Quote Originally Posted by gutnedawg View Post
    1. Find an enumeration of the set of all odd integers
    I know x/2 when x is even and -(x+1)/2 when x is odd represent natural numbers I just cannot turn this into odd numbers only.

    when x is even the numbers I need are {2,6,10,14...}
    when x is odd the numbers are {1,5,9,13...}

    each are separated by 4 but when put together {1,2,5,6,9,10,13,14,...} I cannot find something that works like this.
    Do you know an enumeration for all integers?
    Do you know a bijection from integers to odd integers?

    Compose these two and you have an enumeration for odd integers.

    2. Find an enumeration of the set of all rational numbers that have a terminating decimal representation.
    (E.g. 17=10 = 1:7 and 17=8 = 2:125 are in this set, but 17=9 = 1:88888 : : : is
    not.)
    I'm not sure how to do this one
    Do you know the enumeration for pairs of natural numbers \mathbb N \times \mathbb N?
    Find the bijection between paris of natural numbers and terminating decimals.
    Again, compose
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    1. Find an enumeration of the set of all odd integers
    Does this mean to find a surjection from \mathbb{N} to \{n\in\mathbb{Z}\mid\text{n is even}\}? Does f have to be an injection?

    I know x/2 when x is even and -(x+1)/2 when x is odd represent natural numbers
    I am not sure why you have - before (x+1)/2. The number -(x+1)/2 is not always natural when x is an odd integer, and it is never natural when x is an odd natural number.

    when x is even the numbers I need are {2,6,10,14...}
    when x is odd the numbers are {1,5,9,13...}

    each are separated by 4 but when put together {1,2,5,6,9,10,13,14,...}
    What does {1,2,5,6,9,10,13,14,...} have to do with odd integers, for which you need to find an enumeration? Why do you "need" {2,6,10,14...} and {1,5,9,13...}?

    2. Find an enumeration of the set of all rational numbers that have a terminating decimal representation.
    (E.g. 17=10 = 1:7 and 17=8 = 2:125 are in this set
    It's pretty hard to understand this. 17 is not equal to 10 and neither is 10 to 1:7. Also, 1/7 gives a nonterminating decimal representation 0.142857142...

    Hint from Wikipedia: "Terminating decimals represent rational numbers of the form k/(2^n5^m)."
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    Quote Originally Posted by snowtea View Post
    Do you know an enumeration for all integers?
    Do you know a bijection from integers to odd integers?

    Compose these two and you have an enumeration for odd integers.
    I'm not sure how to enumerate the negative numbers. An enumeration for odd positive numbers would be 2x+1 correct?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Quote Originally Posted by gutnedawg View Post
    I'm not sure how to enumerate the negative numbers. An enumeration for odd positive numbers would be 2x+1 correct?
    That's correct. Composing as snowtea said will give the following enumeration:

    1,-1,3,-3,5,-5,...
    Last edited by DrSteve; January 13th 2011 at 01:05 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    so how do I 'compose' the enumeration and bijection? The enumeration is x/2 if x is even and -(x+1)/2 if x is odd and the bijection is 2x+1... I just don't get how to describe the nth term of the enumeration
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    When you substitute x/2 into 2x+1, you get 2(x/2)+1=x+1. When you substitute -(x+1)/2 into 2x+1 you get 2[-(x+1)/2+1=-x-1+1=-x
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    ah ok this makes sense... so my nth term would be x+1 if x is even and -x if x is odd and this is the correct final answer yes?
    Thanks

    I do no know the enumeration for pairs of natural numbers so I'm somewhat stuck here.... I guess I need some further explanation
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Yes - that's correct.


    I think the idea behind the way to do the second one being suggested is the following:

    You can think of any positive rational number that terminates as a.b where a and b are natural numbers. Now use snowpea's idea, together with the usual trick (as we've been discussing) to get the negatives as well.

    (I don't remember off the top of my head an explicit bijection between natural numbers and pairs of natural numbers, but you should be able to find one easily with an internet search for "pairing function").

    Be aware that these solutions are far from unique. There are lots of ways to do enumeration problems.


    By the way, we've all been giving you hints to produce explicit functions that give bijections. It's not clear from the way you've written the questions that this is necessary. If you only have to "show the list" (as I did in my first post), then we can answer these questions much more quickly and easily.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    so if I'm correct I should have some function f(x,y) = x.y ... or should it be (x/2).y when x is even and [-(x+1)/2].y when x is odd
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1
    Quote Originally Posted by DrSteve View Post
    (I don't remember off the top of my head an explicit bijection between natural numbers and pairs of natural numbers, but you should be able to find one easily with an internet search for "pairing function").
    Let \Phi:\mathbb{Z}^+\times\mathbb{Z}^+ \to\mathbb{Z}^+ defined by \Phi(m,n)=2^{m-1}(2n-1).
    That is a bijection.
    Easily extended to all rationals.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    That's the idea but not quite. Your final function will be a function of one variable. The domain is the set of natural numbers and the range is a subset of the rational numbers. You're going to compose as follows:

    \mathbb{N}\rightarrow \mathbb{N}\times \mathbb{N}\rightarrow \mathbb{Z}\times \mathbb{N}\rightarrow \mathbb{Q}.

    The first is the pairing function. The second is the map (a,b)\rightarrow (f(a),b) where f is the function we've previously discussed, and the third is the map (a,b)\rightarrow a.b.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    I am asked to find the enumeration but I have to specify the nth term of the enumeration
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    so is f(a) the a/2 if a is even and -(a+1)/2 if a is odd? Then how do I map these to a.b?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    f(a).b
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Enumeration question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2009, 08:21 PM
  2. Enumeration question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 14th 2009, 08:34 PM
  3. Clarification on enumeration
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 10th 2009, 09:38 PM
  4. Enumeration problem
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: September 17th 2008, 05:52 AM
  5. enumeration
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 23rd 2005, 03:54 PM

Search Tags


/mathhelpforum @mathhelpforum