A003779 -id:A003779 - cp's OEIS frontend

A241606 A linear divisibility sequence of the fourth order related to A003779.

1, 11, 95, 781, 6336, 51205, 413351, 3335651, 26915305, 217172736, 1752296281, 14138673395, 114079985111, 920471087701, 7426955448000, 59925473898301, 483517428660911, 3901330906652795, 31478457514091281, 253988526230055936

Offset: 1

Peter Bala, Apr 26 2014

A003779, which counts spanning trees in the graph P_5 x P_n, is a linear divisibility sequence of order 16. It factors into two fourth-order linear divisibility sequences; this sequence is one of the factors, the other is A143699.

The present sequence is the case P1 = 11, P2 = 23, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy.

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 (11,-25,11,-1).

Cf. A003779, A100047, A143699.

a[n_] := ChebyshevU[n-1, 1/4*(7-Sqrt[5])]*ChebyshevU[n-1, 1/4*(7+Sqrt[5])]; Table[a[n]//Round, {n, 1, 20}] (* Jean-François Alcover, Apr 28 2014, after Peter Bala *)

O.g.f. x*(1 - x^2)/(1 - 11*x + 25*x^2 - 11*x^3 + x^4).
a(n) = A003779(n)/A143699(n).
a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), n >= 1, where alpha = 1/4*(11 + sqrt(29)), beta = 1/4*(11 - sqrt(29)) and where T(n,x) denotes the Chebyshev polynomial of the first kind.
a(n)= U(n-1,1/4*(7 - sqrt(5)))*U(n-1,1/4*(7 + sqrt(5))), n >= 1, where U(n,x) denotes the Chebyshev polynomial of the second kind.
a(n) = the bottom left entry of the 2X2 matrix T(n,M), where M is the 2 X 2 matrix [0, -23/4; 1, 11/2].
See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences.
a(n) = 11*a(n-1) - 25*a(n-2) + 11*a(n-3) - a(n-4). - Vaclav Kotesovec, Apr 28 2014

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

Original entry on oeis.org

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

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

Original entry on oeis.org

1, 1, 55, 209, 6336, 30305, 817991, 4140081, 108435745, 557568000, 14479521761, 74795194705, 1937528668711, 10021992194369, 259423766712000, 1342421467113969, 34741645659770711, 179796299139278305, 4652799879944138561

Offset: 0

Alois P. Heinz, Apr 15 2011

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

9th row of array A189006.

Bisection gives: A028471 (even part), A003779 (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[9, n];
a /@ Range[0, 18] (* Jean-François Alcover, Feb 27 2020, after Alois P. Heinz in A189006 *)

G.f.: -(x^30+x^29-154*x^28 +6777*x^26-1440*x^25-123961*x^24 +26752*x^23 +1132714*x^22-185889*x^21 -5684515*x^20+574750*x^19+16401668*x^18 -708928*x^17 -27757938*x^16+27757938*x^14+708928*x^13 -16401668*x^12 -574750*x^11+5684515*x^10 +185889*x^9-1132714*x^8-26752*x^7 +123961*x^6 +1440*x^5-6777*x^4+154*x^2-x-1) / (x^32-209*x^30+11936*x^28 -274208*x^26 +3112032*x^24-19456019*x^22 +70651107*x^20-152325888*x^18+196664896*x^16 -152325888*x^14+70651107*x^12 -19456019*x^10 +3112032*x^8-274208*x^6 +11936*x^4-209*x^2+1).

A339257 Number of spanning trees in the n X 5 king graph.

Original entry on oeis.org

1, 27648, 146356224, 698512774464, 3271331573452800, 15258885095892902976, 71111090441547013886784, 331335100372867196224868352, 1543757070688065237574186369344, 7192607774929149127350811889484864, 33511424900308657559195109303117533184, 156134620449573478209362729027690283037248

Offset: 1

Seiichi Manyama, Nov 29 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Spanning Tree

Column 5 of A338029.

Cf. A003779.

# Using graphillion
from graphillion import GraphSet
def make_nXk_king_graph(n, k):
    grids = []
    for i in range(1, k + 1):
        for j in range(1, n):
            grids.append((i + (j - 1) * k, i + j * k))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
            if i > 1:
                grids.append((i + (j - 1) * k, i + j * k - 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A338029(n, k):
    if n == 1 or k == 1: return 1
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    spanning_trees = GraphSet.trees(is_spanning=True)
    return spanning_trees.len()
def A339257(n):
    return A338029(n, 5)
print([A339257(n) for n in range(1, 15)])

Empirical g.f.: -x*(218700000000*x^8 - 2040471000000*x^7 + 538526880000*x^6 + 311791396500*x^5 - 17462695797*x^4 - 80280747*x^3 + 10513308*x^2 - 21759*x - 1) / (656100000000*x^8 - 4293081000000*x^7 + 4819127400000*x^6 - 930215250900*x^5 + 51621632181*x^4 - 1033572501*x^3 + 5949540*x^2 - 5889*x + 1). - Vaclav Kotesovec, Dec 09 2020

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

A241606 A linear divisibility sequence of the fourth order related to A003779.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A339257 Number of spanning trees in the n X 5 king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

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