Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2013-12-14 02:24:17

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Getting the coefficient.

Hi;

At the request of anonimnystefy:

Part 1

Sure generating functions are great because they turn a combinatorics problem into a computational one. But how do you get those coefficients? I am not talking about the baby problems they post in books that they can do by hand I am talking about industrial strength ones. Let's see how a CAS would do it.

Now there are several means, spot the pattern, recurrence relations, complex analysis and some others. We will try them all.

Let's look at a baby problem first and see how it is done.

A die is thrown 10 times, what is the coefficient of x^25?
This can restated as a die is thrown 10 times what is the probability that the sum of the die equals 25?

The gf is :

Without going into residues one way to do this is

Im[NIntegrate[Evaluate[
    				(( (x + x^2 + x^3 + x^4 + x^5 + x^6)/6)^10/x^26 /. 
       x -> E^(I \[CurlyPhi])) I E^(I \[CurlyPhi])],
   		{\[CurlyPhi], 0, 2 \[Pi]}, Method -> Trapezoidal, 
   WorkingPrecision -> 35, PrecisionGoal -> 16, MaxRecursion -> 12, 
   AccuracyGoal -> 16]]/(2 \[Pi])

Running that we get the immediate answer of 0.0137465944596860234720317024843773815. The exact answer by expanding the expression is

We did well as you can see.

Did you follow up to here?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#2 2013-12-14 02:48:26

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: Getting the coefficient.

Yes, that is the method from the other thread, right?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#3 2013-12-14 02:55:36

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

Yep, but never shown. Let's see a larger one.

Let's say we flip the die 100 times. We want the coefficient of x^500.

Im[NIntegrate[Evaluate[
    				(( (x + x^2 + x^3 + x^4 + x^5 + x^6)/6)^100/x^501 /. 
       x -> E^(I \[CurlyPhi])) I E^(I \[CurlyPhi])],
   		{\[CurlyPhi], 0, 2 \[Pi]}, Method -> Trapezoidal, 
   WorkingPrecision -> 50, PrecisionGoal -> 25, MaxRecursion -> 13, 
   AccuracyGoal -> 25]]/(2 \[Pi])

We get:

Is that right?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#4 2013-12-14 02:59:44

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: Getting the coefficient.

Hm, by expanding, I get

Last edited by anonimnystefy (2013-12-14 03:01:08)


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#5 2013-12-14 03:04:45

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

This is what you should have:


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#6 2013-12-14 03:50:34

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: Getting the coefficient.

Yeah.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#7 2013-12-14 03:57:30

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

You see it now?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#8 2013-12-14 04:17:19

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: Getting the coefficient.

Wait, that's the residue method?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#9 2013-12-14 04:25:15

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

I think that is what it is called but no matter it works.

Do you notice how much faster it is than expanding?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#10 2013-12-14 04:26:13

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: Getting the coefficient.

Hm, I've already seen this method.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#11 2013-12-14 04:36:07

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

I do not think you have, I have kept this a secret because of its speed over the original routine.

Let's do a real sized problem now and see how it does.

How about 10000 throws and what is the coefficient of x^50000?

Im[NIntegrate[
   Evaluate[(((x + x^2 + x^3 + x^4 + x^5 + x^6)/6)^10000/x^50001 /. 
       x -> E^(I \[CurlyPhi])) I E^(I \[CurlyPhi])], {\[CurlyPhi], 0, 
    2 \[Pi]}, Method -> Trapezoidal, WorkingPrecision -> 150, 
   PrecisionGoal -> 75, MaxRecursion -> 14, 
   AccuracyGoal -> 75]]/(2 \[Pi])

I get:

This is the end of Part 1.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#12 2013-12-15 08:23:25

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: Getting the coefficient.

Hi bobbym

I cannot expand it, so I cannot check. I am sure that that value is close.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#13 2013-12-15 13:33:57

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

How do we usually verify a result in numerical work like this?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#14 2013-12-15 18:25:49

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: Getting the coefficient.

With another method?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#15 2013-12-15 22:36:06

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

That is correct! That brings us to Part 2.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#16 2013-12-16 01:23:55

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: Getting the coefficient.

Shoot!


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#17 2013-12-16 03:23:07

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

Part 2

Another way is to form a recurrence relation for the coefficients.

We will start with the toy problem given in post #1.

We wish to get the coefficient of x^25.

We form the recurrence for the numerator:

We will need to prime it with the first 5 values.

Series[(x + x^2 + x^3 + x^4 + x^5 + x^6)^k, {x, 0, 5}] // Normal

This is the ouput:

x^k (1 + k x + 1/2 (k + k^2) x^2 + 1/6 (2 k + 3 k^2 + k^3) x^3 + 
   1/24 (6 k + 11 k^2 + 6 k^3 + k^4) x^4 + 
   1/120 (24 k + 50 k^2 + 35 k^3 + 10 k^4 + k^5) x^5)

We eliminate the variable k.

x^k (1 + k x + 1/2 (k + k^2) x^2 + 1/6 (2 k + 3 k^2 + k^3) x^3 + 
     1/24 (6 k + 11 k^2 + 6 k^3 + k^4) x^4 + 
     1/120 (24 k + 50 k^2 + 35 k^3 + 10 k^4 + k^5) x^5) /. 
  k -> 10 // Expand

This yields:

Compute the recurrence:

RecurrenceTable[{a[n] == 
    1/(-10 + 
      n) (65 a[-5 + n] - n a[-5 + n] + 54 a[-4 + n] - n a[-4 + n] + 
       43 a[-3 + n] - n a[-3 + n] + 32 a[-2 + n] - n a[-2 + n] + 
       21 a[-1 + n] - n a[-1 + n]), a[10] == 1, a[11] == 10, 
   a[12] == 55, a[13] == 220, a[14] == 715}, a, {n, 10, 25}] // Last

this yields 831204. Now we divide by 6 ^ 10.


which we know is correct. Can you follow?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#18 2013-12-16 17:49:11

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: Getting the coefficient.

I understand everything except hiw you formed the recurrence.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#19 2013-12-17 00:47:02

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

You have not followed our comments earlier on how to form a recurrence from a gf?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#20 2013-12-17 01:26:56

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: Getting the coefficient.

Hm, found it. It is very old.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#21 2013-12-17 01:33:58

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

I have a little routine that does these automatically.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#22 2013-12-17 01:46:41

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,176
Website

Re: Getting the coefficient.

But you have to write the routine manually, unless you use butterflies....


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#23 2013-12-17 01:49:30

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

I have written it long ago. The great DZ says you do not truly understand a piece of math until you program it.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#24 2013-12-17 02:00:05

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,176
Website

Re: Getting the coefficient.

Does it mean that Euclid, Euler, Pythagoras, Fibonacci did not know any math?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#25 2013-12-17 02:12:35

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,247

Re: Getting the coefficient.

Agnishom:That is exactly what he means. had they been around today they would program their ideas and even be smarter.

Anonimnystefy: Can you do the steps to get the recurrence because where I am going with this is to test the answer to the 10000 die problem which I believe is incorrect. Thus proving that method is kaboobly doo as stated in the other thread.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Board footer

Powered by FluxBB