A139400 -id:A139400 - cp's OEIS frontend

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

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

Offset: 1

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

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

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

Seiichi Manyama, Antidiagonals n = 1..50, flattened
Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. - From _N. J. A. Sloane_, May 27 2012

Diagonal gives A007341. Rows and columns 1..10 give A000012, A001353, A006238, A003696, A003779, A139400, A334002, A334003, A334004, A334005.

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

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 *)

T(n,m) = polresultant(polchebyshev(n-1, 2, x/2), polchebyshev(m-1, 2, (4-x)/2)); \\ Michel Marcus, Apr 13 2020

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A116469(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    spanning_trees = GraphSet.trees(is_spanning=True)
    return spanning_trees.len()
print([A116469(j + 1, i - j + 1) for i in range(9) for j in range(i + 1)])  # Seiichi Manyama, Apr 12 2020

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

A210724 Number of domino tilings of the 11 X n grid with upper left corner removed iff n is odd.

Original entry on oeis.org

1, 1, 144, 780, 51205, 380160, 21001799, 170537640, 8940739824, 74795194705, 3852472573499, 32565539635200, 1666961188795475, 14143261515284447, 722364079570222320, 6136973985625588560, 313196612952258199679, 2662079368040434932480, 135818983640055277506397

Offset: 0

Alois P. Heinz, Mar 30 2012

Alois P. Heinz, Table of n, a(n) for n = 0..250
Index entries for sequences related to dominoes

11th row of array A189006.

Bisection gives: A028473 (even part), A139400 (odd part).

A[1, 1] = 1;
A[m_, n_] := A[m, n] = Module[{i, j, s, t, M}, Which[m == 0 || n == 0, 1, m < n, A[n, m], True, s = Mod[n*m, 2]; M[i_, j_] /; j < i := -M[j, i]; M[, ] = 0; For[i = 1, i <= n, i++, For[j = 1, j <= m, j++, t = (i - 1)*m + j - s; If[i > 1 || j > 1 || s == 0, If[j < m, M[t, t + 1] = 1]; If[i < n, M[t, t + m] = 1 - 2*Mod[j, 2]]]]]; Sqrt[Det[Array[M, {n*m - s, n*m - s}]] ]]];
a[n_] := A[11, n];
a /@ Range[0, 18] (* Jean-François Alcover, Feb 27 2020, after Alois P. Heinz in A189006 *)

a(n) = 780*a(n-2) -194881*a(n-4) +22377420*a(n-6)
-1419219792*a(n-8) +55284715980*a(n-10)
-1410775106597*a(n-12) +24574215822780*a(n-14)
-300429297446885*a(n-16) +2629946465331120*a(n-18)
-16741727755133760*a(n-20) +78475174345180080*a(n-22)
-273689714665707178*a(n-24) +716370537293731320*a(n-26)
-1417056251105102122*a(n-28) +2129255507292156360*a(n-30)
-2437932520099475424*a(n-32) +2129255507292156360*a(n-34)
-1417056251105102122*a(n-36) +716370537293731320*a(n-38)
-273689714665707178*a(n-40) +78475174345180080*a(n-42)
-16741727755133760*a(n-44) +2629946465331120*a(n-46)
-300429297446885*a(n-48) +24574215822780*a(n-50)
-1410775106597*a(n-52) +55284715980*a(n-54)
-1419219792*a(n-56) +22377420*a(n-58)
-194881*a(n-60) +780*a(n-62) -a(n-64).

A161498 Expansion of x(1-x)(1+x)/(1-13x+36x^2-13*x^3+x^4).

Original entry on oeis.org

1, 13, 132, 1261, 11809, 109824, 1018849, 9443629, 87504516, 810723277, 7510988353, 69584925696, 644660351425, 5972359368781, 55329992188548, 512595960817837, 4748863783286881, 43995092132369664, 407585519020921249

Offset: 1

R. J. Mathar, Jun 11 2009

Proposed by R. Guy in the seqfan list, Mar 29 2009.

The sequence is the case P1 = 13, P2 = 34, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Apr 03 2014

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume
Index entries for linear recurrences with constant coefficients, signature (13,-36,13,-1)

Cf. A006238, A100047.

I:=[1,13,132,1261]; [n le 4 select I[n] else 13*Self(n-1)-36*Self(n-2)+13*Self(n-3)-Self(n-4): n in [1..20]]; // Vincenzo Librandi, Dec 19 2012

CoefficientList[Series[(1 - x)*(1 + x)/(1 - 13*x + 36*x^2 - 13*x^3 + x^4), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 19 2012 *)

a(n) = A139400(n) / ( A001906(n)*A001353(n)*A004254(n) ).
a(n) = 13*a(n-1)-36*a(n-2)+13*a(n-3)-a(n-4).
a(n) = A187732(n)-A187732(n-2). - R. J. Mathar, Mar 18 2011
From Peter Bala, Apr 03 2014: (Start)
a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), where alpha = 1/4*(13 + sqrt(33)), beta = 1/4*(13 - sqrt(33)) and where T(n,x) denotes the Chebyshev polynomial of the first kind.
a(n) = U(n-1,1/2*(4 + sqrt(3) ))*U(n-1,1/2*(4 - sqrt(3))) for n >= 1, where U(n,x) denotes the Chebyshev polynomial of the second kind.
a(n) = bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, -17/2; 1, 13/2].
See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)

A278417 a(n) = n*((2+sqrt(3))^n + (2-sqrt(3))^n)/2.

Original entry on oeis.org

0, 2, 14, 78, 388, 1810, 8106, 35294, 150536, 632034, 2620870, 10759342, 43804812, 177105266, 711809378, 2846259390, 11330543632, 44929049794, 177540878718, 699402223118, 2747583822740, 10766828545746, 42095796462874, 164244726238366, 639620518118424, 2486558615814050, 9651161613824822, 37403957244654702

Offset: 0

Indranil Ghosh, Nov 21 2016

This was originally based on a graph theory formula in the Wikipedia which turned out to be wrong.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (8,-18,8,-1).

Cf. A030019, A069996, A139400, A193153.

f:=n->expand(n*((2+sqrt(3))^n + (2-sqrt(3))^n)/2); # N. J. A. Sloane, May 13 2017

Table[Simplify[(n/2) (((2 + #)^n + (2 - #)^n)) &@ Sqrt@ 3], {n, 3, 27}] (* or *)
Drop[#, 3] &@ CoefficientList[Series[2 x^3*(39 - 118 x + 55 x^2 - 7 x^3)/(1 - 4 x + x^2)^2, {x, 0, 27}], x] (* Michael De Vlieger, Nov 24 2016 *)
LinearRecurrence[{8,-18,8,-1},{0,2,14,78},30] (* Harvey P. Dale, Jan 01 2021 *)

vector(25, n, n+=2; n*((2+sqrt(3))^n + ((2-sqrt(3))^n))/2) \\ Colin Barker, Nov 21 2016

Vec(2*x^3*(39 - 118*x + 55*x^2 - 7*x^3) / (1 - 4*x + x^2)^2 + O(x^30)) \\ Colin Barker, Nov 21 2016

def a278417(n):
    a = [0, 2, 14, 78, 388, 1810]
    if n < 6:
        return a[n]
    for k in range(n - 5):
        a = a[1:] + [7*a[-1] - 10*a[-2] - 10*a[-3] + 7*a[-4] - a[-5]]
    return a[-1]
# David Radcliffe, May 09 2025

From Colin Barker, Nov 21 2016: (Start)
a(n) = 7*a(n-1) - 10*a(n-2) - 10*a(n-3) + 7*a(n-4) - a(n-5) for n>6.
G.f.: 2*x^3*(39 - 118*x + 55*x^2 - 7*x^3) / (1 - 4*x + x^2)^2.
(End)

Entry revised by N. J. A. Sloane, May 13 2017

A338832 Number of spanning trees in the k_1 X ... X k_j grid graph, where (k_1 - 1, ..., k_j - 1) is the partition with Heinz number n.

Original entry on oeis.org

1, 1, 1, 4, 1, 15, 1, 384, 192, 56, 1, 31500, 1, 209, 2415, 42467328, 1, 49766400, 1, 2558976, 30305, 780, 1, 3500658000000, 100352, 2911, 8193540096000, 207746836, 1, 76752081000, 1, 20776019874734407680, 380160, 10864, 4140081, 242716067758080000000, 1

Offset: 1

Pontus von Brömssen, Nov 11 2020

nonn

a(n) > 1 precisely when n is composite.

			The partition (2, 2, 1) has Heinz number 18 and the 3 X 3 X 2 grid graph has a(18) = 49766400 spanning trees.

Pontus von Brömssen, Table of n, a(n) for n = 1..1151
Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory B 24 (1978), 202-212.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Spanning Tree
Index entries for sequences related to trees

X n grid: A001353(n) = a(2*prime(n-1))
X n grid: A006238(n) = a(3*prime(n-1))
X n grid: A003696(n) = a(5*prime(n-1))
X n grid: A003779(n) = a(7*prime(n-1))
X n grid: A139400(n) = a(11*prime(n-1))
X n grid: A334002(n) = a(13*prime(n-1))
X n grid: A334003(n) = a(17*prime(n-1))
X n grid: A334004(n) = a(19*prime(n-1))
X n grid: A334005(n) = a(23*prime(n-1))
n X n grid: A007341(n) = a(prime(n-1)^2)
m X n grid: A116469(m,n) = a(prime(m-1)*prime(n-1))
X 2 X n grid: A003753(n) = a(4*prime(n-1))
X n X n grid: A067518(n) = a(2*prime(n-1)^2)
n X n X n grid: A071763(n) = a(prime(n-1)^3)
X ... X 2 grid: A006237(n) = a(2^n)

a(n) = Product_{n_1=0..k_1-1, ..., n_j=0..k_j-1; not all n_i=0} Sum_{i=1..j} (2*(1 - cos(n_i*Pi/k_i))) / Product_{i=1..j} k_i, where (k_1 - 1, ..., k_j - 1) is the partition with Heinz number n.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A210724 Number of domino tilings of the 11 X n grid with upper left corner removed iff n is odd.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A161498 Expansion of x*(1-x)*(1+x)/(1-13*x+36*x^2-13*x^3+x^4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A278417 a(n) = n*((2+sqrt(3))^n + (2-sqrt(3))^n)/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A338832 Number of spanning trees in the k_1 X ... X k_j grid graph, where (k_1 - 1, ..., k_j - 1) is the partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A161498 Expansion of x(1-x)(1+x)/(1-13x+36x^2-13*x^3+x^4).