### Categories

### Recent Comments

- tpc on Mathematics and poetry
- tpc on Discovery
- tpc on Dear Maurits
- Twin corrections | eon on Mathematics and Coffee
- tpc on Prime (Car) Number

### Links

### Archives

- August 2018
- July 2018
- June 2018
- December 2017
- November 2017
- August 2017
- May 2017
- April 2017
- March 2017
- October 2016
- September 2016
- August 2016
- July 2016
- December 2015
- October 2015
- September 2015
- August 2015
- June 2015
- March 2015
- February 2015
- January 2015
- August 2014
- July 2014
- June 2014
- April 2014
- March 2014
- January 2014
- November 2013
- October 2013
- September 2013
- August 2013
- July 2013
- June 2013
- May 2013
- April 2013
- February 2013
- January 2013
- December 2012
- November 2012
- October 2012
- September 2012
- August 2012
- July 2012
- June 2012
- May 2012
- March 2012
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
- September 2011
- August 2011
- July 2011
- June 2011
- May 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009
- December 2008
- November 2008
- October 2008
- September 2008
- June 2008
- May 2008
- April 2008
- March 2008
- January 2008
- December 2007
- November 2007
- August 2007
- July 2007
- June 2007
- May 2007
- April 2007
- March 2007
- February 2007
- January 2007
- December 2006
- November 2006
- October 2006
- September 2006
- August 2006
- July 2006
- June 2006
- May 2006
- April 2006
- March 2006
- February 2006
- January 2006
- December 2005
- November 2005
- September 2005
- August 2005
- July 2005
- June 2005
- May 2005
- April 2005
- March 2005
- February 2005
- January 2005
- December 2004
- November 2004

### Meta

# 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