Overview
On this page, we continue our study of Combinatorics by discussing partitions (with a fixed number of summands) and the so-called Stars & Bars technique.
Basic learning objectives
These are the tasks you should be able to perform with reasonable fluency when you arrive at your next class meeting. Important new vocabulary words are indicated in italics.
Advanced learning objectives
In addition to mastering the basic objectives, here are the tasks you should be able to perform after class, with practice:
- Be able to count the number of ordered partitions of a positive integer and solve related counting problems using the stars & bars technique.
To prepare for class
-
Watch the following video (by Numberphile, with Prof. Ken Ribet) which explains the “Bagel Problem” and how to use the Stars & Bars technique to solve it:
-
Watch the following video (by Brendan Cordy) which demonstrates how to solve a problem (and a few variations of it) using basic combinatorics and the Stars & Bars technique:
After class
-
Watch the following video (by Kimberly Brehm) which shows some more examples, including counting positive integer solutions to certain linear equations (i.e. “integer partitions with fixed number of summands”), starting at 8:48. Important Note: She uses the so-called multiset notation \(\left(\!\binom{n}{k}\!\right)\) - note the double parentheses - to denote the number of ways to arrange \(n\) bars and \(k\) stars, i.e. \(\left(\!\binom{n}{k}\!\right)=\binom{k+n-1}{k}=\binom{k+n-1}{n-1}\).
