Mathematics desk
< November 5	<< Oct \| November \| Dec >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 6

Number of routes on a square grid

I've been considering a grid of integral points on the square with corners (0,0) and (n,n), for varying n. Specifically, the number of routes from (0,1) to (1,0) with steps parallel to the axes, neither passing through (0,0) nor visiting any other point more than once. For n=1 and n=2 it's easy to see that there are 1 and 7 routes respectively, and for n=3 I think that there are 70 (from a laborious drawing of the possibilities, with any larger case totally impracticable by this method). Is this correct, and is there a general formula? Putting 1,7,70 into OEIS didn't give anything recognisable as this problem.→31.51.161.12 (talk) 10:49, 6 November 2016 (UTC)[reply]

I think you’ve discovered an application of Pascal’s triangle. It certainly includes 70 in the middle of one of its rows; I can’t see it on that page but from memory. The formula is on that page, while there’s an OEIS page here: [1]. --JohnBlackburne^words_deeds 10:58, 6 November 2016 (UTC)[reply]

Pretty sure you're thinking of the case where you're going from corner to corner and taking the minimum possible steps; this is different. More specifically, 7 is in Pascal's triangle but not on the diagonal.

It would be helpful to not be restricted to squares, so define P(m,n) to be the number of paths for the rectangle from (0, 0) to (m, n). Then is pretty easy to see that P(1,n) = n. I believe it can be shown that for a fixed m, the values of P(m, n) as a function of n have a recursive formula, which in turn can give you information about how fast it grows.

If you fill in the edges from (0, 0) then you get cycles so you might think of this as a special case of the problem of counting simple cycles in a graph. These are contain in something called the cycle space which is actually very easy to enumerated. You might also think of the problem as counting the number of ~~ways to divide a rectangle into at most two polyominos~~ simply connected polyominos in a rectangle which contain a given corner square. --RDBury (talk) 16:54, 6 November 2016 (UTC)[reply]

When you said "the number of routes from (0,1) to (1,0)", did you really mean "from (0,n) to (n,0)" ? This should be the same as from (0,0) to (n,n). StuRat (talk) 17:15, 6 November 2016 (UTC)[reply]

Except (0, 0) is being excluded and I don't see why you would do that if you're going from corner to corner. Assuming what the OP meant is what is written, then the values of P(2,n) are 2, 7, 19, 48, ... which are partial sums of the Pell numbers. Also, I made a correction to something in my previous post. --RDBury (talk) 18:03, 6 November 2016 (UTC)[reply]

OK, looks like the OP didn't mean corner to corner after all. StuRat (talk) 15:33, 7 November 2016 (UTC)[reply]

Knuth's Simpath algorithm might be applicable to this problem. Also, oeis:A007764 covers the problem of counting paths going from corner to corner. And I made another correction to my statement above; it might be correct this time. --RDBury (talk) 06:13, 7 November 2016 (UTC)[reply]

(OP) (0,1) to (1,0) excluding (0,0) is the same as (0,0) to (0,0) if the direction is ignored, it just seemed a clearer way of defining what I meant. Can anyone confirm 70 for n=3, and give numerical values for any higher n? And indeed a recurrence relation, if an explicit formula in n is not possible? Thanks to all so far.→31.51.161.12 (talk) 14:58, 7 November 2016 (UTC)[reply]

I got 97 for n=3 and I checked it couple different ways so I'm pretty confident that it's at least closer to the actual number than 70. I don't want to try to list them all but I'll give you a break down by length to help narrow down where the discrepancies are. I don't think an explicit formula or a recurrence relation is realistic given what I've been reading about similar problems. For example the number corner to corner paths is listed in the OEIS (see above) but apparently the values are known only up to n=26 and judging from the number of different people who found the different values it took a major computational effort to get the values that are known. If there was a recurrence relation then the values wouldn't be that hard to find.

It does seem like this sequence should be in the OEIS though since there are already related sequences. This first thing I would suggest though is to not insist on squares but look at rectangles as well. The OEIS lists corner to corner counts that way too at oeis:A064298. The advantage would be that you can find recurrence relations for individual rows (or columns) of the array. The complexity of these recurrences would grow exponentially as you go down the table though.

Another thing I'd suggest to include the path through (0,0), which would increase all the values by one. This would be equivalent to including the empty path when you state the problem as counting paths from (0,0) to (0,0). It seems like a simpler way to state the problem and I noticed that the generating functions were a bit simpler when you added one to the values. For example the second row of the array is already in the OEIS (oeis:A048739, partial sums of Pell numbers) if you add 1 to the values. --RDBury (talk) 19:00, 7 November 2016 (UTC)[reply]

I promised the number of paths by length for n=3: 1 (length 2), 2 (length 4), 6 (length 6), 18 (length 8), 40 (length 10), 24 (length 12), 6 (length 14). There was some "laborious drawing of the possibilities" involved but the values should be close at least. --RDBury (talk) 19:40, 7 November 2016 (UTC)[reply]

Thanks. I agree with the figure of 97, from a program to simulate possible routes from start to finish, but with no explanation of how my set of drawn routes was so lacking - the systematic approach clearly wasn't systematic enough.→31.51.161.12 (talk) 17:16, 9 November 2016 (UTC)[reply]

Name of graph

I'd like to know the name of a particular mathematical graph, if one exists. Basically, it's an ordered list of which each element is itself an ordered list.

For example:

L₂ = 1243.23, 1302.0, 1302.1, 32445.98992
L₅ = 32.8, 563345.089, 2322678.76, 2322678.76, 2332123.333
L₂₄ = 232.09, 342.91, 356.87, 376.76, 379.44, 382.21, 453.98
L₁₁₄₃ = 1433.03
L₁₁₆₅ = 54332, 76778, 77345.0, 77665

Notice that the index (identifier) of each sublist is not necessarily increasing by one (2, 5, 24, 1143, 1165 rather than 1, 2, 3, 4, 5). Another graph can contain far more sublists and elements than are presented here but each example of this type of graph is finite, both vertically (2, 5, 7 ...) and horizontally (1234.23, 1302.0 ...).

Each vertical element (sublist index) is unique but each horizontal element may have duplicates (see the third and four element of sublist index 5). A sublist may not exist without at least one element. The indexes and elements may, of course, be anything: letters, symbols or anything else on which an order may be imposed.

Pictorially, the above is represented by the following bi-unidirectional graph:

G =

2 => 1243.23 > 1302.0 > 1302.1 > 32445.98992

V

5 => 32.8 > 563345.089 > 2322678.76 > 2322678.76 > 2332123.333

V

24 => 232.09 > 342.91 > 356.87 > 376.76 > 379.44 > 382.21 > 453.98

V

1143 => 1433.03

V

1165 => 54332 > 76778 > 77345.0 > 77665

Each vertical sublist index has two directed pointers: one accessing the first horizontal element of that sublist and one accessing the next vertical index. Each horizontal element has only one pointer (to the next element in that sublist). Thus the whole graph can only be accessed by a pointer to the first sublist index (in this case, 2).

So, is this anywhere close to a named mathematical graph (or other mathematical term)? Perhaps this is closer to a data structure in computers? Any help would be appreciated. --RoyGoldsmith (talk) 23:48, 6 November 2016 (UTC)[reply]

This looks more like a data structure than something to do with graph theory. You might call it a list of lists or a lookup table of lists and you could easily implement them in, say, Python. The way you have it drawn you might also call them rooted trees which are a type of graph but are used more in computer algorithms than in graph theory. --RDBury (talk) 19:51, 7 November 2016 (UTC)[reply]

Seems like a jagged array to me. -- Meni Rosenfeld (talk) 21:26, 7 November 2016 (UTC)[reply]

The problem with a jagged array is that it doesn't contain sublist indices (2, 5, etc.). A jagged array would look something like this:

=> 1243.23 > 1302.0 > 1302.1 > 32445.98992

=> 32.8 > 563345.089 > 2322678.76 > 2322678.76 > 2332123.333

=> 232.09 > 342.91 > 356.87 > 376.76 > 379.44 > 382.21 > 453.98

=> 1433.03

=> 54332 > 76778 > 77345.0 > 77665

However, could my graph be a rooted forest, a disjoint union of rooted trees? --RoyGoldsmith (talk) 13:39, 8 November 2016 (UTC)[reply]

Well, if you want you could have a jagged array where some of the sublists are null. Then the "sublist indices" would be the indices for which the sublist is non-null, with the rest ignored. But possibly this will not be efficient for the operations you want. -- Meni Rosenfeld (talk) 14:33, 8 November 2016 (UTC)[reply]