You are not logged in.

- Topics: Active | Unanswered

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

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,462

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,462

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,462

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****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 83,251

Hi gAr;

Very good!

**In mathematics, you don't understand things. You just get used to them.I have the result, but I do not yet know how to get it.All physicists, and a good many quite respectable mathematicians are contemptuous about proof.**

Offline

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

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****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 83,251

Hi gAr;

I am getting

This matrix is singular so I can not invert.

I have the result, but I do not yet know how to get it.

All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

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

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****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 83,251

Hi gAr;

What is x exactly?

I have the result, but I do not yet know how to get it.

All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

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

A formal variable for the g.f.

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 83,251

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!

I have the result, but I do not yet know how to get it.

All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

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

Hi,

Yes, nice, isn't it?!

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 83,251

How did you come upon this?

I have the result, but I do not yet know how to get it.

All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

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

When I was reading this.

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 83,251

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

I have the result, but I do not yet know how to get it.

All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

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

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,462

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****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 83,251

Yes, it might prove useful for other types.

I have the result, but I do not yet know how to get it.

All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

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

Okay, taking a break, see you later.

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 83,251

See you later and thanks for coming in.

I have the result, but I do not yet know how to get it.

All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline