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

Posted in Combinatorics, Fun Stuff, Quotes/People | Leave a comment

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

Posted in Books, Combinatorics | Leave a comment

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

Posted in Combinatorics, Quotes/People | Leave a comment

Another binomial sum

Came across an interesting problem Brent Yorgey from his blog The Math Less Traveled. In this post he tried to explain what is meant by a combinatorial proof to prepare his readers for a proof of this identity [tex] \displaystyle … Continue reading

Posted in Combinatorics | Leave a comment

An AMC problem on sieveing primes

The following is an AMC 12 problem from 2005, courtesy of the MAA Minute Math. Follow the link for an interactive version complete with hints, solutions and difficulty hosted on MAA.org. Problem: Call a number “prime-looking” if it is composite … Continue reading

Posted in Combinatorics, Number Theory, Problems | Leave a comment

A dicey past year exam question

A die consists of six faces with each face representing precisely one of the numbers 1, 2, 3, 4, 5, 6. Suppose that n such dice are rolled for some positive integer n. The number of the upper face of … Continue reading

Posted in Combinatorics, Problems | Leave a comment

Modelling with exponential generating functions

Let [tex] a_n[/tex] be the number of ways to distribute n distinct objects to four distinct boxes, such that the total objects is even. Find the exponential generating function. Either all four boxes have even number of objects, or exactly … Continue reading

Posted in Combinatorics, Problems | Leave a comment

A nonlinear first order recurrence relation

Mr Ding! asked me the following question from Bona’s textbook. Question 6 of supplementary exercises in chapter 3. [tex] a_n = (n+1) a_{n-1} +3^n, a_0 = 1[/tex] My solution as follows. Let [tex]b_{n+1} = a_n [/tex]then [tex] b_{n+1} = (n+1) … Continue reading

Posted in Combinatorics, Problems | Leave a comment

Bell Numbers

defined as [tex] \displaystyle B(n) = \sum_{k=0}^n \left\{ {n \atop k}\right\}[/tex] counts the total number of ways to partition n distinct objects into disjoint subsets (or blocks) where [tex] \displaystyle \left\{ {n \atop k}\right\} [/tex] is the well known Stirling … Continue reading

Posted in Combinatorics, Fun Stuff | Leave a comment

Binomial identity and probability

The identity [tex]\displaystyle \sum k \binom{n}{k} = n 2^{n-1} [/tex] 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

Posted in Combinatorics, Probability | Leave a comment

Double Factorial

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

Posted in Combinatorics | Leave a comment

Pascal’s triangle

Perhaps the most famous triangle of all. Take your calculator, and compute [tex] 11, 11^2, 11^3, 11^4[/tex] … 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

Posted in Combinatorics | Leave a comment

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. [tex] \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}[/tex] Note how it interchanges p with q and m with s. Not much information on this person is … Continue reading

Posted in Combinatorics, Quotes/People, Teaching, Technology | Leave a comment

Finite Projective Plane

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

Posted in Combinatorics, Geometry/Topology | Leave a comment

A combinatorial identity

I came across the following identity today. [tex] \displaystyle{1 \choose k} + {2 \choose k} + \ldots + {99 \choose k} = {100 \choose k+1}[/tex] It is not exactly difficult to establish if one uses the Pascal relation repeatedly. [tex] … Continue reading

Posted in Combinatorics | 2 Comments

A Calendar Puzzle

A simple little puzzle. Suppose you are given two ordinary 6 sided dice. Is it possible to put the numbers 0-9 (with repetition) onto the faces of both dice, such that using both dice you can display all the days … Continue reading

Posted in Combinatorics, Fun Stuff, Problems | 10 Comments

Web Sudoku

I reached this link via Mathforge. What can I say, the game is addictive. My current record is 6 min for the easy game and I’ve yet to try the hard and 55 min for the evil level. Now, the … Continue reading

Posted in Combinatorics, Fun Stuff | Leave a comment

Cranks

in mathematics does not refer to eccentric old men (although there are many around) but refer to certain statistics related to partitions. The name probably came about because there is a related notion of ranks of partitions. This article in … Continue reading

Posted in Combinatorics, Number Theory | 1 Comment

Binomial Coefficients

[tex]{n \choose r}[/tex] is the number of ways of picking r objects out of n possibilities without order. A simple but elegant identity is this [tex] {n+1 \choose r }= {n \choose r} + {n \choose r-1}[/tex] which appears when … Continue reading

Posted in Combinatorics | Leave a comment