|
Hey guys: This week is my first week in university, and I'm taking a course in combinatoric. We are learning about Enumeration (for those who don't know, it is the topic that answers the question: "How many elements of (some set) have (some property)?)
So the prof began to explain and lecture about this topic by raising an example: How many ways can we choose a dozen donuts if the available flavours are chocolate, maple, lemon, plain, and the shop has enough available? So at the beginning I was like "this is ez, combination n choose k?" Then the prof starts lecturing about things and I became lost.
The steps to answering similar questions such as the one above are: (1) Find an algebraic expression called a generating function. (2) Find a certain coefficient in the generating function.
WUT? The prof then wrote down some complex notation formula, something about the weight function and such and such, and explained bijection (one-to-one correspondence). At this point in time I felt like rage-quitting. The thing is, the prof doesn't really put things in simple terms, and asking some ppl in my class only to receive some half-assed answers. So I got home, and searched on the web about these topics.
And now I'm still confused as hell.
Have you guys ever learned or encountered this topic before? If so, can you guys just briefly enlighten me on this subject? I really don't want to fall behind on my first week
|
A first course in combinatorics starts with generating functions? Seems like a pedagogical error to me...
EDIT:
On September 17 2010 12:28 Talent.L wrote: How many ways can we choose a dozen donuts if the available flavours are chocolate, maple, lemon, plain, and the shop has enough available? So at the beginning I was like "this is ez, combination n choose k?" Then the prof starts lecturing about things and I became lost.
The steps to answering similar questions such as the one above are: (1) Find an algebraic expression called a generating function. (2) Find a certain coefficient in the generating function.
This is what he probably wants: so there are 12 donuts and 4 different flavors. For each flavor, we can choose any non-negative number of those donuts. We can represent this choice as picking some term in (1 + x + x^2 + x^3 + x^4 + ...). The list goes on indefinitely since there are infinitely many of each. So for example, if we take 3 chocolate donuts, that corresponds to picking x^3. Now multiply these all together and you get:
(1 + x + x^2 + x^3 + x^4 + ... )(1 + x + x^2 + x^3 + x^4 + ...)(1 + x + x^2 + x^3 + x^4 + ... )(1 + x + x^2 + x^3 + x^4 + ...) = a_0 + a_1*x + a_2*x^2 + a_3*x^3 + a_4*x^4 + ...
The first factor is chocolate, second maple, third lemon, fourth plain. So as another example, if we took 2 chocolate, 0 maple, 2 lemon, and 4 plain, that corresponds to picking x^2, 1, x^2, and x^4, respectively from these factors. But notice that this choice contributes exactly one x^8 term on the right side. In fact, the coefficient of x^8 on the right side will be the number of ways to pick 8 donuts with these 4 flavors! So the answer to your problem is in fact the coefficient of x^12. Make sense?
Finding those coefficients is tricky as I've written it because those factors go to infinity, but if you're willing to ignore technical details, you can in fact let 1 + x + x^2 + x^3 + x^4 + ... = 1 / (1 - x) without worrying about x too much.
GL HF !
|
I am taking that right now! I was confused by generating functions too, but now I sort of understand them. Explanation to follow
|
HAHA
Are you in Math 239 at U of Waterloo? Prof being Penny Haxell? At 12:30 MWF?
Honestly though, its not too bad. But you shouldnt be asking for help at TL. Tutorials and office hours are the way to go.
The generating function is to see specifics, ie. not just solve how many different combinations there are, but if they are given a weight, or if there is a restriction of how many donuts there are (not infinitely many to choose from)
|
On September 17 2010 12:38 Oracle wrote: HAHA
Are you in Math 239 at U of Waterloo? Prof being Penny Haxell? At 12:30 MWF?
Honestly though, its not too bad. But you shouldnt be asking for help at TL. Tutorials and office hours are the way to go.
OMG YES! haha do you mind exchanging contact info (emails, msn, etc)? i'm so confused in class :/
|
Generating function is just a (formal) series or polynomial or rational function whose coefficients "count" something (intuitively).
So for example (1+x)^n encodes all the data about nCk, since the coefficients of x^i are just nCi. So you can prove a lot of results about these counting "coefficients" by algebraically manipulating these (formal) functions. Just try equating the coefficients you get from (1 + x)^n (1 + x)^m = (1 + x)^(n+m). You'll get an identity involving (n+m)Ck in terms of sums of nCk's and mCk's very easily.
Or in algebraic geometry, you can encode all the dimensions of k-th degree terms of projective sections, and prove a lot of things about degrees.. define genus, dimensions, etc.. very easily (existence of hilbert polynomial is also quite transparent).
The idea just seems to be that you're encoding all the counting data into an algebraic expression you can easily manipulate.
I'm not a combinatorist, but that alone has been pretty useful to me.
|
On September 17 2010 12:31 FiBsTeR wrote:A first course in combinatorics starts with generating functions? Seems like a pedagogical error to me... EDIT: Show nested quote +On September 17 2010 12:28 Talent.L wrote: How many ways can we choose a dozen donuts if the available flavours are chocolate, maple, lemon, plain, and the shop has enough available? So at the beginning I was like "this is ez, combination n choose k?" Then the prof starts lecturing about things and I became lost.
The steps to answering similar questions such as the one above are: (1) Find an algebraic expression called a generating function. (2) Find a certain coefficient in the generating function. This is what he probably wants: so there are 12 donuts and 4 different flavors. For each flavor, we can choose any non-negative number of those donuts. We can represent this choice as picking some term in (1 + x + x^2 + x^3 + x^4 + ...). The list goes on indefinitely since there are infinitely many of each. So for example, if we take 3 chocolate donuts, that corresponds to picking x^3. Now multiply these all together and you get: (1 + x + x^2 + x^3 + x^4 + ... )(1 + x + x^2 + x^3 + x^4 + ...)(1 + x + x^2 + x^3 + x^4 + ... )(1 + x + x^2 + x^3 + x^4 + ...) = a_0 + a_1*x + a_2*x^2 + a_3*x^3 + a_4*x^4 + ... The first factor is chocolate, second maple, third lemon, fourth plain. So as another example, if we took 2 chocolate, 0 maple, 2 lemon, and 4 plain, that corresponds to picking x^2, 1, x^2, and x^4, respectively from these factors. But notice that this choice contributes exactly one x^8 term on the right side. In fact, the coefficient of x^8 on the right side will be the number of ways to pick 8 donuts with these 4 flavors! So the answer to your problem is in fact the coefficient of x^12. Make sense? Finding those coefficients is tricky as I've written it because those factors go to infinity, but if you're willing to ignore technical details, you can in fact let 1 + x + x^2 + x^3 + x^4 + ... = 1 / (1 - x) without worrying about x too much. GL HF !
Thanks for the help! I'm still slightly confused, but I sort of get it now..
|
I share your pain.
To be honest, I never understood combinatorics very well.
|
you use generating functions when you have some sequence a-sub-n defined recursively and you want an explicit definition for a-sub-n. often you will be given a problem that is like "count this" and then you find a recursive formula for it and then use generating functions to go from a recursive formula to an explicit formula.
a generating function, call it a(x), has the form (a-sub-0) + x(a-sub-1) + (x^2)(a-sub-2) ... ie the sum from i=0 to infinity of (x^n)(a-sub-n). The idea is that the a-sub-n's have the same value as the sequence.
as an example, if we had the recurrence a-sub-n - 10(a-sub-(n-1)) + 25(a-sub-(n-2)) = 0 (n>=2) with initial values a-sub-0 = a-sub-1 = 1 :
You want to put the recurrence in terms of the generating function, so you essentially multiply both sides by (x^n). Really what you are doing is you know the recurrence holds for all n>=2, so you can add all of those equations together and they will still hold.
so you do that, but since the recurrence only holds for n>=2 the sums are from n=2 to infinity which means if you want it in terms of a(x) you have to subtract off the n=1 and n=0 terms. Therefore you go from (x^n)(sum from n=2 to infinity of[a-sub-n - 10(a-sub-(n-1)) + 25(a-sub-(n-2))]) = 0 to [a(x) - 1 - x] - [10x(a(x)-1)] + [25(x^2)a(x)] = 0
from there you solve the equation for a(x) and use calculus to convert that into a taylor series, which then gives you a-sub-n in terms of n (ie the explicit definition of a-sub-n) which is exactly what you were looking for.
|
United States4053 Posts
gonna try to make this simple let's say i want to pick 10 m&m's, and i have blue and green m&m's, how many ways are there? i'll expand (1 + x + x^2 + x^3 + ... + x^10) * (1 + x + x^2 + x^3 + ... + x^10) and find the coefficient of x^10. say I choose x^4 from the first factor, and x^6 from the second factor. let's say that means 4 blue m&ms and 6 green m&ms. similarly for other pairs. if i expand, obviously the coefficient of x^10 is going to be 11, and lo and behold there are 11 ways to pick 10 m&m's in blue and green.
|
Just a quick example why the simple way doesn't work.
You would think that since you had 4 options that are independent of each other you could just do 4^n and then divide by n! since we don't care about order, and this does make a certain amount of sense. However, there's a little problem. Think about the case where (n=4) we choose 3 chocolate donuts and one plain, how many ways can we order them? Well, if we brute force it we get:
CCCP CCPC CPCC PCCC
only 4 (n) ways to arrange this particular case, and so we have a problem since we divided out too many terms (n! or in other words 4!).
Hope it helps a bit, gl edit: for clarity
|
United States4053 Posts
On September 17 2010 13:08 jonnyp wrote:+ Show Spoiler +Just a quick example why the simple way doesn't work. You would think that since you had 4 options that are independent of each other you could just do 4^n and then divide by n! since we don't care about order, and this does make a certain amount of sense. However, there's a little problem. Think about the case where (n=4) we choose 3 chocolate donuts and one plain, how many ways can we order them? Well, if we brute force it we get: CCCP CCPC CPCC PCCC only 4 (n) ways to arrange this particular case, and so we have a problem since we divided out too many terms (n! or in other words 4!). Hope it helps a bit, gl edit: for clarity Generating functions inherently circumvent this issue, because they don't consider order at all.
|
On September 17 2010 12:41 Talent.L wrote:Show nested quote +On September 17 2010 12:38 Oracle wrote: HAHA
Are you in Math 239 at U of Waterloo? Prof being Penny Haxell? At 12:30 MWF?
Honestly though, its not too bad. But you shouldnt be asking for help at TL. Tutorials and office hours are the way to go. OMG YES! haha do you mind exchanging contact info (emails, msn, etc)? i'm so confused in class :/ I took that class this summer. =]
It wasn't as hard as people hyped it up to be, the assignments are fairly interesting and the tests are just watered down assignments.
|
yea me and crunchums are both in combinatorics at CMU although i'm not sure he knows who i am.... although i did wear my TL shirt last class so maybe. : P
|
On September 17 2010 13:13 infinitestory wrote:Show nested quote +On September 17 2010 13:08 jonnyp wrote:+ Show Spoiler +Just a quick example why the simple way doesn't work. You would think that since you had 4 options that are independent of each other you could just do 4^n and then divide by n! since we don't care about order, and this does make a certain amount of sense. However, there's a little problem. Think about the case where (n=4) we choose 3 chocolate donuts and one plain, how many ways can we order them? Well, if we brute force it we get: CCCP CCPC CPCC PCCC only 4 (n) ways to arrange this particular case, and so we have a problem since we divided out too many terms (n! or in other words 4!). Hope it helps a bit, gl edit: for clarity Generating functions inherently circumvent this issue, because they don't consider order at all. yeah but they're not very intuitive. It sounded like he was having a mental block understanding why we can't just use the "regular" way so I was illustrating where it breaks down.
|
On September 17 2010 13:18 thundertoss wrote: yea me and crunchums are both in combinatorics at CMU although i'm not sure he knows who i am.... although i did wear my TL shirt last class so maybe. : P o.O are you also in my pragmatism class / do you want to play for our CBW team / I suppose you are already signed up for our CSL team but if you're not do you want me to sign you up?
edit: man I should make a blog thread where I ask people who go to CMU to post in it : 3
|
On September 17 2010 13:08 jonnyp wrote:Just a quick example why the simple way doesn't work. You would think that since you had 4 options that are independent of each other you could just do 4^n and then divide by n! since we don't care about order, and this does make a certain amount of sense. However, there's a little problem. Think about the case where (n=4) we choose 3 chocolate donuts and one plain, how many ways can we order them? Well, if we brute force it we get: CCCP CCPC CPCC PCCC only 4 (n) ways to arrange this particular case, and so we have a problem since we divided out too many terms (n! or in other words 4!). Hope it helps a bit, gl edit: for clarity
4C1 works in this case.. it falls apart when theres 3 or more possible donuts
and 4^n / n! = 4^4 / 4! isnt even an integer
|
On September 17 2010 13:08 jonnyp wrote:Just a quick example why the simple way doesn't work. You would think that since you had 4 options that are independent of each other you could just do 4^n and then divide by n! since we don't care about order, and this does make a certain amount of sense. However, there's a little problem. Think about the case where (n=4) we choose 3 chocolate donuts and one plain, how many ways can we order them? Well, if we brute force it we get: CCCP CCPC CPCC PCCC only 4 (n) ways to arrange this particular case, and so we have a problem since we divided out too many terms (n! or in other words 4!). Hope it helps a bit, gl edit: for clarity
There is still a simple way to solve this problem with just combinations and no gfs, it's just not as natural as the kind of approach you described.
Here are my 12 donuts:
oooooooooooo
Now I'm going to throw in 3 dividers like so:
oooo|o|oooo|ooo
The donuts before the first divider are chocolate, the ones between the next dividers are... you get the point. So every assortment of 12 circles and 3 lines yields a unique choice of donuts. But we can go backwards: if I take 5 chocolate and 7 plain, I write:
ooooo|||ooooooo
There is thus a bijection (1-1 correspondence) between choices of 12 donuts with 4 flavors and permuting 12 circles and 3 lines. If you've seen combinations before, you can see this is just 15 C 3, which turns out to be the answer. In fact, with n donuts k flavors, it isn't too much of a leap to find there are (n + k - 1) C (k - 1) choices.
EDIT:
And just to show you the gf above does indeed give the same answer:
|
God I hated combinatorics so much, my professor was some Polish dude who I couldn't understand at all and didn't have class notes. Needless to say, I got a C. Although if you don't know what a bijection is, you should probably brush up on some stuff. Have you taken a proof-based math class before?
*Note: Yes, I also go to CMU*
|
good thing for you guys you find your classmates here..)
|
|
|
|