Category Archives: Combinatorics

Binomial identity and probability

The identity $\displaystyle \sum k \binom{n}{k} = n 2^{n-1}$ is pretty standard, and one can prove it algebraically by cancelling the k in the sum with the binomial coefficient and then using the binomial theorem summation or a combinatorial … Continue reading

Double Factorial

Using the double factorial notation to denote the following $\displaystyle n!! = \prod_{i=0}^{\lfloor \frac{n-1}{2} \rfloor} (n-2i)$ seems pretty standard. (See Wolfram and Wiki.) So $4!! = 4 \times 2 = 8$ but $(4!)! = 24!$. … Continue reading

Pascal’s triangle

Perhaps the most famous triangle of all. Take your calculator, and compute $11, 11^2, 11^3, 11^4$ … cute! Can you explain why? It’s so famous that there’s lots of information on the web about it. Named after Pascal but … Continue reading

Sicherman Dice

We all know the possible outcomes of throwing two usual six-sided dice. Have you ever wondered if there are other possible types of dice, i.e. still six-sided but with different face values, which gives the same outcome? The answer is … Continue reading

Posted in Combinatorics, Probability | 4 Comments

Lyness

Intrigued by the following very pretty combinatorial identity attributed to R.C. Lyness. $\sum_{r=0}^n \binom{n}{r} \binom{p}{s+r} \binom{q+r}{m+n} = \sum_{r=0}^n \binom{n}{r} \binom{q}{m+r} \binom{p+r}{s+n}$ Note how it interchanges p with q and m with s. Not much information on this person is … Continue reading

Learned a cool trick today. The finite projective plane of order n has $n^2 + n + 1$ points, $n^2 + n + 1$ lines, $n + 1$ points on each line, $n + 1$ lines passing each point. The … Continue reading