A006238 -id:A006238 - cp's OEIS frontend

A161159 a(n) = A003739(n)/(5A001906(n)A006238(n)).

9, 245, 7776, 254035, 8336079, 273725760, 8988999201, 295197803645, 9694285226784, 318360072624475, 10454936893196391, 343339870595441280, 11275272921720374649, 370279686003420394565, 12159975800265309667296

Offset: 1

R. J. Mathar, Jun 03 2009

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

Vincenzo Librandi, Table of n, a(n) for n = 1..600
Index entries for linear recurrences with constant coefficients, signature (40,-248,430,-248,40,-1).

I:=[9,245,7776,254035,8336079,273725760]; [n le 6 select I[n] else 40*Self(n-1)-248*Self(n-2)+430*Self(n-3)-248*Self(n-4)+40*Self(n-5)-Self(n-6): n in [1..16]]; // Vincenzo Librandi, Dec 19 2012

seq(coeff(series(x*(9 -115*x +208*x^2 -115*x^3 +9*x^4)/((1-5*x+x^2)*(1-35*x+72*x^2-35*x^3+x^4)), x, n+1), x, n), n = 1..20); # G. C. Greubel, Dec 25 2019

CoefficientList[Series[(9-115x+208x^2-115x^3+9x^4)/((1-5x+x^2)*(1-35x+72x^2- 35x^3+x^4)), {x, 0, 20}], x] (* Vincenzo Librandi, Dec 19 2012 *)

my(x='x+O('x^30)); Vec(x*(9 -115*x +208*x^2 -115*x^3 +9*x^4)/((1-5*x+ x^2)*(1-35*x+72*x^2-35*x^3+x^4))) \\ G. C. Greubel, Dec 25 2019

def A161159_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x*(9 -115*x +208*x^2 -115*x^3 +9*x^4)/((1-5*x+x^2)*(1-35*x+72*x^2-35*x^3+x^4)) ).list()
a=A161159_list(30); a[1:] # G. C. Greubel, Dec 25 2019

a(n) = 40*a(n-1) -248*a(n-2) +430*a(n-3) -248*a(n-4) +40*a(n-5) -a(n-6).

G.f.: x*(9 -115*x +208*x^2 -115*x^3 +9*x^4)/((1-5*x+x^2)*(1-35*x+72*x^2-35*x^3 +x^4)).

A100047 A Chebyshev transform of the Fibonacci numbers.

Original entry on oeis.org

0, 1, 1, -1, -1, 0, -1, -1, 1, 1, 0, 1, 1, -1, -1, 0, -1, -1, 1, 1, 0, 1, 1, -1, -1, 0, -1, -1, 1, 1, 0, 1, 1, -1, -1, 0, -1, -1, 1, 1, 0, 1, 1, -1, -1, 0, -1, -1, 1, 1, 0, 1, 1, -1, -1, 0, -1, -1, 1, 1, 0, 1, 1, -1, -1, 0, -1, -1, 1, 1, 0, 1, 1, -1, -1, 0, -1, -1, 1, 1, 0, 1, 1, -1, -1, 0, -1, -1, 1, 1

Offset: 0

Paul Barry, Oct 31 2004

Multiplicative with a(p^e) = (-1)^(e+1) if p = 2, 0 if p = 5, 1 if p == 1 or 9 (mod 10), (-1)^e if p == 3 or 7 (mod 10). - David W. Wilson, Jun 10 2005
This sequence is a divisibility sequence, i.e., a(n) divides a(m) whenever n divides m. Case P1 = 1, P2 = -1, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Mar 24 2014
From Peter Bala, Mar 24 2014: (Start)
This is the particular case P1 = 1, P2 = -1, Q = 1 of the following results:
Let P1, P2 and Q be integers. Let alpha and beta denote the roots of the quadratic equation x^2 - 1/2*P1*x + 1/4*P2 = 0. Let T(n,x;Q) denote the bivariate Chebyshev polynomial of the first kind defined by T(n,x;Q) = 1/2*( (x + sqrt(x^2 - Q))^n + (x - sqrt(x^2 - Q))^n ) (when Q = 1, T(n,x;Q) reduces to the ordinary Chebyshev polynomial of the first kind T(n,x)). Then we have
1) The sequence A(n) := ( T(n,alpha;Q) - T(n,beta;Q) )/(alpha - beta) is a linear divisibility sequence of the fourth order.
2) A(n) belongs to the 3-parameter family of fourth-order divisibility sequences found by Williams and Guy.
3) The o.g.f. of the sequence A(n) is the rational function x*(1 - Q*x^2)/(1 - P1*x + (P2 + 2*Q)*x^2 - P1*Q*x^3 + Q^2*x^4).
4) The o.g.f. is the Chebyshev transform of the rational function x/(1 - P1*x + P2*x^2), where the Chebyshev transform takes the function A(x) to the function (1 - Q*x^2)/(1 + Q*x^2)*A(x/(1 + Q*x^2)).
5) Let q = sqrt(Q) and set a = sqrt( q + (P2)/(4*q) + (P1)/2 ) and b = sqrt( q + (P2)/(4*q) - (P1)/2 ). Then the o.g.f. of the sequence A(n) is the Hadamard product of the rational functions x/(1 - (a + b)*x + q*x^2) and x/(1 - (a - b)*x + q*x^2). Thus A(n) is the product of two (usually, non-integer) Lucas-type sequences.
6) A(n) = the bottom left entry of the 2 X 2 matrix 2*T(n,1/2*M;Q), where M is the 2 X 2 matrix [0, -P2; 1, P1].
For examples of the above see A006238, A054493, A078070, A092184, A098306, A100048, A108196, A138573, A152090 and A218134. (End)

			A Chebyshev transform of the Fibonacci numbers A000045: if A(x) is the g.f. of a sequence, map it to ((1-x^2)/(1+x^2))A(x/(1+x^2)).
The denominator is the 10th cyclotomic polynomial.
G.f. = x + x^2 - x^3 - x^4 - x^6 - x^7 + x^8 + x^9 + x^11 + x^12 - x^13 + ...

G. C. Greubel, Table of n, a(n) for n = 0..1000
Peter Bala, Linear divisibility sequences and Chebyshev polynomials
Tian-Xiao He, Peter J.-S. Shiue, An Approach to the Construction of Linear Divisibility Sequences of Higher Orders, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.2.
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 (1,-1,1,-1).

Other Chebyshev transforms: A011655, A099443, A100048.
Cf. A006238, A054493, A078070, A092184, A098306, A108196, A138573, A152090, A218134.
Cf. also A011558, A080891, A244895, A226162.

a := n -> (-1)^iquo(n, 5)*signum(mods(n, 5)):
seq(a(n), n=0..89); # after Michael Somos, Peter Luschny, Dec 30 2018

a[ n_] := {1, 1, -1, -1, 0, -1, -1, 1, 1, 0}[[Mod[ n, 10, 1]]]; (* Michael Somos, May 24 2015 *)
a[ n_] := (-1)^Quotient[ n, 5] Sign[ Mod[ n, 5, -2]]; (* Michael Somos, May 24 2015 *)
a[ n_] := (-1)^Quotient[n, 5] {1, 1, -1, -1, 0}[[Mod[ n, 5, 1]]]; (* Michael Somos, May 24 2015 *)
LinearRecurrence[{1, -1, 1, -1}, {0, 1, 1, -1}, 90] (* Jean-François Alcover, Jun 11 2019 *)

{a(n) = (-1)^(n\5) * [0, 1, 1, -1, -1][n%5+1]}; /* Michael Somos, May 24 2015 */

{a(n) = (-1)^(n\5) * sign( centerlift( Mod(n, 5)))}; /* Michael Somos, May 24 2015 */

G.f.: x*(1 - x^2)/(1 - x + x^2 - x^3 + x^4).
a(n) = a(n-1) - a(n-2) + a(n-3) - a(n-4).
a(n) = n*Sum_{k=0..floor(n/2)} (-1)^k *binomial(n-k, k)*A000045(n-2*k)/(n  -k).
From Peter Bala, Mar 24 2014: (Start)
a(n) = (T(n,alpha) - T(n,beta))/(alpha - beta), where alpha = (1 + sqrt(5))/4 and beta = (1 - sqrt(5))/4 and T(n,x) denotes the Chebyshev polynomial of the first kind.
a(n) = bottom left entry of the matrix T(n, M), where M is the 2 X 2 matrix [0, 1/4; 1, 1/2].
The o.g.f. is the Hadamard product of the rational functions x/(1 - 1/2*(sqrt(5) + 1)*x + x^2) and x/(1 - 1/2*(sqrt(5) - 1)*x + x^2). (End)
Euler transform of length 10 sequence [ 1, -2, 0, 0, -1, 0, 0, 0, 0, 1]. - Michael Somos, May 24 2015
a(n) = a(-n) = -a(n + 5) for all n in Z. - Michael Somos, May 24 2015
|A011558(n)| = |A080891(n)| = |a(n)| = A244895(n). - Michael Somos, May 24 2015

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

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

Original entry on oeis.org

1, 1, 8, 15, 95, 192, 1183, 2415, 14824, 30305, 185921, 380160, 2332097, 4768673, 29253160, 59817135, 366944287, 750331584, 4602858719, 9411975375, 57737128904, 118061508289, 724240365697, 1480934568960, 9084693297025, 18576479568193, 113956161827912

Offset: 0

Alois P. Heinz, Apr 15 2011

Alois P. Heinz, Table of n, a(n) for n = 0..550
Index entries for sequences related to dominoes
Index entries for linear recurrences with constant coefficients, signature (0,15,0,-32,0,15,0,-1).

5th row of array A189006.

Bisections give: A003775 (even part), A006238 (odd part).

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|15|-32|15>>^iquo(n, 2, 'r').
        `if`(r=0, <<8, 1, 1, 8>>, <<1, 0, 1, 15>>))[3, 1]:
seq(a(n), n=0..30);

a[n_] := Product[2(2+Cos[2 j Pi/(n+1)]+Cos[k Pi/3]), {k, 1, 2}, {j, 1, n/2} ] // Round;
Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Aug 19 2018, after A099390 *)

G.f.: (x-1)*(1+x)*(x^4+x^3-6*x^2+x+1) / (-x^8+15*x^6-32*x^4+15*x^2-1).

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)

A338532 Number of spanning trees in the n X 3 king graph.

Original entry on oeis.org

1, 192, 17745, 1612127, 146356224, 13286470095, 1206167003329, 109497763028928, 9940381426772625, 902403667119137183, 81921642989758089216, 7436977302591050167695, 675140651246077550931841, 61290344237862763973468352, 5564035123440571957929508305, 505111975464406109413779799007

Offset: 1

Seiichi Manyama, Nov 29 2020

nonn

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

Column 3 of A338029.

Cf. A006238.

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

Empirical g.f.: x*(-15*x^3 - 111*x^2 + 97*x + 1) / (x^4 - 95*x^3 + 384*x^2 - 95*x + 1). - Vaclav Kotesovec, Dec 04 2020

A003761 Number of spanning trees in D_4 X P_n.

Original entry on oeis.org

3, 270, 20160, 1477980, 108097935, 7903526400, 577834413429, 42245731959480, 3088601154192960, 225808743709815750, 16508958287605688193, 1206975861055570636800, 88242438021480689844999, 6451436286916714206370530, 471666820375043557337304000

Offset: 1

Frans J. Faase

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

Sean A. Irvine, Table of n, a(n) for n = 1..100
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
P. Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551 [math.CO], 2008. [From _Paul Raff_, Mar 06 2009]
P. Raff, Analysis of the Number of Spanning Trees of D_4 x P_n. Contains sequence, recurrence, generating function, and more. [From _Paul Raff_, Mar 06 2009]
Index entries for sequences related to trees
Index entries for linear recurrences with constant coefficients, signature (90,-1313,5850,-9828,5850,-1313,90,-1).

I:=[3,270,20160,1477980,108097935,7903526400, 577834413429,42245731959480]; [n le 8 select I[n] else 90*Self(n-1)-1313*Self(n-2)+5850*Self(n-3)-9828*Self(n-4)+5850*Self(n-5)-1313*Self(n-6)+90*Self(n-7)-Self(n-8): n in [1..20]]; // Vincenzo Librandi, Aug 03 2015

CoefficientList[Series[3 (x^6 - 67 x^4 + 180 x^3 - 67 x^2 + 1)/(x^8 - 90 x^7 + 1313 x^6 - 5850 x^5 + 9828 x^4 - 5850 x^3 + 1313 x^2 - 90 x + 1), {x, 0, 33}], x] (* Vincenzo Librandi, Aug 03 2015 *)

a(1) = 3,
a(2) = 270,
a(3) = 20160,
a(4) = 1477980,
a(5) = 108097935,
a(6) = 7903526400,
a(7) = 577834413429,
a(8) = 42245731959480 and
a(n) = 90*a(n-1) - 1313*a(n-2) + 5850*a(n-3) - 9828*a(n-4) + 5850*a(n-5) - 1313*a(n-6) + 90*a(n-7) - a(n-8).
G.f.: 3*x*(x^6 -67*x^4 +180*x^3 -67*x^2 +1) / (x^8 -90*x^7 +1313*x^6 -5850*x^5 +9828*x^4 -5850*x^3 +1313*x^2 -90*x +1). - Paul Raff, Mar 06 2009
a(n) = 3*A006238(n)*A001109(n). [R. Guy, seqfan list, Mar 28 2009] - R. J. Mathar, Jun 03 2009

Recurrence from Faase's web page added by N. J. A. Sloane, Feb 03 2009

More terms from Sean A. Irvine, Aug 02 2015

A140824 Expansion of (x-x^3)/(1-3x+2x^2-3*x^3+x^4).

Original entry on oeis.org

0, 1, 3, 6, 15, 41, 108, 281, 735, 1926, 5043, 13201, 34560, 90481, 236883, 620166, 1623615, 4250681, 11128428, 29134601, 76275375, 199691526, 522799203, 1368706081, 3583319040, 9381251041, 24560434083, 64300051206, 168339719535, 440719107401, 1153817602668

Offset: 0

N. J. A. Sloane, Sep 07 2009, based on email from R. K. Guy, Mar 09 2009

Case P1 = 3, P2 = 0, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Mar 25 2014

G. C. Greubel, Table of n, a(n) for n = 0..1000
Peter Bala, Linear divisibility sequences and Chebyshev polynomials
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 (3,-2,3,-1).

Cf. A006238, A005248, A054493, A078070, A092184, A098306, A100047, A100048, A108196, A138573, A152090, A218134.

LinearRecurrence[{3, -2, 3, -1}, {0, 1, 3, 6}, 50] (* G. C. Greubel, Aug 08 2017 *)

x='x+O('x^50); concat([0], Vec((x-x^3)/(1-3*x+2*x^2-3*x^3+x^4))) \\ G. C. Greubel, Aug 08 2017

a(0) = 0, a(1) = 1, a(2) = 3, a(3) = 6, a(n) - 3 a(n + 1) + 2 a(n + 2) - 3 a(n + 3) + a(n + 4) = 0.
From Peter Bala, Mar 25 2014: (Start)
a(n) = 2/3*( T(n,3/2) - T(n,0) ), where T(n,x) is a Chebyshev polynomial of the first kind.
a(n) = 1/3 * (A005248(n) - (i^n + (-i)^n)) = 1/3 * (Fibonacci(2*n-1) + Fibonacci(2*n+1) - (i^n + (-i)^n)).
a(n) = bottom left entry of the 2 X 2 matrix 2*T(n, 1/2*M), where M is the 2 X 2 matrix [0, 0; 1, 3].
The o.g.f. is the Hadamard product of the rational functions x/(1 - 1/sqrt(2)*(sqrt(5) + i)*x + x^2) and x/(1 - 1/sqrt(2)*(sqrt(5) - i)*x + x^2). See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End)
a(n) = A099483(n) - A099483(n-2). - R. J. Mathar, Feb 10 2016

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

A161159 a(n) = A003739(n)/(5*A001906(n)*A006238(n)).

Views

Author

Keywords

Comments

Links

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A100047 A Chebyshev transform of the Fibonacci numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

A338532 Number of spanning trees in the n X 3 king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A003761 Number of spanning trees in D_4 X P_n.

Views

Author

Keywords

References

Links

Programs

Magma

A161159 a(n) = A003739(n)/(5A001906(n)A006238(n)).

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

A140824 Expansion of (x-x^3)/(1-3x+2x^2-3*x^3+x^4).