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

You are not logged in.

#1 2013-12-24 18:07:31

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

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

View Image: pattern.png

"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

#2 2013-12-24 18:23:29

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

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

Offline

#3 2013-12-24 18:32:34

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

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

Offline

#4 2013-12-24 21:55:36

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

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

Offline

#5 2013-12-24 23:46:04

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,763

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#6 2014-04-02 04:47:48

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

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

Offline

#7 2014-04-02 06:27:10

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,763

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#8 2014-04-02 17:24:28

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

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

Offline

#9 2014-04-02 19:16:08

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,763

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#10 2014-04-02 22:42:38

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

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

Offline

#11 2014-04-03 04:55:11

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,763

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#12 2014-04-03 05:51:04

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

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

Offline

#13 2014-04-03 06:27:05

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,763

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#14 2014-04-03 15:47:53

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

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

Offline

#15 2014-04-03 15:50:30

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,763

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#16 2014-04-03 16:16:21

ElainaVW
Member
Registered: 2013-04-29
Posts: 291

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!

Offline

#17 2014-04-03 19:03:06

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

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

Offline

#18 2014-04-03 20:10:42

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,763

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

#19 2014-04-03 20:14:52

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

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

Offline

#20 2014-04-03 20:16:05

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,763

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.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

Board footer

Powered by FluxBB