FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
number of grid network combinations
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
Author Message
JeeBee
science forum beginner


Joined: 18 Dec 2005
Posts: 9

PostPosted: Wed Dec 21, 2005 9:22 am    Post subject: number of grid network combinations Reply with quote

Suppose I have a MxN grid network,
(MxN nodes, (M-1)(N-1) boxes (cells),
2M(N-1) edges).
But cells surrounded by three edges are not allowed (I call these invalid
positions).
Example: (the grid does not have to be connected)
+-+ +-+
| | |
+ +-+-+

If the number of edges e = 2M(N-1), then a simple upperbound
on the number of grid networks is 2^e.

I already found that the number of valid 2xn positions is
p_n + q_n, defined as:

p_n = (4 3)^n * 7
q_n (3 2) 5
(2x2 matrix to the n-th power multiplied by vector (7 5)).

- Can somebody generalize this equation to MxN networks?
- Can somebody specify a function that maps the numbers
{0,1,2,...,p} exactly to all valid positions?
(where p is the total number of valid positions).

The former I think is very well possible, though I'm a bit stuck there.
The latter might be very difficult.

Maybe it can be done in a different way, starting like this:
There are 12 valid 2x2 boxes:
2^4 - 4 invalid boxes = 12. The 4 invalid boxes are:
+-+ +-+ + + +-+
| | | | | |
+ + +-+ +-+ +-+

For two boxes AB, there are about half of 12^2 boxes, because they
share one edge (using the above function I know the exact answer is
74, indeed about half of 12^2).
+ + +
A B
+ + +
Then perhaps add a third box C, and (later?) fourth box D
+ + +
A B
+ + +
C D
+ + +
Maybe it is possible to construct a difference equation like I did for
this case?

Any comments are very welcome,
JeeBee.
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Thu Dec 22, 2005 6:30 am    Post subject: Re: number of grid network combinations Reply with quote

JeeBee wrote:
Quote:
Suppose I have a MxN grid network,
(MxN nodes, (M-1)(N-1) boxes (cells),
2M(N-1) edges).
But cells surrounded by three edges are not allowed (I call these invalid
positions).

I assume you can have two or one or no edges around a cell ...

Quote:
Example: (the grid does not have to be connected)
+-+ +-+
| | |
+ +-+-+

If the number of edges e = 2M(N-1), then a simple upperbound
on the number of grid networks is 2^e.

I already found that the number of valid 2xn positions is
p_n + q_n, defined as:

p_n = (4 3)^n * 7
q_n (3 2) 5
(2x2 matrix to the n-th power multiplied by vector (7 5)).

You can probably also get this by setting up and solving a recurrance.

Quote:
- Can somebody generalize this equation to MxN networks?

I mention a possible approach below. Difficult but not impossible.

Quote:
- Can somebody specify a function that maps the numbers
{0,1,2,...,p} exactly to all valid positions?
(where p is the total number of valid positions).

That would be interesting. You could think of mapping p to a binary
string of length 4mn, where a 1 means there's a certain edge present,
next to a certain square, and a 0 means otherwise. The hard part would
be making sure that the network is consistent; i.e., the edge between
two neighboring squares is either there for both squares or absent for
both squares. I'll have to think about the map from p to the binary
strings for a while.

Your example above (of a bad network) ---

Quote:
+-+ +-+
| | |
+ +-+-+

--- could be coded as 1111 1111 1011, where each block of 4 refers to
the corresponding square, and whether the edges are present is
determined by the block of 4. The edges, in order, are top, right,
bottom, left.

You can tell this is a bad network, because one of the blocks (the last
one) has 3 1's in it. The hard part is maintaining "consistency"; for
instance, there is no network for the binary string
1111 1110 1111.

Quote:
The former I think is very well possible, though I'm a bit stuck there.
The latter might be very difficult.

The second might be easier (for the 2xn case) than the first (for the
mxn case).

Quote:
Maybe it can be done in a different way, starting like this:
There are 12 valid 2x2 boxes:
2^4 - 4 invalid boxes = 12. The 4 invalid boxes are:
+-+ +-+ + + +-+
| | | | | |
+ + +-+ +-+ +-+

For two boxes AB, there are about half of 12^2 boxes, because they
share one edge (using the above function I know the exact answer is
74, indeed about half of 12^2).
+ + +
A B
+ + +
Then perhaps add a third box C, and (later?) fourth box D
+ + +
A B
+ + +
C D
+ + +
Maybe it is possible to construct a difference equation like I did for
this case?

You might want to try using Inclusion-Exclusion, where you let A(m,n)
be the set of all networks where the (m,n) cell has exactly 3 edges
around it. That will get messy, but you can truncate the formula and
get a lower or upper bound. (Bonferroni's Inequalities)

The IE formula is at
http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html (You'd
be using formula (3).)

A(m,n) = 2^(e-4) * 4, since there are 4 edges around the (m,n) cell,
and you're choosing the one which is not in the network. (We're
counting "bad guys" here.) Then there are 2^(e-4) ways to choose
whether each of the other edges is in the network or not; these edges
don't affect whether the network is in A(m,n).

Thus the number of "bad guys" is at most (mn) * 2^(e-4) * 4, so the
number of good networks is at least
2^e - m n 2^(e-2). (I incorporated the 4 into the 2^*.)

Now if you can count the number of networks where the (m,n) and (p,q)
cells have exactly 3 edges around them, you can use the next term of
the IE formula to get a lower bound on the number of bad networks. This
has to be broken into cases, whether (m,n) is adjacent to (p,q) or not,
and whether at least one of these squares is in a corner or along an
edge.

It's messy, but not too bad. I wouldn't want to take the next step,
though.

--- Christopher Heckman
Back to top
JeeBee
science forum beginner


Joined: 18 Dec 2005
Posts: 9

PostPosted: Thu Dec 22, 2005 10:19 am    Post subject: Re: number of grid network combinations Reply with quote

Thanks Christopher!

Quote:
I assume you can have two or one or no edges around a cell ...

Sorry if I wasn't really clear here. I meant one or two or four,
but not three.

I am talking about the game dots-and-boxes. If there are exactly three
moves around a box, the value does not need to be stored in the database,
because it can be looked up from several other positions quickly
(by either taking all boxes or leaving one or two double-crosses).
(later I will also add rotation/mirrorring and the fact that the outer
two corner moves (for all four corners) are exactly equal to each other).

Quote:
p_n = (4 3)^n * 7
q_n (3 2) 5
(2x2 matrix to the n-th power multiplied by vector (7 5)).

You can probably also get this by setting up and solving a recurrance.

I did, and this was the solution of those recurrent equations Smile
p_n = 4 * p_{n-1} + 3 * q_{n-1}
q_n = 3 * p_{n-1} + 2 * q_{n-1} (if i'm not mistaking...)
with p_2=7, q_2=5

Quote:
- Can somebody specify a function that maps the numbers
{0,1,2,...,p} exactly to all valid positions? (where p is the total
number of valid positions).

The above function is needed to compute the database index given a
position. That is why I don't want any numbers skipped, because that would
increase the size of my database.

Quote:
Your example above (of a bad network) ---

So this network is actually a good one (one I do want in the database).
It's value should be -2, because the player to move will lose the two
remaining boxes.

Quote:
+-+ +-+
| | |
+ +-+-+

You might want to try using Inclusion-Exclusion, where you let A(m,n) be
the set of all networks where the (m,n) cell has exactly 3 edges around
it. That will get messy, but you can truncate the formula and get a lower
or upper bound. (Bonferroni's Inequalities)

The IE formula is at
http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html (You'd be
using formula (3).)

Thank you for this!
JeeBee.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
The time now is Mon Jun 26, 2017 10:36 pm | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts how to deduce a number validation algorithm? Tim_Mac Math 1 Fri Jul 21, 2006 10:43 am
No new posts a subset of natural number levine121323@yahoo.com Math 1 Fri Jul 21, 2006 6:17 am
No new posts Another look at triangle number factoring. Dan11 Math 2 Tue Jul 18, 2006 7:05 pm
No new posts Hofstadter's _GEB_ -- Help with number theory Daniel al-Autistiqui Math 3 Tue Jul 18, 2006 5:33 pm
No new posts Number Theory Danilo num-analysis 1 Sat Jul 15, 2006 2:57 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0260s ][ Queries: 16 (0.0046s) ][ GZIP on - Debug on ]