Number theory · Maths EE idea · Ambitious
Counting partitions with generating functions
A research question to start from
How do generating functions prove that the number of partitions of n into odd parts equals the number into distinct parts?
A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.
Why it works as a maths EE
A surprising identity with two proofs (algebraic and a bijection), letting you compare methods in the discussion.
Mathematics you would need
- Power series as generating functions
- Infinite products (formally)
- Bijections
- Partition diagrams
Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.
One possible line of attack
- Count both kinds of partition by hand for n up to 10.
- Derive the generating functions and prove the identity algebraically.
- Construct an explicit bijection and prove it works.
- Compare the two proofs: what each explains.
Scope and difficulty
Ambitious. Ambitious; formal power series need careful, honest treatment.
Pitfalls
- Hand-waving about infinite products.
- Bijection described but not proved.
Where to start reading
Search a library catalogue or a university's open lecture notes for: Euler partition theorem odd distinct; Glaisher bijection; generating functions. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).