"On Picture-Writing": An Introduction to Generating Functions

This group problem-solving and proof-detailing session will explore, in depth, the three questions posed in George Pólya's paper "On Picture-Writing" which provides an introductory treatment of the method of generating functions in combinatory analysis.

You can obtain free access to Pólya's paper with a free MyJSTOR account at http://www.jstor.org/stable/2309555

To find the paper in a library, consult The American Mathematical Monthly Vol. 63, No. 10, Dec., 1956, pp. 689-697.

Question 1: "In how many ways can you change a dollar?" In particular, let P(n) "denote the number of ways of paying the amount of n cents with five kinds of coins: cents, nickels, dimes, quarters, and half-dollars." Using the method of generating functions developed in the paper, prove that P(100)=292.

Question 2: "Dissect a convex polygon with n sides into n-2 triangles by n-3 diagonals and compute D(n), the number of different dissections of this kind." Using the method of generating functions developed in the paper, prove that for n≥3 D(n)=(-½)C(½,n-1)(-4)ⁿ⁻¹=(2·6·10···(4n-10))/(2·3·4···(n-1)) where C(x,n) is a generalized bionomial coefficient (see https://en.wikipedia.org/wiki/Binomial_coefficient).

Question 3: "Compute T(n), the number of different trees with n knots" where a tree is a connected graph of points and lines with no closed path. The root of the tree is a distinguished point that has just one line to it which is called the trunk. Any other point, besides the root, is called a knot. Compute the values of T(n) for 1≤n≤5 using the method of picture-writing developed in the paper.

Since this topic requires a mastery of the basic counting rules, those participants who want to strengthen their understanding of these rules may find my notes at https://plus.google.com/104222466367230914966/posts/TqtbKxzLVgz
helpful. They elaborate on this 9 minute Ma Yu Chun video http://www.youtube.com/watch?v=0pRIQFJksX4 (subtitles http://www.cjfearnley.com/TsinghuaX60240013.x/week2/Week2.00001.TSGCMATHT314-V000900_DTH.srt) or you can sign up for Yuchun's course Combinatorial Mathematics at https://www.edx.org/course/combinatorial-mathematics-zu-he-shu-xue-tsinghuax-60240013x-2 and watch it on the edX platform which includes subtitles, transcripts and other amenities.

Note: If we do not have time and bandwidth to discuss all three questions on Sep 22nd, which is likely, we will discuss the rest of the paper at the October 27th meetup. Currently, we are planning a long series on combinatorics, number theory, and other related topics where generating functions will play an important role. So this introductory material will be useful to master.

As a PA resident, I was able to obtain a PDF copy of the paper from Temple University. Because the paper is still under copyright, I can only send it to you for educational purposes (and I cannot post it on-line). If you want a copy for educational purposes, send me an e-mail at cjf@CJFearnley.com.

I do not recommend consulting the following resources (they are unnecessary and will require too much time to review), however I include them as reference for those who want to dig more deeply into the subject. Between Oct 2016 and Feb 2017, Math Counts organized three topics on generating functions based on Ma Yu Chun's course (mentioned above). Here are links to those three events: Oct 2016: Counting with Generating Functions (Integer Partitions and more) (https://www.meetup.com/MathCounts/events/234687256), Jan 2017: Solving Basic Recurrence Relations with Generating Functions (https://www.meetup.com/MathCounts/events/236793457), Feb 2017: Solving Linear Homogeneous Recurrence Relations (https://www.meetup.com/MathCounts/events/236786700).