cp's OEIS Frontend

A116469 Square array read by antidiagonals: T(m,n) = number of spanning trees in an m X n grid.

%I A116469 #82 Jan 23 2025 10:25:36
%S A116469 1,1,1,1,4,1,1,15,15,1,1,56,192,56,1,1,209,2415,2415,209,1,1,780,
%T A116469 30305,100352,30305,780,1,1,2911,380160,4140081,4140081,380160,2911,1,
%U A116469 1,10864,4768673,170537640,557568000,170537640,4768673,10864,1
%N A116469 Square array read by antidiagonals: T(m,n) = number of spanning trees in an m X n grid.
%C A116469 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.
%C A116469 a(n,n) = A007341(n).
%C A116469 a(m,n) = number of perfect mazes made from a grid of m X n cells. - _Leroy Quet_, Sep 08 2007
%C A116469 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:
%C A116469 . .___.___. . .___.___. . .___.___. . .___.___. . .___.___.
%C A116469 ._|___|___| ._|___|___| ._| | |___| ._|___|___| ._| |___| |
%C A116469 | |___|___| | | | |___| | |_|_|___| |___| |___| | |_|___|_|
%C A116469 |_|___|___| |_|_|_|___| |_|___|___| |___|_|___| |_|___|___|
%C A116469 . .___.___. . .___.___. . .___.___. . .___.___. . .___.___.
%C A116469 ._|___|___| ._|___|___| ._| | |___| ._|___|___| ._|___|___|
%C A116469 | |___| | | | | | | | | | |_|_| | | |___| | | | | | |___| |
%C A116469 |_|___|_|_| |_|_|_|_|_| |_|___|_|_| |___|_|_|_| |_|_|___|_|
%C A116469 . .___.___. . .___.___. . .___.___. . .___.___. . .___.___.
%C A116469 ._|___| | | ._|___| | | ._| | | | | ._|___| | | ._|___|___|
%C A116469 | |___|_|_| | | | |_|_| | |_|_|_|_| |___| |_|_| |___|___| |
%C A116469 |_|___|___| |_|_|_|___| |_|___|___| |___|_|___| |___|___|_|
%C A116469    - _Alois P. Heinz_, Apr 15 2011
%C A116469 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
%H A116469 Seiichi Manyama, <a href="/A116469/b116469.txt">Antidiagonals n = 1..50, flattened</a>
%H A116469 Germain Kreweras, <a href="http://dx.doi.org/10.1016/0095-8956(78)90021-7">Complexité et circuits Eulériens dans les sommes tensorielles de graphes</a>, J. Combin. Theory, B 24 (1978), 202-212. - From _N. J. A. Sloane_, May 27 2012
%F A116469 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
%F A116469 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
%e A116469 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.
%e A116469 Array begins:
%e A116469   1,   1,      1,         1,           1,              1, ...
%e A116469   1,   4,     15,        56,         209,            780, ...
%e A116469   1,  15,    192,      2415,       30305,         380160, ...
%e A116469   1,  56,   2415,    100352,     4140081,      170537640, ...
%e A116469   1, 209,  30305,   4140081,   557568000,    74795194705, ...
%e A116469   1, 780, 380160, 170537640, 74795194705, 32565539635200, ...
%p A116469 Digits:=200;
%p A116469 T:=(m,n)->round(Re(evalf(simplify(expand(
%p A116469 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
%t A116469 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 *)
%o A116469 (Python)
%o A116469 # Using graphillion
%o A116469 from graphillion import GraphSet
%o A116469 import graphillion.tutorial as tl
%o A116469 def A116469(n, k):
%o A116469     if n == 1 or k == 1: return 1
%o A116469     universe = tl.grid(n - 1, k - 1)
%o A116469     GraphSet.set_universe(universe)
%o A116469     spanning_trees = GraphSet.trees(is_spanning=True)
%o A116469     return spanning_trees.len()
%o A116469 print([A116469(j + 1, i - j + 1) for i in range(9) for j in range(i + 1)])  # _Seiichi Manyama_, Apr 12 2020
%o A116469 (PARI) T(n,m) = polresultant(polchebyshev(n-1, 2, x/2), polchebyshev(m-1, 2, (4-x)/2)); \\ _Michel Marcus_, Apr 13 2020
%Y A116469 Diagonal gives A007341. Rows and columns 1..10 give A000012, A001353, A006238, A003696, A003779, A139400, A334002, A334003, A334004, A334005.
%K A116469 nonn,tabl
%O A116469 1,5
%A A116469 Calculated by _Hugo van der Sanden_ after a suggestion from _Leroy Quet_, Mar 20 2006