 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2008/b/5/a/i/solution

For

k \geq 1

, monotonicity of the logarithm gives

lo g (k!) = \sum_{j = 1}^{k} lo g j \geq \int_{1}^{k} lo g t d t = k lo g k - k + 1 \geq k lo g k - k .

Thus

k! \geq (k / e)^{k}

n^{k}

yields

(k n) \leq \frac{n ^{k}}{k !} \leq (e n / k)^{k} .

 New to topics? Read the docs here!