Question

How can we use the partition generating function to solve a problem like this?

Answer 1

TO show the number of ways a certain amount of cents can be formed using pennies, nicklels, dimes, and quarters

Answer 2

the hard part about this seems to be the limit of integers (only being able to use 1, 5, 10, and 25)

Answer 3

@DanJS @Kainui @rational @Blacksteel

Answer 4

In my understanding, the general idea is as follows: one writes down the generating polynomial that includes all of the listed amounts of cents as powers:
\[g(x)=x+x^5+x^{10}+x^{25}\]

Answer 5

g(x) represents "a coin" Now if someone asks you take k coins and count the number of ways one could get, say, m cents using these k coins, you apply the trick of generating functions. You mutliply k functions g(x): \[g^k(x)=(x+x^5+x^{10}+x^{25})^k\]. You can now multiply this out, perhaps use multinomial fomula to do so. But let us take a concrete example of k=3 coins, and m=25 cents: \[g^3(x)=(x+x^5+x^{10}+x^{25})^3\]

Answer 6

\[g^3(x)=x^{75}+3 x^{60}+3 x^{55}+3 x^{51}+3 x^{45}+6 x^{40}+6 x^{36}+3 x^{35}+6 x^{31}+x^{30}+3 x^{27}+3 x^{25}+3 x^{21}+3 x^{20}+6 x^{16}+x^{15}+3 x^{12}+3 x^{11}+3 x^7+x^3\]

Answer 7

is there for a specific amount of cents though? Like If I asked for the partitions of 26 cents, i don't think there is a restraint on the amount of coins

Answer 8

(hmm, the line shows partially truncated, but maybe others can see it full). So let me say we are looking for m=40 cents (because that is what seems to fit the display). To get the number of ways three coins can be combined into a sum of 40 cents ais now the factor in front of x^{40}, which turns out to be 6. Six ways.

Answer 9

you mean given a desired total amount of cents what is the way to get it using any number of coins? I would think the answer is similar, but you need to add the term x^0 to g(x) to account for "no contribution from a particular coin), like this

Answer 10

\[g(x)=1+x+x^5+x^{10}+x^{25}\]

Answer 11

then you need to choose k at least that of the desired total amount to account for polynomial to attain the sum using minimal denomitation (1 cent), so that would be g^{40}(x) for 40 cents.

Answer 12

Generally you want to find some formula, similar to the multinomial formula, that gives you a prescription for the factor of each term, so you do not really need to multiply everything out. Does this make sense?

Answer 13

im still a little confused.

Answer 14

possible you can demonstrate a full out example for any number of cents?

Answer 15

when you say "any number of cents" are you referring to the total sum (value in cents) or to the number of coins?

Answer 16

i would like it to be the total sum. but if it's a lot more complicated then we can stick with the number of coins

Answer 17

okay we can take an example: 40 cents using any number of coins

Answer 18

ok

Answer 19

so i took the 40th power of the polynomial g(x) = 1+x+x^5+x^10+x^25. The coefficient of the power 40 of that polynomial is astronomical, about 7000 trillion.

Answer 20

which makes sense if one thinks about having 40 1 cent coins permuted all ways, then 35 pennies permuted with 1 nickel, etc.etc.

Answer 21

Normally, the number of coins is given which makes the problem manageable, like I showed further above.

Answer 22

i was hoping for this to be an ordered partition is that possible

Answer 23

the main point is that you get the essence of why this works, then you will solve any similar problem

Answer 24

what precisely do you mean by ordered partition?

Answer 25

if it was ordered wouldnt it be alot more manageable? like you can only arrange 40 pennies once.

Answer 26

thats actually called non-ordered my bad

Answer 27

if we allowed order partitions that formula is generally 2^(x-1)

Answer 28

then generating is usually for non-ordered

Answer 29

actually my comment on permutation was out of place - the arragement of 40 pennies will be counted only once in the total number of ways we can get 40 cents.

Answer 30

right

Answer 31

so let me make sure i understand correctly: for a simpler example how many non-ordered arrangements of pennies and dimes can get you total of 6 cents,

Answer 32

(sorry i mean to say nickel instead of dime) you want to count 6 pennies as one, then 1 nickel + 5 pennies and that's it, i.e. 2 arrangements?

Answer 33

sounds right

Answer 34

obviously dimes and quarters can be used too but they cant in that situation

Answer 35

but if its near impossible. let's just stick with your first idea.

Answer 36

i need to sign off but will keep thinking about this. thanks

Answer 37

no, thank you :)

i still have a day to figure this out

thanks for taking your time

Answer 38

This seems to have a bunch of useful info and might actually answer your question https://math.berkeley.edu/~mhaiman/math172-spring10/partitions.pdf. I haven't had time to read through but will do so, too.

Answer 39

im reading it and im looking for the part that will specificlaly help me, know where that is?

Answer 40

@satellite73

Answer 41

but im actually getting more and more interested in your first interpretation of the problem as well

Answer 42

would it be (x+x^5+x^10+x^25)^k for any number of cents?

Answer 43

yes, with k coins

Answer 44

oh no wait i think i know what you mean. you put k as the amount of coins and all the exponents are the possible cents u can get with 3 coins, thats why so many exponents are missing because alot of number of cents cannot be made with only 3 coins, correct?

Answer 45

you got it!

Answer 46

im definitely gonna use that for my research paper. however for the final one due in a week, if its possible to solve my interpretation of the problem, that would be nice as well but thanks anyhow

Answer 47

also, do you know how to do that with non-ordered partitions?