| Displaying 1-5 of 5 results found.
page
1
A linear divisibility sequence of the fourth order related to A003779.
+20
2
1, 11, 95, 781, 6336, 51205, 413351, 3335651, 26915305, 217172736, 1752296281, 14138673395, 114079985111, 920471087701, 7426955448000, 59925473898301, 483517428660911, 3901330906652795, 31478457514091281, 253988526230055936
COMMENTS
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.
FORMULA
O.g.f. x*(1 - x^2)/(1 - 11*x + 25*x^2 - 11*x^3 + x^4).
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
MATHEMATICA
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 *)
Square array read by antidiagonals: T(m,n) = number of spanning trees in an m X n grid.
+10
26
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
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(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:
. .___.___. . .___.___. . .___.___. . .___.___. . .___.___.
._|___|___| ._|___|___| ._| | |___| ._|___|___| ._| |___| |
| |___|___| | | | |___| | |_|_|___| |___| |___| | |_|___|_|
|_|___|___| |_|_|_|___| |_|___|___| |___|_|___| |_|___|___|
. .___.___. . .___.___. . .___.___. . .___.___. . .___.___.
._|___|___| ._|___|___| ._| | |___| ._|___|___| ._|___|___|
| |___| | | | | | | | | | |_|_| | | |___| | | | | | |___| |
|_|___|_|_| |_|_|_|_|_| |_|___|_|_| |___|_|_|_| |_|_|___|_|
. .___.___. . .___.___. . .___.___. . .___.___. . .___.___.
._|___| | | ._|___| | | ._| | | | | ._|___| | | ._|___|___|
| |___|_|_| | | | |_|_| | |_|_|_|_| |___| |_|_| |___|___| |
|_|___|___| |_|_|_|___| |_|___|___| |___|_|___| |___|___|_|
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
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 *)
PROG
(Python)
# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
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()
(PARI) T(n, m) = polresultant(polchebyshev(n-1, 2, x/2), polchebyshev(m-1, 2, (4-x)/2)); \\ Michel Marcus, Apr 13 2020
Number of domino tilings of the 9 X n grid with upper left corner removed iff n is odd.
+10
3
1, 1, 55, 209, 6336, 30305, 817991, 4140081, 108435745, 557568000, 14479521761, 74795194705, 1937528668711, 10021992194369, 259423766712000, 1342421467113969, 34741645659770711, 179796299139278305, 4652799879944138561
FORMULA
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).
MATHEMATICA
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];
Number of spanning trees in the n X 5 king graph.
+10
3
1, 27648, 146356224, 698512774464, 3271331573452800, 15258885095892902976, 71111090441547013886784, 331335100372867196224868352, 1543757070688065237574186369344, 7192607774929149127350811889484864, 33511424900308657559195109303117533184, 156134620449573478209362729027690283037248
FORMULA
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
PROG
(Python)
# 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
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()
print([ A339257(n) for n in range(1, 15)])
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.
+10
1
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
COMMENTS
a(n) > 1 precisely when n is composite.
FORMULA
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.
EXAMPLE
The partition (2, 2, 1) has Heinz number 18 and the 3 X 3 X 2 grid graph has a(18) = 49766400 spanning trees.
CROSSREFS
2 X n grid: A001353(n) = a(2*prime(n-1)) 3 X n grid: A006238(n) = a(3*prime(n-1)) 4 X n grid: A003696(n) = a(5*prime(n-1)) 5 X n grid: A003779(n) = a(7*prime(n-1)) 6 X n grid: A139400(n) = a(11*prime(n-1)) 7 X n grid: A334002(n) = a(13*prime(n-1)) 8 X n grid: A334003(n) = a(17*prime(n-1)) 9 X n grid: A334004(n) = a(19*prime(n-1)) 10 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)) 2 X 2 X n grid: A003753(n) = a(4*prime(n-1)) 2 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) 2 X ... X 2 grid: A006237(n) = a(2^n)
Search completed in 0.011 seconds
| 