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

You are not logged in.

- Topics: Active | Unanswered

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

This is what you should have:

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

You see it now?

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

Wait, that's the residue method?

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

Hm, I've already seen this method.

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

Hi bobbym

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

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

With another method?

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

That is correct! That brings us to Part 2.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

Shoot!

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

I understand everything except hiw you formed the recurrence.

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

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.**

**If it ain't broke, fix it until it is.**

Offline

**anonimnystefy****Real Member**- From: Harlan's World
- Registered: 2011-05-23
- Posts: 15,937

Hm, found it. It is very old.

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

The knowledge of some things as a function of age is a delta function.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

I have a little routine that does these automatically.

**In mathematics, you don't understand things. You just get used to them.**

**If it ain't broke, fix it until it is.**

Offline

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'

'But our love is like the wind. I can't see it but I can feel it.' -A Walk to remember

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

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.**

**If it ain't broke, fix it until it is.**

Offline

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'

'But our love is like the wind. I can't see it but I can feel it.' -A Walk to remember

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 96,639

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.**

**If it ain't broke, fix it until it is.**

Offline