dtan5457
  • dtan5457
Anyone know how to explain how generating functions work as a formula for partitions?
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
agreene
  • agreene
I'm not entirely sure what you're asking... but it sounds like you're asking about parametric equations.
Kainui
  • Kainui
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.
dtan5457
  • dtan5457
is it possible for you to give an example like the partition of 5=7, show using generating function?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

agreene
  • agreene
The ordinary generating function of a sequence \(a_n\): \[G(a_n:x) = \sum_{n=0}^{\infty} a_n x^n\]
agreene
  • agreene
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}\]
agreene
  • agreene
Lambert *
dtan5457
  • dtan5457
just like the one in https://en.wikipedia.org/wiki/Partition_(number_theory)#Partition_function
dtan5457
  • dtan5457
@ganeshie8 @dan815
dtan5457
  • dtan5457
im specifically eyeing to understand
dtan5457
  • dtan5457
basically i see that the approximation formula will never get u an exact value of p(n) but what about the generating formula
dtan5457
  • dtan5457
@satellite73
Kainui
  • Kainui
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.
dtan5457
  • dtan5457
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
Kainui
  • Kainui
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.
dtan5457
  • dtan5457
Before I attempt to understand this, this will work for any positive integer? Or is it limited like the approximation theory?
Kainui
  • Kainui
This is the exact formula for the partitions, not an approximation.
dtan5457
  • dtan5457
How exactly did you get the "baby" formula in the first place?
Kainui
  • Kainui
Guess first, then I'll tell you.
dtan5457
  • dtan5457
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)?
dtan5457
  • dtan5457
im still trying to understand the generating formula
dtan5457
  • dtan5457
is every term a new multiple of exponents like (1+x^4+x^8+x^12+x^16?
Kainui
  • Kainui
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.
dtan5457
  • dtan5457
so if the partition to solve was like 4 or 5 what would it look like?
Kainui
  • Kainui
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)\]
Kainui
  • Kainui
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
Kainui
  • Kainui
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}\]
dtan5457
  • dtan5457
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
Kainui
  • Kainui
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.
dtan5457
  • dtan5457
@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)
dtan5457
  • dtan5457
what can i remove from there that the coefficient would still be right?
Kainui
  • Kainui
I think I was wrong about removing lower terms, but I am rushed so I gotta go but I'll be back
dtan5457
  • dtan5457
ok thanks man

Looking for something else?

Not the answer you are looking for? Search for more explanations.