Welcome to MathOverflow

Question

6

4

There are short and sweet proofs of various forms of Stirling's approximation. But even the sweetest among them don't instill the same conviction in the reader as a direct bijective proof.

Computer scientists can often get away with a very weak form of Stirling's approximation:

$$(n/2)^{n/2} \leq n! \leq n^n$$

From this follows

$$(n/2)\ log(n) - (n/2)\ log(2) \leq log(n!) \leq n\ log(n)$$

and therefore $log(n!) = \Theta(n\ log(n))$. This is sufficient to establish the lower bound on comparison-based sorting algorithms and many other asymptotic bounds.

Does anyone know a natural bijective proof of $(n/2)^{n/2} \leq n! \leq n^n$?

flag	asked Aug 2 2010 at 4:40 Per Vognsen 1,041●5●15

Why it's important to have a bijective proof?! I would be very happy to hear some motivation. Any way, if you wish to have some combinatorics involved, you should clarify how to interpret $(n/2)^{n/2}$ for $n$ odd. – Wadim Zudilin Aug 2 2010 at 5:31

For $n$ even, $n/2$ of the factors of $n!$ are at least $n/2$. So, the natural interpretation for $n$ odd is to round down $n/2$. But I would be happy with a bijective proof that only directly encompasses the even case. As for why I want a bijective proof? The usual reason of wanting to see the underlying combinatorial structure. – Per Vognsen Aug 2 2010 at 5:39

For a stronger lower bound which implies yours, see mathoverflow.net/questions/27912/… . – Wadim Zudilin Aug 2 2010 at 5:40

1

By the way, maybe I should mention my original intuition that the lower bound should have something to do with the existence of fixed-point-free involutions on sets of even cardinality. – Per Vognsen Aug 2 2010 at 5:56

Btw, as to elementary forms of the Stirling inequality, note also $e^n\geq \frac{n^n}{n!}$ from the exponential series. – Pietro Majer Aug 2 2010 at 8:00

Igor Pak · Accepted Answer · 2010-08-02 08:45:42Z UTC

6

Think of all maps from the first $n/2$ elements of {$1,...,n$} to the last $n/2$. Say, let $a_1< \ldots < a_k \to z$. Make a cycle $a_1 \to a_2 \to \ldots \to a_k \to z \to a_1$. Do this for all $z$. The details are straightforward. This proves the lower bound.

answered Aug 2 2010 at 8:45

Igor Pak
8,206●2●17●57

Beautiful. Thanks! This also works in the odd $n$ case by fixing the median element. – Per Vognsen Aug 2 2010 at 8:57

Aaron Meyerowitz · Answer 2 · 2010-08-02 05:12:29Z UTC

2

n! counts one-to-one functions from {1,2,...,n} to itself while $n^n$ counts all such functions. For a bijective proof of the lower bound one would likely want n=2m, Then the lower number is the $m^m$ functions g from {1,...,m} to itself . I thought I had an easy bijection to a class of partial one-to-one functions but the on I had isn't right...

edited Aug 2 2010 at 5:12

answered Aug 2 2010 at 5:06

Aaron Meyerowitz
11.6k●1●10●31

	Yeah, the upper bound poses no problem. I too have had a couple of false starts on a bijective proof of the lower bound, so I'm sympathetic to your mistake. :) – Per Vognsen Aug 2 2010 at 5:19
	OK, its not so pretty but one-to-one functions from {1,...,m} to {1,...,n} number n(n-1)...*(m+1) and all m terms are greater than m. So take any of the m^m functions g from {1..m} to itself and make a function f by assigning in turn f(1),f(2),... where f(i) is the g(i)th in order from the things not already assigned. – Aaron Meyerowitz Aug 2 2010 at 5:32

Bijective proof of weak form of Stirling’s approximation

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.