# Category Archives: Combinatorics

## Catalan numbers

I really enjoyed reading Federico Ardila’s article in the Mathematical Intelligencer. Apparently there was a vote of 3030 members at an assembly of CUP (Not Cambridge University Press but the Candidatura d’Unitat Popular). The vote had to do with forming … Continue reading

## two thousand years of combinatorics

by Don Knuth is the opening chapter to Combinatorics:Ancient & Modern, which according to its preface is perhaps the first book-length survey of the history of combinatorics. Knuth’s chapter is actually taken from his Art of Computer Programming Volume 4 … Continue reading

## A combinatorialist worth his salt

Just as every analyst automatically interchanges the order of integration, and every combinatorialist worth his salt double counts at the drop of a hat, Erdös was constantly on the lookout for opportunities to apply the probabilistic method. [emphasis mine] Taken … Continue reading

## 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