Upper bounding n choose k

We want to show that for 1\leq k\leq n, the following holds: {n\choose k} \leq \Big(\frac{n\cdot e}{k}\Big)^k.

First, recall the power series e^k=\sum_{i=0}^\infty{\frac{k^i}{i!}}. For k \geq 1, this sum is definitely larger than its kth term only. In other words, e^k \geq k^k/k!, which implies k! \geq (k/e)^k. Now,

\begin{matrix}{n\choose k}  &=& \frac{n!}{k! \cdot (n-k)!}\\  &=& \frac{n(n-1)(n-2)\cdots (n-(k-1))}{k!}\\  &\leq& \frac{n^k}{k!} \\  &\leq& \frac{n^k}{(k/e)^k} \\  &=& (\frac{en}{k})^k.\\  \end{matrix}

This proof is extracted from the StackExchange discussion here. For more inequalities/bounds for binomial coefficients, see Wikipedia.

Advertisements

Stirling Numbers of First and Second Kind: A Combinatorial Explanation of the Recursive Definitions

Stirling Numbers (of the first and second kind) are famous in combinatorics. There are well known recursive formulas for them, and they can be expressed through generating functions. Below we mention and explain the recursive definitions of the Stirling numbers through combinatorial ideas.

Since the Stirling numbers of the second kind are more intuitive, we will start with them.

Continue reading “Stirling Numbers of First and Second Kind: A Combinatorial Explanation of the Recursive Definitions”