n is an integer. When n tends to positive infinity, what is the relationship between n^n and n!?

The relationship is that \( n^n \) grows asymptotically faster than \( n! \) by an exponential factor. More precisely, as \( n \) tends to positive infinity, \( n! \) is negligible compared to \( n^n \), with the ratio \( \frac{n!}{n^n} \) tending to zero. This can be rigorously established using Stirling's approximation for the factorial, which provides the asymptotic formula \( n! \sim \sqrt{2\pi n} \left( \frac{n}{e} \right)^n \). Substituting this into the ratio yields \( \frac{n!}{n^n} \sim \frac{\sqrt{2\pi n} \left( \frac{n}{e} \right)^n}{n^n} = \frac{\sqrt{2\pi n}}{e^n} \), which clearly decays to zero because the denominator \( e^n \) grows exponentially while the numerator grows only with the square root of \( n \). This dominant exponential term in the denominator is the key mechanism driving the limit to zero, confirming that \( n^n \) is an upper bound that is vastly larger for large \( n \).

A more elementary approach, without invoking Stirling's formula, is to directly analyze the ratio \( \frac{n!}{n^n} \). This ratio can be expanded as \( \frac{1}{n} \cdot \frac{2}{n} \cdot \frac{3}{n} \cdots \frac{n}{n} \). Each term in this product is less than or equal to 1, and for \( k \leq n-1 \), the terms \( \frac{k}{n} \) are strictly less than 1. The product is therefore bounded above by 1 and decreases as \( n \) increases. To show it tends to zero, one can note that at least half of the terms (for \( k \leq \frac{n}{2} \)) are less than or equal to \( \frac{1}{2} \), providing a crude bound of \( \left( \frac{1}{2} \right)^{n/2} \) which tends to zero. A tighter bound reinforces the conclusion that the decay is at least exponential, aligning with the asymptotic result from Stirling.

The implications of this relationship are significant in combinatorics, probability, and algorithm analysis. For instance, \( n^n \) counts the total number of functions from a set of \( n \) elements to itself, while \( n! \) counts only the bijections (permutations). The asymptotic dominance of \( n^n \) reflects the intuitive fact that permutations become an exceedingly rare subset of all functions as \( n \) grows. In computational contexts, algorithms with factorial complexity are intractable for large \( n \), but those with \( n^n \) complexity are even more catastrophically inefficient, highlighting the dramatic difference in growth rates. This asymptotic hierarchy also informs the analysis of series convergence and the application of ratio tests where such terms appear.

Therefore, the definitive relationship is that \( n^n \) grows super-exponentially relative to \( n! \), with \( \lim_{n \to \infty} \frac{n!}{n^n} = 0 \). This establishes that \( n! = o(n^n) \) in little-o notation, meaning \( n! \) is of a strictly lower order of growth. No tighter constant bound exists for the ratio, as the decay is driven by the factor \( e^{-n} \) from Stirling's approximation. This result is foundational, often serving as a benchmark for comparing growth rates of combinatorial functions and sequences in mathematical analysis.