You are currently browsing the category archive for the ‘Combinatorics’ category.

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.

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.

Read the rest of this entry »

Proofs from the Book

Proofs from the Book

This book, inspired from Paul Erdős‘ notion of the Book, presents some beautiful proofs to some intriguing math problems. Both the problems and proofs presented here are elegant, clear, and artistic.