Categories
Recent Comments
- Anthony C. Lanni on A Calendar Puzzle
- Luis on Polya and Ramanujan
- Chris on Picture Hanging Puzzle
- lakesh kumar ravi on An application of quadratic residues
- tpc on Magic formula
Links
Archives
- 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
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