login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A116469 Square array read by antidiagonals: T(m,n) = number of spanning trees in an m X n grid. 8
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; text; 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 neighbors 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 X 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

Each row (and column) of the square array is a divisibility sequence, i.e., if n divides m then a(n) divides a(m). It follows that the main diagonal, A007341, is also a divisibility sequence. Row k satisfies a linear recurrence of order 2^k. - Peter Bala, Apr 29 2014

LINKS

Table of n, a(n) for n=1..46.

Germain Kreweras, Complexite et circuits Euleriens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. - From N. J. A. Sloane, May 27 2012

FORMULA

T(m,n) = Product_{k=1..n-1} Product_{h=1..m-1} (4*sin(h*Pi/(2*m))^2 + 4*sin(k*Pi/(2*n))^2); [Kreweras] - N. J. A. Sloane, May 27 2012

Equivalently, T(n,m) = resultant( U(n-1,x/2), U(m-1,(4-x)/2 ) = Product_{k = 1..n-1} Product_{h = 1..m-1} (4 - 2*cos(h*Pi/m) - 2*cos(k*Pi/n)), where U(n,x) denotes the Chebyshev polynomial of the second kind. The divisibility properties of the array mentioned in the Comments follow from this representation. - Peter Bala, Apr 29 2014

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

MAPLE

Digits:=200;

T:=(m, n)->round(Re(evalf(simplify(expand(

mul(mul( 4*sin(h*Pi/(2*m))^2+4*sin(k*Pi/(2*n))^2, h=1..m-1), k=1..n-1)))))); # crude Maple program from N. J. A. Sloane, May 27 2012

MATHEMATICA

T[m_, n_] := Product[4 Sin[h Pi/(2 m)]^2 + 4 Sin[k Pi/(2 n)]^2, {h, m - 1}, {k, n - 1}]; Flatten[Table[FullSimplify[T[k, r - k]], {r, 2, 10}, {k, 1, r - 1}]] (* Ben Branman, Mar 10 2013 *)

CROSSREFS

Diagonal gives A007341. Rows and columns 1..6 give A000012, A001353, A006238, A003696, A003779, A139400.

Sequence in context: A320280 A157211 A176428 * A156599 A155826 A010320

Adjacent sequences:  A116466 A116467 A116468 * A116470 A116471 A116472

KEYWORD

nonn,tabl

AUTHOR

Calculated by Hugo van der Sanden after a suggestion from Leroy Quet, Mar 20 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 23 15:00 EST 2020. Contains 332166 sequences. (Running on oeis4.)