1. ## 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}

2. ## 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?

3. 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.

4. Originally Posted by noles2188
question:
a) Show that there are n! linear orderings of {1, 2,...,n}
There are $\displaystyle (n!)$ permutations on {1, 2,...,n}.
If $\displaystyle \sigma :\left\{ {1,2, \cdots ,n} \right\} \leftrightarrow \left\{ {1,2, \cdots ,n} \right\}$ is such a permutation the define a relation as follows:
$\displaystyle jRk\mbox{ if and only if }\sigma ^{ - 1} (j) \leqslant \sigma ^{ - 1} (k)$.
Can you show that $\displaystyle R$ linear orderings of {1, 2,...,n}?
If so there are at least how many linear orderings of {1, 2,...,n} are there?