partition

Counting PartitionsJohn C. Baez, January 15, 2004In class we studied the structure type G for which:A G-structure on a nite set S is a way of chopping S into two parts, totally orderingthe rst part and chopping it into blocks of length 1, and totally ordering the second partand chopping it into blocks of length 2.Translating this description into an equation, we saw1 1G =21 Z 1 Zwhich gives the generating function1 1 2 2 4jGj(z) = = (1 +z +z +)(1 +z +z +)21 z 1 z2 3 4 5= 1 +z + 2z + 2z + 3z + 3z +If we write XnjGj(z) = g znn0then g is the number of ways of writing the number n as a sum of 1’s and 2’s, where we don’t carenabout the order | or equivalently, where we write all the 1’s rst:0 = =)g = 101 = 1 =)g = 112 = 1 + 1; 2 =)g = 223 = 1 + 1 + 1; 1 + 2 =)g = 234 = 1 + 1 + 1 + 1; 1 + 1 + 2; 2 + 2 =)g = 345 = 1 + 1 + 1 + 1 + 1; 1 + 1 + 1 + 2; 1 + 2 + 2 =)g = 35and so on. The reason we don’t see an n! in the denominator of this generating function is thatputting a G-structure on the set n secretly involves choosing a total order on the elements of n, andthere are n! ways to make this choice.(By the way: when the factors of n! cancel for this reason, people call the generating function anordinary generating function. When they don’t cancel, people call it an exponential generatingfunction. People often treat these cases as if they were very di erent. But they’re not: ordinarygenerating functions are just exponential generating ...