Grid problem (or nonintersecting rook path problem)


Someone in Intermediate Counting posed the following problem as a generalization of a class problem:

Given an m by n grid, how many ways are there to get from one corner to the diagonally opposite corner moving horizontally and vertically such that no tile is used more than once?

(I know I posted this problem before. Sorry about that.) Thanks to the Encyclopedia of Integer Sequences, we now know more terms for the square grid cases: 1, 2, 12, 184, 8512, 1262816, 575780564, etc. (They have a few more on the Encyclopedia of Integer Sequences.) It’s sequence A007764 if anyone cares. Let us call the terms a_n, and let b_n=a_n/a_{n-1}. I did think that lim_{n\to\infty} b_n/b_{n-1}=3. Now I really don’t know. The first few terms of b_n/b_{n-1} are 3, 2.5556, 3.0170, 3.2070, 3.0733, 3.0068, 3.0186, 3.0362, 3.0419, 3.0423. That’s a weird sequence. I don’t understand it. It would be interesting if the limit turns out to be pi, but I don’t think that will be the case.

Advertisements

About Simon

Hi. I'm Simon Rubinstein-Salzedo. I'm a mathematics postdoc at Dartmouth College. I'm also a musician; I play piano and cello, and I also sometimes compose music and study musicology. I also like to play chess and write calligraphy. This blog is a catalogue of some of my thoughts. I write them down so that I understand them better. But sometimes other people find them interesting as well, so I happily share them with my small corner of the world.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s