Counting with Generating Functions (Integer Partitions and more)

A very powerful tool for counting is a generalization of polynomials and power series called generating functions (https://en.wikipedia.org/wiki/Generating_function). This discussion will explore basic properties and techniques of using this important counting tool. We will explore how generating functions can model tossing dice, weighing objects on a balance scale, making change with coins, calculating the number of partitions of a natural number. We will consider some basic ways to manipulate generating functions. Along the way we will explore Ferrers diagrams (more commonly called Youngs diagrams).

The main focus will be to get a basic understanding of generating functions. We will explore integer partitions in depth as a key example for the application of generating functions. There will be a brief introduction to using algebra, Taylor expansions, and the method of partial fractions to manipulate generating functions.

To help guide the discussion, please download and work out answers to these 25 exercises: http://files.meetup.com/3948532/CountingWithGeneratingFunctions.Oct2016.problems.pdf . Most of the problems are straightforward, but a few could be challenging for even our most knowledgeable members. If you have questions or issues with any of the problems, please post a comment below.

To help you learn the basics of generating functions, there are 8 highlighted Ma Yu Chun videos from the free on-line course TsinghuaX 60240013.x Combinatorial Mathematics (https://www.edx.org/course/combinatorial-mathematics-tsinghuax-60240013x-0) on the edX (http://edx.org) platform (Note: in Wikipedia it is reported that Tsinghua University (https://en.wikipedia.org/wiki/Tsinghua_University) is sometimes called the "MIT of China" due to its specialty in engineering and science).

Since Ma Yu Chun can be difficult for some people to understand, I have written detailed notes for each video and there are subtitles. I recommend watching each video for the first time at a slow playback speed (maybe 70-90% of full speed). As with reading a mathematics paper, it can be helpful to watch the videos once to get an overview before trying to master the key points. Searching for additional resources may be necessary to understand some parts.

• Download and work out 25 exercises about generating functions and the combinatorics of integer partitions at http://files.meetup.com/3948532/CountingWithGeneratingFunctions.Oct2016.problems.pdf

• Download 48 pages of slides (only pages 1-36 are relevant for this event, the material on Recurrence Relations will be discussed at a future event) for Ma Yu Chun's videos at https://courses.edx.org/c4x/TsinghuaX/60240013.x/asset/edxCM_w3.pdf

• 1. Definition Of Generating Function (1), 10 minute video. Read my notes on video 1 (https://plus.google.com/104222466367230914966/posts/4ATWakKuiDZ). Subtitles for video 1. This video assumes an understanding of the product and sum principles of counting. For a refresher in understanding these principles, read my notes on Ma Yu Chun's 9 minute video introduction to the fundamental principles of counting (https://plus.google.com/104222466367230914966/posts/TqtbKxzLVgz).

http://www.youtube.com/watch?v=zolnm0zTx40

• 2. Definition Of Generating Function (2), 8 minute video. Read my notes on video 2 (https://plus.google.com/104222466367230914966/posts/NRFW7nookEc). Subtitles for video 2.

http://www.youtube.com/watch?v=Vc5LsbLl0cI

• 3. Simple Applications Of Generating Functions, 6 minute video. Read my notes on video 3 (https://plus.google.com/104222466367230914966/posts/WRCveWUmnML). Subtitles for video 3.

http://www.youtube.com/watch?v=FHzv9A5r3Og

• 4. Integer Partitions (1), 5 minute video. Read my notes on video 4 (https://plus.google.com/u/0/104222466367230914966/posts/QPsKPSa7Wp6). Subtitles for video 4.

http://www.youtube.com/watch?v=VwU7gFmG9DU

• 5. Integer Partitions (2), 6 minute video. Read my notes on video 5 (https://plus.google.com/104222466367230914966/posts/38eZnMQUhe7). Subtitles on video 5.

http://www.youtube.com/watch?v=cLQqYn0oNV0

• 6. Integer Partitions (3), 11 minute video. Read my notes on video 6 (https://plus.google.com/104222466367230914966/posts/edtnXE5E572). Subtitles on video 6.

http://www.youtube.com/watch?v=-PRfcq1VKCY

• 7. Ferrers Diagram, 6 minute video. Read my notes on video 7 (https://plus.google.com/104222466367230914966/posts/MM78ppUDgTL). Subtitles on video 7 (http://cjfearnley.com/TsinghuaX60240013.x/week3/Week3.00007.TSGCMATHT314-V003100_DTH.srt).

http://www.youtube.com/watch?v=GU50oy2YlyY

• 8. What Can We Do With A Generating Function?, 4 minute video. Read my notes on video 8 (https://plus.google.com/104222466367230914966/posts/GuejZuNKK5C). Subtitles on video 8 (http://cjfearnley.com/TsinghuaX60240013.x/week3/Week3.00008.TSGCMATHT314-V003300_DTH.srt).

http://www.youtube.com/watch?v=KkH0U2SEev4

• (Optional) Pages 81-94 of Kenneth P. Bogart's free on-line resource "Combinatorics Through Guided Discovery" (http://www.math.dartmouth.edu/news-resources/electronic/kpbogart/ComboNoteswHints11-06-04.pdf#Page=93) provides a good introduction to generating functions.

https://upload.wikimedia.org/wikipedia/commons/f/f3/Straight_line.png

I use the python script youtube-dl to download the videos. You can download the latest version at https://rg3.github.io/youtube-dl/ . Youtube-dl should work on any system that supports python.

If you download the subtitles to the same directory as the videos, in Linux you can use "mplayer -sub SUBTITLES-FILE VIDEO-FILE" or "mpv --sub-file SUBTITLES-FILE VIDEO-FILE" where SUBTITLES-FILE and VIDEO-FILE are the local names you gave to those files.

https://upload.wikimedia.org/wikipedia/commons/f/f3/Straight_line.png

Note: this is our third session on Ma Yu Chun's course Combinatorial Mathematics (https://www.edx.org/course/combinatorial-mathematics-zu-he-shu-xue-tsinghuax-60240013x-0). To see the event description and problem set from the first session, see the link Combinatorics: The Science of Counting and Arrangements (19 Sep 2015) (https://www.meetup.com/MathCounts/events/224748900/). For the second session and its problem set see Combinations and Permutations (28 May 2016) (https://www.meetup.com/MathCounts/events/230843893/).