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

You are not logged in.

- Topics: Active | Unanswered

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

This method is useful in enumerating strings which must avoid or contain a particular pattern.

Example 1:** Find the number of 5 digit numbers (does not start with 0), and does not contain '25'.**

We will first create a directed graph as in the diagram.

The corresponding adjacency matrix is:

For 5-digit numbers, we take the fifth power:

Sum of the first row gives the required number of strings, which is 86329

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

The recurrence relation for the problem is easy enough to find without a computer.

Anyway, once we have the matrix, it can be guessed by some CAS.

E.g. FriCAS has some routines for that.

To use it, we'll first calculate the first few terms

[1, 9 , 89 , 881 , 8721 , 86329 , 854569 , 8459361 , 83739041 , 828931049 , 8205571449]

and enter

`guessPRec [1 , 9 , 89 , 881 , 8721 , 86329 , 854569 , 8459361 , 83739041 , 828931049 , 8205571449]`

which gives

f(n): f(n + 2) - 10f(n + 1) + f(n)= 0,f(0)= 1,f(1)= 9

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Example 2:

**Find the number of 5 digit numbers (does not start with 0), and does not contain '25' and '52'.**

This can be found just by deleting one transition from the previous example. The matrix is given by:

and the guessed recurrence relation is

f(n): - n f(n + 2) + 9n f(n + 1) + 8n f(n)= 0,f(0)= 1,f(1)= 9

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

The recurrence relation can also be found by obtaining the characteristic polynomial of the matrix.

So, in example 2, the char. poly, is

The boxed part is the polynomial for the required recurrence, i.e.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,508

Hi gAr;

Very good!

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

**Online**

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Update:

Even better, we can directly get the generating function for every entry in the matrix.

There, totally eliminated the need for setting of initial conditions!

In our example 2, we add up the g.f's in the first row.

In Sage:

```
am=matrix([
[0 , 0 , 1 , 6 , 1 , 1],
[0 , 1 , 1 , 6 , 1 , 1],
[0 , 1 , 1 , 6 , 1 , 1],
[0 , 1 , 1 , 6 , 1 , 1],
[0 , 1 , 1 , 6 , 1 , 0],
[0 , 1 , 1 , 6 , 0 , 1]
])
sum((identity_matrix(6)-x*am).inverse()[0]).full_simplify()
```

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,508

Hi gAr;

I am getting

This matrix is singular so I can not invert.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

**Online**

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Looks like you subtracted from a ones-matrix!

Even maxima gets it right:

```
am:matrix(
[0 , 0 , 1 , 6 , 1 , 1],
[0 , 1 , 1 , 6 , 1 , 1],
[0 , 1 , 1 , 6 , 1 , 1],
[0 , 1 , 1 , 6 , 1 , 1],
[0 , 1 , 1 , 6 , 1 , 0],
[0 , 1 , 1 , 6 , 0 , 1]
)$
id:matrix(
[1,0,0,0,0,0],
[0,1,0,0,0,0],
[0,0,1,0,0,0],
[0,0,0,1,0,0],
[0,0,0,0,1,0],
[0,0,0,0,0,1]
)$
iam:invert(id-x*am)$
ratsimp(sum(iam[1,i],i,1,6));
```

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,508

Hi gAr;

What is x exactly?

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

**Online**

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

A formal variable for the g.f.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,508

Hi gAr;

Okay, everything working fine. I used to just get a recurrence for each element as I needed them. The gf for each one and all at once is nice. Very good!

83232 again!

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

**Online**

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Hi,

Yes, nice, isn't it?!

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,508

How did you come upon this?

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

**Online**

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

When I was reading this.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,508

Okay, thanks for the link. I enjoyed the whole thread very much.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

**Online**

**ElainaVW****Member**- Registered: 2013-04-29
- Posts: 580

Hello gAr;

Very pretty and I got it to work and understood it before Bobbym did!

Offline

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Hi bobbym,

You're welcome!

Hi ElainaVW,

Hope that you both enjoyed as much as I did!

It gets rid of the dreadful casework to come up with a recurrence, in some problems it's even hardly possible.

I think it's also possible to solve tiling problems like this.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,508

Yes, it might prove useful for other types.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

**Online**

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,479

Okay, taking a break, see you later.

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,508

See you later and thanks for coming in.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

**Online**