|
| |
|
|
A116469
|
|
Number of spanning trees in an m X n grid read by antidiagonals.
|
|
2
| |
|
|
1, 1, 1, 1, 4, 1, 1, 15, 15, 1, 1, 56, 192, 56, 1, 1, 209, 2415, 2415, 209, 1, 1, 780, 30305, 100352, 30305, 780, 1, 1, 2911, 380160, 4140081, 4140081, 380160, 2911, 1, 1, 10864, 4768673, 170537640, 557568000, 170537640, 4768673, 10864, 1, 1
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,5
|
|
|
COMMENTS
| This is the number of ways the points in an m x n grid can be connected to their orthogonal neighbours such that for any pair of points there is precisely one path connecting them
a(n,n) = A007341(n)
a(m,n)= number of perfect mazes made from a grid of m-by-n cells. - Leroy Quet Sep 08 2007
Also number of domino tilings of the (2m-1) X (2n-1) rectangle with upper left corner removed. For m=2, n=3 the 15 domino tilings of the 3 X 5 rectangle with upper left corner removed are:
. .___.___. . .___.___. . .___.___. . .___.___. . .___.___.
._|___|___| ._|___|___| ._| | |___| ._|___|___| ._| |___| |
| |___|___| | | | |___| | |_|_|___| |___| |___| | |_|___|_|
|_|___|___| |_|_|_|___| |_|___|___| |___|_|___| |_|___|___|
. .___.___. . .___.___. . .___.___. . .___.___. . .___.___.
._|___|___| ._|___|___| ._| | |___| ._|___|___| ._|___|___|
| |___| | | | | | | | | | |_|_| | | |___| | | | | | |___| |
|_|___|_|_| |_|_|_|_|_| |_|___|_|_| |___|_|_|_| |_|_|___|_|
. .___.___. . .___.___. . .___.___. . .___.___. . .___.___.
._|___| | | ._|___| | | ._| | | | | ._|___| | | ._|___|___|
| |___|_|_| | | | |_|_| | |_|_|_|_| |___| |_|_| |___|___| |
|_|___|___| |_|_|_|___| |_|___|___| |___|_|___| |___|___|_|
- Alois P. Heinz, Apr 15 2011
|
|
|
EXAMPLE
| a(2,2) = 4, since we must have exactly 3 of the 4 possible connections: if we have all 4 there are multiple paths between points; if we have fewer some points will be isolated from others.
Array begins:
1, 1, 1, 1, 1, 1, ...
1, 4, 15, 56, 209, 780, ...
1, 15, 192, 2415, 30305, 380160, ...
1, 56, 2415, 100352, 4140081, 170537640, ...
1, 209, 30305, 4140081, 557568000, 74795194705, ...
1, 780, 380160, 170537640, 74795194705, 32565539635200, ...
|
|
|
CROSSREFS
| Diagonal gives: A007341. Rows and columns 1-6 give: A000012, A001353, A006238, A003696, A003779, A139400.
Sequence in context: A141724 A157211 A176428 * A156599 A155826 A010320
Adjacent sequences: A116466 A116467 A116468 * A116470 A116471 A116472
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Calculated by Hugo van der Sanden (hv(AT)crypt.org) after a suggestion from Leroy Quet, Mar 20 2006.
|
| |
|
|
