Question

Anyone know how to explain how generating functions work as a formula for partitions?

Answer 1

I'm not entirely sure what you're asking... but it sounds like you're asking about parametric equations.

Answer 2

It's basically cause partitions depend on other lower partitions, so there's a recurrence relation that you can throw onto a generating function that can end up simplifying stuff nicely sometimes.

Answer 3

is it possible for you to give an example like the partition of 5=7, show using generating function?

Answer 4

The ordinary generating function of a sequence \(a_n\):
\[G(a_n:x) = \sum_{n=0}^{\infty} a_n x^n\]

Answer 5

There are a ton of them depending on what you want to do, ie: Lamber series is defined as: \[EG(a_n :x) = \sum_{n=-0}^{\infty} a_n \frac{x^n}{1-x^n}\]

Answer 6

Lambert *

Answer 7

just like the one in https://en.wikipedia.org/wiki/Partition_(number_theory)#Partition_function

Answer 8

@ganeshie8 @dan815

Answer 9

im specifically eyeing to understand

Answer 10

basically i see that the approximation formula will never get u an exact value of p(n) but what about the generating formula

Answer 11

@satellite73

Answer 12

I'm not entirely sure, I'm reading the wiki article, but I know how it tends to get dense so I'll dissect it for you @dtan5457 I am sorta struggling with it, but I might be able to figure this out with you.

https://en.wikipedia.org/wiki/Partition_(number_theory)#Generating_function

Ok so first off, what are all the partitions of a number? Just the number of different ways you can write that number as a sum without worrying about order. So what is it for 3?

Turns out to be 3, because of these:

1+1+1
1+2
3

Now how do we tie this into generating functions?

The generating function they use is:

\[(1+x+x^2+x^3+\cdots )(1+x^2+x^4+x^6+\cdots)(1+x^3+x^6+x^9+\cdots)\cdots\]

Well that's somewhat scary, but at least it follows a pattern. Let's look at a baby version of the generating function they use to get an idea for what's happening, since this is all we need to find the coefficient on the \(x^3\) term.

\[(1+x+x^2+x^3)(1+x^2)(1+x^3)\]

Now when we multiply it out what will the coefficient be on the \(x^3\) term? Well we can multiply the whole thing together and find it, or just look at which terms sum to 3 in the exponent:

\[x^0x^3+ x^1x^2+x^3x^0 = 3 x^3 \]

Well ok, we're getting the right answer but I'm not particularly sure what's being counted.

Answer 13

i see what your kind of doing but im not sure how you got your terms x^0x^3+x^1x^2+x^3x^0=3^x3

i understand that the coefficient does become 3 though

Answer 14

Alright I'm starting to see now, if we throw in the base number of the geometric series that's being multiplied to this: \[(1+x+x^2+x^3)(1+x^2)(1+x^3)\]

we get:

\[(1^{1*0}+x^{1*1}+x^{1*2}+x^{1*3})(1^{2*0}+x^{2*1})(1^{3*0}+x^{3*1})\]

NOW when we multiply it together we have more structure going on in there when we look for the \(x^3\) term:

\[1^{1*0}1^{2*0}x^{3*1} + x^{1*1}x^{2*1}1^{3*0}+x^{1*3}1^{2*0}1^{3*0} = 3x^3\]
Now I'm starting to understand how this is giving us the partitions in the exponents, the first term \(1^{1*0}1^{2*0}x^{3*1}\) represents the term 3 one time, the second term \(x^{1*1}x^{2*1}1^{3*0}\) represents 1 a single time with 2 a single time, and the last term \(x^{1*3}1^{2*0}1^{3*0}\)represents 1 three times.

If this doesn't explain it well enough, don't feel bad I'm still trying to digest this myself, but this is sorta what I'm seeing in this so far.

Answer 15

Before I attempt to understand this, this will work for any positive integer? Or is it limited like the approximation theory?

Answer 16

This is the exact formula for the partitions, not an approximation.

Answer 17

How exactly did you get the "baby" formula in the first place?

Answer 18

Guess first, then I'll tell you.

Answer 19

maybe u just canceled out all that wasn't necessary while not touching the first term of (1+x+x^2+x^3)

then you put (1+x^2)(1+x^3)

so would x^4 be (1+x+x^3+x^4)(1+x^2)(1+x^3)(1+x^4)?

Answer 20

im still trying to understand the generating formula

Answer 21

is every term a new multiple of exponents like (1+x^4+x^8+x^12+x^16?

Answer 22

Yeah, I just threw out all the higher terms that wouldn't contribute to the coefficient on \(x^3\), so this baby version is exactly accurate for p(1), p(2), and p(3) only, and severely underestimates p(n) for all other values higher haha.

Answer 23

so if the partition to solve was like 4 or 5 what would it look like?

Answer 24

Then you'd need at least this to calculate p(4) since it'll be the coefficient on \(x^4\):
\[(1+x+x^2+x^3+x^4)(1+x^2+x^4)(1+x^3)(1+x^4)\]

(Although the (1+x^3) term is unnecessary for calculating p(4), I just wanted to ONLY add terms rather than take off terms so that it's still valid for p(3) and lower).

Similarly for p(5) it's the coefficient on \(x^5\) so only the terms that multiply together to have 5 in the exponent matter, so adding on to the last one:

\[ (1+x+x^2+x^3+x^4+x^5)(1+x^2+x^4)(1+x^3)(1+x^4)(1+x^5)\]

Answer 25

Right now I'm reading this, it looks like it's a little easier for me to understand http://www.artofproblemsolving.com/wiki/index.php/Partition_(combinatorics)#Generating_Functions

Answer 26

I suggest just not using the baby formula I came up with, just use the original thing here:

\[F(x)=(1+x+x^2+x^3+\cdots )(1+x^2+x^4+x^6+\cdots)(1+x^3+x^6+x^9+\cdots)\cdots\]
Now you know the coefficient on \(x^3\) is p(3) right? Just find it on your own right now.

If it helps, I've written it out this way too:

\[F(x) = \sum_{n=0}^\infty P(n)x^n = \prod_{k=1}^\infty \sum_{n=0}^\infty x^{kn}\]

Note that the geometric series:

\[ \sum_{n=0}^\infty x^{kn} = \frac{1}{1-x^k}\]

So we can rewrite it as:

\[F(x) = \sum_{n=0}^\infty P(n)x^n = \prod_{k=1}^\infty \frac{1}{1-x^k}\]

Answer 27

I will definitely look at this tomorrow night, I finished my research paper thanks to your brief explanation but I do want to fully understand this tomorrow. thanks again

Answer 28

Yeah I am still trying to better understand this, I've had partitions on my todo list to learn for a while. Glad I could help. The way that I am currently understanding it of how to derive it is:

\[1+x^k+x^{2k}+x^{3k}+\cdots\] is the generating function for partitioning ONLY n into a sum of k pieces.

So specific example:

\[1+x^3+x^{6}+x^{9}+\cdots\]

How many ways can you partition 7 into a sum of 3s? 0 ways. Look there, and we see \(0x^7\) is there. How many ways can we partition 9 into a sum of 3s? 3+3+3=9 Only one way. \(1*x^9\) Is up there, so good.

Now the partition function we're after is made up of combining pieces like this together, and that's what it does.

Answer 29

@Kainui If you go back to this, I am really starting to get this. However, I have a question about removing some terms when finding the partitions. You said for example that that expansion for the integer 4, we can remove (1+x^3), what are the rules for that?

like how would i completely simplify for the integer 9?

(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)(1+x^2+x^4+x^6+x^8)
(1+x^3+x^6+x^9)(1+x^4+x^8)(1+x^5)(1+x^6)(1+x^7)(1+x^8)(1+x^9)

Answer 30

what can i remove from there that the coefficient would still be right?

Answer 31

I think I was wrong about removing lower terms, but I am rushed so I gotta go but I'll be back

Answer 32

ok thanks man