A003696 -id:A003696 - cp's OEIS frontend

A161158 a(n) = A003696(n+1)/A001353(n+1).

1, 14, 161, 1792, 19809, 218638, 2412353, 26614784, 293628097, 3239445006, 35739069409, 394290020096, 4349990523425, 47991114171406, 529460241815169, 5841251080892416, 64443392518654337, 710969410782059534

Offset: 0

R. J. Mathar, Jun 03 2009

Proposed by R. Guy in the seqfan list Mar 28 2009.

With an offset of 1, this sequence is the case P1 = 14, P2 = 32, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Apr 27 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..900
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 (14,-34,14,-1).

Cf. A001563, A003696, A100047.

a:=[1,14,161,1792];; for n in [5..20] do a[n]:=14*a[n-1]-34*a[n-2] +14*a[n-3] -a[n-4]; od; a; # G. C. Greubel, Dec 24 2019

I:=[1,14,161,1792]; [n le 4 select I[n] else 14*Self(n-1)-34*Self(n-2) +14*Self(n-3)-Self(n-4): n in [1..30]]; // Vincenzo Librandi, Apr 28 2014

seq(simplify( ChebyshevU(n, (4+sqrt(2))/2)*ChebyshevU(n, (4-sqrt(2))/2) ), n = 0 .. 20); # G. C. Greubel, Dec 24 2019

CoefficientList[Series[(1-x^2)/(1-14x+34x^2-14x^3+x^4), {x, 0, 20}], x] (* Vincenzo Librandi, Apr 28 2014 *)
Table[Simplify[ChebyshevU[n, (4+Sqrt[2])/2]*ChebyshevU[n, (4-Sqrt[2])/2]], {n, 0, 20}] (* G. C. Greubel, Dec 24 2019 *)

vector(21, n, round(polchebyshev(n-1, 2, (4+sqrt(2))/2)*polchebyshev(n-1, 2, (4-sqrt(2))/2)) ) \\ G. C. Greubel, Dec 24 2019

[round(chebyshev_U(n,(4+sqrt(2))/2)*chebyshev_U(n,(4-sqrt(2))/2)) for n in (0..20)] # G. C. Greubel, Dec 24 2019

a(n) = 14*a(n-1) -34*a(n-2) +14*a(n-3) -a(n-4).
G.f.: (1-x^2)/(1-14*x+34*x^2-14*x^3+x^4).
From Peter Bala, Apr 27 2014: (Start)
The following remarks assume an offset of 1.
a(n) = (1/sqrt(17))*( T(n,(7 + sqrt(17))/2) - T(n,(7 - sqrt(17))/2) ), where T(n,x) is the Chebyshev polynomial of the first kind.
a(n) = the bottom left entry of the 2 X 2 matrix T(n,M), where M is the 2 X 2 matrix [0, -8; 1, 7].
a(n) = U(n-1,1/2*(4 + sqrt(2)))*U(n-1,1/2*(4 - sqrt(2))), where U(n,x) is the Chebyshev polynomial of the second kind.
See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)

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

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

Original entry on oeis.org

1, 1, 21, 56, 781, 2415, 31529, 100352, 1292697, 4140081, 53175517, 170537640, 2188978117, 7022359583, 90124167441, 289143013376, 3710708201969, 11905151192865, 152783289861989, 490179860527896, 6290652543875133

Offset: 0

Alois P. Heinz, Apr 15 2011

Alois P. Heinz, Table of n, a(n) for n = 0..400
Index entries for sequences related to dominoes
Index entries for linear recurrences with constant coefficients, signature (0, 56, 0, -672, 0, 2632, 0, -4094, 0, 2632, 0, -672, 0, 56, 0, -1).

7th row of array A189006.

Bisection gives: A028469 (even part), A003696 (odd part).

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[7, n];
a /@ Range[0, 20] (* Jean-François Alcover, Feb 27 2020, after Alois P. Heinz in A189006 *)

G.f.: -(x^14-x^13-35*x^12+277*x^10 +49*x^9-727*x^8 -112*x^7+727*x^6 +49*x^5-277*x^4 +35*x^2-x-1) / (x^16-56*x^14 +672*x^12-2632*x^10 +4094*x^8-2632*x^6 +672*x^4-56*x^2+1).

A338617 Number of spanning trees in the n X 4 king graph.

Original entry on oeis.org

1, 2304, 1612127, 1064918960, 698512774464, 457753027631164, 299940605530116319, 196531575367664678400, 128774089577828985307985, 84377085408032081020147412, 55286683084713553039968700608, 36225680193828279388607070447232, 23736274839549237072891352060244017

Offset: 1

Seiichi Manyama, Nov 29 2020

nonn

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

Column 4 of A338029.

Cf. A003696.

# 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 A338617(n):
    return A338029(n, 4)
print([A338617(n) for n in range(1, 20)])

Empirical g.f.: x*(56*x^7 + 7072*x^6 - 162708*x^5 + 371791*x^4 + 18080*x^3 - 49920*x^2 + 1556*x + 1) / (x^8 - 748*x^7 + 61345*x^6 - 368764*x^5 + 680848*x^4 - 368764*x^3 + 61345*x^2 - 748*x + 1). - Vaclav Kotesovec, Dec 04 2020

A212799 Row 4 of array in A212796.

Original entry on oeis.org

4, 2304, 367500, 42467328, 4381392020, 428652000000, 40643137651228, 3771854305099776, 344499209234302500, 31074298464967845120, 2774871814779003772844, 245741556726521856000000, 21611621448116558812137652, 1889376666754339457990201088, 164334311374716912516773437500

Offset: 1

N. J. A. Sloane, May 27 2012

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..24
Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. See p. 210, Parag. 4.

Cf. A003696, A212796, A212798.

Table[2^(6*n-4)*n*Product[Sin[j*Pi/4]^2 + Sin[k*Pi/n]^2, {j,1,3}, {k,1,n-1}], {n,1,20}]//Round (* Vaclav Kotesovec, Feb 26 2021 *)

# Using graphillion
from graphillion import GraphSet
def make_CnXCk(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))
        grids.append((i + (n - 1) * k, i))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
        grids.append((i + k - 1, i))
    return grids
def A212799(n):
    if n == 1: return 4
    if n == 2: return 2304
    universe = make_CnXCk(4, n)
    GraphSet.set_universe(universe)
    spanning_trees = GraphSet.trees(is_spanning=True)
    return spanning_trees.len()
print([A212799(n) for n in range(1, 8)])  # Seiichi Manyama, Nov 22 2020

From Vaclav Kotesovec, Feb 26 2021: (Start)
a(n) ~ (21 + 12*sqrt(3) + 2*sqrt(2*(97 + 56*sqrt(3))))^n * n/4.
G.f.: 4*x*(1 + 310*x - 33278*x^2 + 785814*x^3 + 4923451*x^4 - 476492324*x^5 + 8394222196*x^6 - 74272031652*x^7 + 371582629705*x^8 - 981246223862*x^9 + 441533151262*x^10 + 6161037199338*x^11 - 23802532730757*x^12 + 46995963516168*x^13 - 58240430817576*x^14 + 46995963516168*x^15 - 23802532730757*x^16 + 6161037199338*x^17 + 441533151262*x^18 - 981246223862*x^19 + 371582629705*x^20 - 74272031652*x^21 + 8394222196*x^22 - 476492324*x^23 + 4923451*x^24 + 785814*x^25 - 33278*x^26 + 310*x^27 + x^28)/ ((1 - x)^2*(1 - 14*x + x^2)^2*(1 - 6*x + x^2)^2*(1 - 4*x + x^2)^2* (1 - 84*x + 230*x^2 - 84*x^3 + x^4)^2*(1 - 24*x + 50*x^2 - 24*x^3 + x^4)^2). (End)

a(10)-a(15) from Seiichi Manyama, Nov 22 2020

A360195 Number of acyclic spanning subgraphs in the 4 X n grid graph.

Original entry on oeis.org

8, 836, 85818, 8790016, 900013270, 92146956300, 9434262852690, 965904015750408, 98891686243392270, 10124779093041746052, 1036600283636692454794, 106129737227642833341248, 10865828704552798371380934, 1112470797598979236296844092, 113897550673086022197853291458

Offset: 1

Andrew Howroyd, Jan 29 2023

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, signature (146,-5145,74504,-525120,1885344,-3430128,3147392,-1418496,278528,-16384).

Row 4 of A360194.

Cf. A003696, A359991.

G.f.: x*(8 - 332*x + 4922*x^2 - 34224*x^3 + 120160*x^4 - 215504*x^5 + 196576*x^6 - 88512*x^7 + 17408*x^8 - 1024*x^9)/(1 - 146*x + 5145*x^2 - 74504*x^3 + 525120*x^4 - 1885344*x^5 + 3430128*x^6 - 3147392*x^7 + 1418496*x^8 - 278528*x^9 + 16384*x^10).

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

A161158 a(n) = A003696(n+1)/A001353(n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A338617 Number of spanning trees in the n X 4 king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A212799 Row 4 of array in A212796.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A360195 Number of acyclic spanning subgraphs in the 4 X n grid graph.

Views

Author

Keywords

Links

Crossrefs

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