Results 1 to 4 of 4

Math Help - Linear Orderings

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    124

    Linear Orderings

    Two part question:
    a) Show that there are n! linear orderings of {1, 2,...,n}
    b) Show that n! lies between 2^{n-1} and 2^{n^2}
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2008
    Posts
    1

    DNE

    Hmmm, this is a tough one. However, I do not believe the statement in (a), "there are n! linear orderings of {1, 2,...,n}", is true. Why would you try to prove it so?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2008
    Posts
    124
    Is that the case, that you cannot prove this? The questions were given as a homework assignment, so I'm assuming that there is a way to prove this. It works when you do the arithmetic. For example, 2! = 2 and there are two ways to order 1 and 2: {1,2} and {2,1}. This is as far as I've gotten.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,711
    Thanks
    1640
    Awards
    1
    Quote Originally Posted by noles2188 View Post
    question:
    a) Show that there are n! linear orderings of {1, 2,...,n}
    There are (n!) permutations on {1, 2,...,n}.
    If \sigma :\left\{ {1,2, \cdots ,n} \right\} \leftrightarrow \left\{ {1,2, \cdots ,n} \right\} is such a permutation the define a relation as follows:
    jRk\mbox{ if and only if }\sigma ^{ - 1} (j) \leqslant \sigma ^{ - 1} (k).
    Can you show that R linear orderings of {1, 2,...,n}?
    If so there are at least how many linear orderings of {1, 2,...,n} are there?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Set Theory - Total vs Partial Orderings
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 12th 2011, 08:23 AM
  2. Replies: 7
    Last Post: October 10th 2011, 03:06 PM
  3. Compactness Theorem and partial orderings
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 2nd 2011, 12:35 PM
  4. Addition and Multiplication of Well Orderings
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 12:32 AM
  5. Equivalence Relations and Partial Orderings
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2007, 10:13 PM

Search Tags


/mathhelpforum @mathhelpforum