Math Is Fun Forum

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Finite State Machines / Directed Graphs for counting problems

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

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Finite State Machines / Directed Graphs for counting problems

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

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Finite State Machines / Directed Graphs for counting problems

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

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Finite State Machines / Directed Graphs for counting problems

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.

---

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

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Finite State Machines / Directed Graphs for counting problems

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Finite State Machines / Directed Graphs for counting problems

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()

---

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

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Finite State Machines / Directed Graphs for counting problems

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Finite State Machines / Directed Graphs for counting problems

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));

---

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

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Finite State Machines / Directed Graphs for counting problems

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Finite State Machines / Directed Graphs for counting problems

A formal variable for the g.f.

---

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

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Finite State Machines / Directed Graphs for counting problems

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Finite State Machines / Directed Graphs for counting problems

Hi,

Yes, nice, isn't it?!

---

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

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Finite State Machines / Directed Graphs for counting problems

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Finite State Machines / Directed Graphs for counting problems

When I was reading this.

---

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

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Finite State Machines / Directed Graphs for counting problems

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.

ElainaVW

Member

Registered: 2013-04-29

Posts: 580

Re: Finite State Machines / Directed Graphs for counting problems

Hello gAr;

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

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Finite State Machines / Directed Graphs for counting problems

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.

---

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

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Finite State Machines / Directed Graphs for counting problems

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Finite State Machines / Directed Graphs for counting problems

Okay, taking a break, see you later.

---

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

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Finite State Machines / Directed Graphs for counting problems

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.