Thread: 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}

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?

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.

Originally Posted by noles2188

question:
a) Show that there are n! linear orderings of {1, 2,...,n}

There are permutations on {1, 2,...,n}.
If is such a permutation the define a relation as follows:
.
Can you show that linear orderings of {1, 2,...,n}?
If so there are at least how many linear orderings of {1, 2,...,n} are there?