Thread by @pgeerkens

@GWOMaths @MathsTim Recall from Feb. 1 this about generating functions for the odd and distinct partitions of n.


Then the generating function for unrestricted partitions of n, P(n), is given by

SUM(P(n) . q^n) = PROD(1 / (1 - q^i) )
where n ∈ {0, ... } and i ∈ {1, ...}.

@GWOMaths @MathsTim Then P(7) will be the coefficient of q^7 from the expansion of the RHS, noting that
1 / (1 - q^i)

is just
SUM(1 + q^i + q^2.i + q^3.i + q^4.i + ...)

and that we only require in each expansion powers of q ≤7.

@GWOMaths @MathsTim Se we must find q^7 term in

G
= (1+q+q^2+q^3+q^4+q^5+q^6+q^7)
.(1+q^2+q^4+q^6).(1+q^3+q^6)
.(1+q^4).(1+q^5)(1+q^6).(1+q^7)

Evaluating from right
G
= (1+q+q^2+q^3+q^4+q^5+q^6+q^7)
.(1+q^2+q^4+q^6).(1+q^3+q^6)
.(1+q^4).(1+q^5)(1+q^6+q^7)

...

@GWOMaths @MathsTim = (1+q+q^2+q^3+q^4+q^5+q^6+q^7)
.(1+q^2+q^4+q^6).(1+q^3+q^6)
.(1+q^4).(1+q^5+q^6+q^7)

= (1+q+q^2+q^3+q^4+q^5+q^6+q^7)
.(1+q^2+q^4+q^6).(1+q^3+q^6)
.(1+q^4+q^5+q^6+q^7)

= (1+q+q^2+q^3+q^4+q^5+q^6+q^7)
.(1+q^2+q^4+q^6)
.(1 + q^3 + q^4 + q^5 + 2.q^6 + 2.q^7)

@GWOMaths @MathsTim = (1+q+q^2+q^3+q^4+q^5+q^6+q^7)
.(1 + q^3 + q^4 + q^5 + 2.q^6 + 2.q^7
+ q^2 + q^5 + q^6 + q^7
+ q^4 + q^7
+ q^6)

= (1+q+q^2+q^3+q^4+q^5+q^6+q^7)
.(1+ q^2 + q^3 + 2.q^4 + 2.q^5 + 4.q^6 + 4.q^7)

@GWOMaths @MathsTim = (1 + q^2 + q^3 + 2.q^4 + 2.q^5 + 4.q^6 + 4.q^7
+ q + q^3 + q^4 + 2.q^5 + 2.q^6 + 4.q^7
+ q^2 + q^4 + q^5 + 2.q^6 + 2.q^7
+ q^3 + q^5 + q^6 + 2.q^7
+ q^4 +q^6 + q^7
+ q^5 + q^7
+ q^6
+ q^7)

= (1 + q + 2.q^2 + 3.q^3 + 5.q^4 + 7.q^5 + 11.q^6 + 15.q^7)

@GWOMaths @MathsTim as for convenience we drop all terms of q^8 or higher.

Then the number of partitions of 7, P(7), is found as the coefficient of q^7, which is 15.

Number of partitions of t is thus 15.

@GWOMaths @MathsTim I found this introduction on generating functions by MIT very easy to follow.

ocw.mit.edu/courses/electr…

This lecture is a good supplement to it:
whitman.edu/mathematics/cg…

@GWOMaths @MathsTim @threadreaderapp unroll

@GWOMaths @MathsTim Manual check,
explicitly enumerating the partitions
in increasing number of parts,
with parts in descending order:

7
6,1; 5,2; 4,3
5,1,1; 4,2,1; 3,3,1; 3,2,2
4,1,1,1; 3,2,1,1; 2,2,2,1
3,1,1,1,1; 2,2,1,1,1
2,1,1,1,1,1
1,1,1,1,1,1,1

As calculated: 15 partitions of 7.

@GWOMaths @MathsTim There is no closed form expression for the individual coefficients of the generating function for P(n), but there is a recurrence expression, as noted at the end of this lecture.
math.berkeley.edu/~mhaiman/math1…

@GWOMaths @MathsTim Evaluating:

P(1) = P(0)
= 1
P(2) = P(1) + P(0) = 1 + 1
= 2
P(3) = P(2) + P(1) = 2 + 1
= 3
P(4) = P(3) + P(2) = 3 + 2
= 5
P(5) = P(4) + P(3) - P(0) = 5 + 3 - 1
= 7
P(6) = P(5) + P(4) - P(1) = 7 + 5 - 1
= 11
P(7) = P(6) + P(5) - P(2) - P(0) = 11 + 7 - 2 - 1
= 15

as before.

@GWOMaths @MathsTim @threadreaderapp unroll