A006235 -id:A006235 - cp's OEIS frontend

A173958 Number A(n,k) of spanning trees in C_k X P_n; square array A(n,k), n>=1, k>=1, read by antidiagonals.

1, 2, 1, 3, 12, 1, 4, 75, 70, 1, 5, 384, 1728, 408, 1, 6, 1805, 31500, 39675, 2378, 1, 7, 8100, 508805, 2558976, 910803, 13860, 1, 8, 35287, 7741440, 140503005, 207746836, 20908800, 80782, 1, 9, 150528, 113742727, 7138643400, 38720000000, 16864848000, 479991603, 470832, 1

Offset: 1

Alois P. Heinz, Nov 26 2010

Every row and every column of the array is a divisibility sequence, i.e., the terms satisfy the property that if n divides m then a(n) divides a(m) provided a(n) > 0. This follows from the representation of the elements of the array as a resultant. - Peter Bala, May 01 2014

			Square array A(n,k) begins:
  1,    2,      3,         4,           5,  ...
  1,   12,     75,       384,        1805,  ...
  1,   70,   1728,     31500,      508805,  ...
  1,  408,  39675,   2558976,   140503005,  ...
  1, 2378, 910803, 207746836, 38720000000,  ...

Alois P. Heinz, Antidiagonals n = 1..60, flattened
Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. See p. 210. - From _N. J. A. Sloane_, May 27 2012
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Path Graph
Wikipedia, Kirchhoff's theorem

Columns k=1-11 give: A000012, A001542, A003690, A003753, A003733, A158880, A158898, A210812, A174001, A210813, A174089.
Rows n=1-2 give: A000027, A006235.
Main diagonal gives A252767.
Cf. A156308.

with(LinearAlgebra):
A:= proc(n, m) local M, i, j;
     if m=1 then 1 else
      M:= Matrix(n*m, shape=symmetric);
      for i to n do
        for j to m-1 do M[m*(i-1)+j, m*(i-1)+j+1]:=-1 od;
        M[m*(i-1)+1, m*i]:= M[m*(i-1)+1, m*i]-1
      od;
      for i to n-1 do
        for j to m do M[m*(i-1)+j, m*i+j]:=-1 od
      od;
      for i to n*m do
        M[i,i]:= -add(M[i,j], j=1..n*m)
      od;
      Determinant(DeleteColumn(DeleteRow(M, 1), 1))
     fi
    end:
seq(seq(A(n, 1+d-n), n=1..d), d=1..9);
# Crude Maple program from N. J. A. Sloane, May 27 2012:
Digits:=200;
T:=(m,n)->round(Re(evalf(simplify(expand(
m*mul(mul( 4*sin(h*Pi/m)^2+4*sin(k*Pi/(2*n))^2, h=1..m-1), k=1..n-1))))));
# Alternative program using the resultant:
for n from 1 to 10 do seq(k*resultant(simplify((2*(ChebyshevT(k,(x + 2)/2) - 1))/x), simplify(ChebyshevU(n-1,1 - x/2)), x), k = 1 .. 10) end do; # Peter Bala, May 01 2014

t[m_, n_] := m*Product[Product[4*Sin[h*Pi/m]^2 + 4*Sin[k*Pi/(2*n)]^2, {h, 1, m-1}], {k, 1, n-1}]; Table[t[m, n-m+1] // Round, {n, 1, 9}, {m, n, 1, -1}] // Flatten (* Jean-François Alcover, Dec 05 2013, after N. J. A. Sloane *)

A(n,k) = m*Prod(Prod( 4*sin(h*Pi/m)^2+4*sin(k*Pi/(2*n))^2, h=1..m-1), k=1..n-1) [Kreweras]. - From N. J. A. Sloane, May 27 2012

Let T(n,x) and U(n,x) denote the Chebyshev polynomials of the first and second kind respectively. Let R(n,x) = 2*( T(n,(x + 2)/2) - 1 )/x (the row polynomials of A156308). Then the (n,k)-th element of the array equals k times the resultant (R(k,x), U(n-1,(2 - x)/2)). - Peter Bala, May 01 2014 [Corrected by Pontus von Brömssen, Apr 08 2025]

A006237 Complexity of tensor sum of n graphs; or spanning trees on n-cube.

Original entry on oeis.org

1, 1, 4, 384, 42467328, 20776019874734407680, 1657509127047778993870601546036901052416000000, 153850844349814660487100539994381178281567942393055761257560677644718869248475136000000000000000000000

Offset: 0

N. J. A. Sloane, Don Knuth

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.6.10.

Alois P. Heinz, Table of n, a(n) for n = 0..10
Aaron R. Bagheri, Classifying the Jacobian Groups of Adinkras, (2017), HMC Senior Theses.
Frank Harary, John P. Hayes, and Horng-Jyh Wu, A survey of the theory of hypercube graphs, Comput. Math. Appl., 15(4) (1988), 277-289.
D. E. Knuth, Letter to N. J. A. Sloane, Oct. 1994
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.
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Spanning Tree
Index entries for sequences related to trees

Cf. A006235.

Table[2^(2^n - 1 - n) Product[k^Binomial[n, k], {k, n}], {n, 0, 10}]

a(n)=2^(2^n-n-1)*prod(k=1,n,k^binomial(n,k))

a(n) = 2^(2^n-1-n)*1^binomial(n, 1)*2^binomial(n, 2)*...*n^binomial(n, n).

Description expanded July 1995

A072373 Complexity of doubled cycle (regarding case n = 2 as a graph).

Original entry on oeis.org

1, 4, 75, 384, 1805, 8100, 35287, 150528, 632025, 2620860, 10759331, 43804800, 177105253, 711809364, 2846259375, 11330543616, 44929049777, 177540878700, 699402223099, 2747583822720, 10766828545725, 42095796462852, 164244726238343, 639620518118400, 2486558615814025

Offset: 1

Michael Somos, Jul 19 2002

Stefano Spezia, Table of n, a(n) for n = 1..1700
Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212.
Index entries for linear recurrences with constant coefficients, signature (10,-35,52,-35,10,-1).

Apart from a(2) coincides with A006235.

/* prism (or doubled cycle) graph with n vertices */ prism(n)=if(n%2,[;],matrix(n,n,i,j,i!=j && ((abs(i-j)==1 && (i+j)!=n+1) || (abs(i-j)==n/2-1 && (i+j)%n==n/2+1) || abs(i-j)==n/2)))

/* treenumber (or complexity) of a graph */ treenumber(m)=local(n); n=matdim(m); if(n,matdet(adj2laplace(m)+matone(n))/n^2)

/* convert adjacency matrix to laplacian matrix */ adj2laplace(m)=local(l,n); n=matdim(m); matdiagonal(m*vectorv(n,i,1))-m

/* matrix J of all ones */ matone(n)=matrix(n,n,i,j,1) /* dimension of a square matrix */ matdim(m)=matsize(m)[1]

PARI
```
a(n)=treenumber(prism(2*n))
```

a(n)=if(n<0,0,polcoeff(-8*x^2+x*(1+2*x-10*x^2+2*x^3+x^4)/((1-x)*(1-4*x+x^2))^2+x*O(x^n),n))

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

a(n) = 10*a(n-1)-35*a(n-2)+52*a(n-3)-35*a(n-4)+10*a(n-5)-a(n-6), n>8.

A175243 Array read by antidiagonals: total number of spanning trees R_n(m) of the complete prism K_m X C_n.

Original entry on oeis.org

1, 2, 1, 3, 12, 3, 4, 75, 294, 16, 5, 384, 11664, 16384, 125, 6, 1805, 367500, 5647152, 1640250, 1296, 7, 8100, 10609215, 1528823808, 6291456000, 259200000, 16807, 8, 35287, 292626432, 380008339280, 18911429680500, 13556617751088, 59549251454

Offset: 1

R. J. Mathar, Mar 13 2010

			The array starts in row n=1 as:
  1,    1,        3,         16,        125
  2,   12,      294,      16384,    1640250
  3,   75,    11664,    5647152, 6291456000
  4,  384,   367500, 1528823808,
  5, 1805, 10609215,

F. T. Boesch and H. Prodinger, Spanning tree formulas and Chebyshev polynomials, Graphs Combinat. 2 (1986) 191-200.
Index entries for sequences related to trees

Cf. A006235 (column 2), A000272, A212798 (column 3).

A175243 := proc(n,m) n*2^(m-1)/m*( orthopoly[T](n,1+m/2)-1)^(m-1) ; end proc:
for d from 2 to 10 do for m from 1 to d-1 do n := d-m ; printf("%d,",A175243(n,m)) ; end do: end do:

r[n_, m_] := n*2^(m-1)*(ChebyshevT[n, 1+m/2]-1)^(m-1)/m; Table[r[n-m, m], {n, 2, 9}, {m, 1, n-1}] // Flatten (* Jean-François Alcover, Jan 10 2014 *)

R_n(m) = n*2^(m-1)* (T(n,1+m/2)-1)^(m-1)/m, where T(n,x) are Chebyshev polynomials, A008310.

Each column of the array is a linear divisibility sequence. Conjecturally, the k-th column satisfies a linear recurrence of order 4*k - 2. - Peter Bala, May 04 2014

A340561 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = sqrt( Product_{a=1..n-1} Product_{b=1..k-1} (4sin(aPi/n)^2 + 4cos(bPi/k)^2) ).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 12, 16, 4, 1, 1, 29, 75, 45, 5, 1, 1, 70, 361, 384, 121, 6, 1, 1, 169, 1728, 3509, 1805, 320, 7, 1, 1, 408, 8281, 31500, 30976, 8100, 841, 8, 1, 1, 985, 39675, 284089, 508805, 261725, 35287, 2205, 9, 1

Offset: 1

Seiichi Manyama, Jan 11 2021

			Square array begins:
  1, 1,   1,    1,      1,       1, ...
  1, 2,   5,   12,     29,      70, ...
  1, 3,  16,   75,    361,    1728, ...
  1, 4,  45,  384,   3509,   31500, ...
  1, 5, 121, 1805,  30976,  508805, ...
  1, 6, 320, 8100, 261725, 7741440, ...

Columns 1..4 give A000012, A000027, A004146, A006235.
Rows 1..3 give A000012, A000129, A005386.
Main diagonal gives A340563.
T(n, 2*n) gives A252767.
Cf. A173958, A340476, A340560.

default(realprecision, 120);
{T(n, k) = round(sqrt(prod(a=1, n-1, prod(b=1, k-1, 4*sin(a*Pi/n)^2+4*cos(b*Pi/k)^2))))}

A180510 G.f.: (t^5 + 2t^4 + t^3 + 2t^2 + t) / (t^6 + t^5 - 2t^4 - 5t^3 - 2*t^2 + t + 1).

Original entry on oeis.org

0, 1, 1, 2, 7, 5, 20, 27, 49, 106, 155, 331, 560, 1013, 1917, 3310, 6223, 11117, 20140, 36899, 66185, 121014, 218791, 396703, 721280, 1305025, 2371433, 4298618, 7796439, 14150029, 25652500, 46550531, 84427441, 153141122, 277824947, 503893035, 914114320, 1658100757, 3007674389, 5455918726, 9896444495, 17951959061, 32563657260

Offset: 0

N. J. A. Sloane, Jan 20 2011

An example of a sextic divisibility sequence whose characteristic polynomial has degree 6 and a 12-element dihedral Galois group. This example has a field and polynomial discriminant of 98000, which is one of the smallest possible.

			G.f. = x + x^2 + 2*x^3 + 7*x^4 + 5*x^5 + 20*x^6 + 27*x^7 + 49*x^8 + 106*x^9 + ... - _Michael Somos_, Dec 30 2022

Found by Noam D. Elkies and described in an email from Elkies to R. K. Guy, Jan 18 2011

Vincenzo Librandi, Table of n, a(n) for n = 0..300 (corrected by Ray Chandler, Jan 19 2019)
E. L. Roettger, H. C. Williams, and R. K. Guy, Some extensions of the Lucas functions, Number Theory and Related Fields: In Memory of Alf van der Poorten, Series: Springer Proceedings in Mathematics & Statistics, Vol. 43, J. Borwein, I. Shparlinski, W. Zudilin (Eds.) 2013.
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (-1,2,5,2,-1,-1).

Cf. A001351, A001945, A005120, A006235.

CoefficientList[ Series[(x^5 + 2x^4 + x^3 + 2x^2 + x)/(x^6 + x^5 - 2x^4 - 5x^3 - 2x^2 + x + 1), {x, 0, 42}], x] (* Robert G. Wilson v, Jun 26 2011 *)
a[1] = 0; a[2] = 1; a[3] = 1; a[4] = 2; a[5] = 7; a[6] = 5; a[n_Integer] := a[n] = -a[n - 6] - a[n - 5] + 2 a[n - 4] + 5 a[n - 3] + 2 a[n - 2] - a[n - 1] (* Or *)
LinearRecurrence[{-1, 2, 5, 2, -1, -1}, {0, 1, 1, 2, 7, 5}, 43] (* Roger L. Bagula, Mar 16 2012 *)
a[ n_] := a[n] = Sign[n]*With[{m = Abs[n]}, If[ m<4, {0, 1, 1, 2}[[m+1]], -a[m-1] +2*a[m-2] +5*a[m-3] +2*a[m-4] -a[m-5] -a[m-6]]]; (* Michael Somos, Dec 30 2022 *)

makelist(coeff(taylor(x*(x^4+2*x^3+x^2+2*x+1)/(x^6+x^5-2*x^4-5*x^3-2*x^2+x+1), x, 0, n), x, n), n, 1, 42);  /* Bruno Berselli, Jun 05 2011 */

Vec((x^5+2*x^4+x^3+2*x^2+x)/(x^6+x^5-2*x^4-5*x^3-2*x^2+x+1)+O(x^99)) \\ Charles R Greathouse IV, Jun 06 2011

{a(n) = sign(n)*polcoeff((x^5 + 2*x^4 + x^3 + 2*x^2 + x)/(x^6 + x^5 - 2*x^4 - 5*x^3 - 2*x^2 + x + 1) + x*O(x^abs(n)), abs(n))}; /* Michael Somos, Dec 30 2022 */

a(n) = -a(-n) for all n in Z. - Michael Somos, Dec 30 2022

cp's OEIS Frontend

A173958 Number A(n,k) of spanning trees in C_k X P_n; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A006237 Complexity of tensor sum of n graphs; or spanning trees on n-cube.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A072373 Complexity of doubled cycle (regarding case n = 2 as a graph).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

PARI

PARI

PARI

PARI

Formula

A175243 Array read by antidiagonals: total number of spanning trees R_n(m) of the complete prism K_m X C_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A340561 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = sqrt( Product_{a=1..n-1} Product_{b=1..k-1} (4*sin(a*Pi/n)^2 + 4*cos(b*Pi/k)^2) ).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

A180510 G.f.: (t^5 + 2*t^4 + t^3 + 2*t^2 + t) / (t^6 + t^5 - 2*t^4 - 5*t^3 - 2*t^2 + t + 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

PARI

Formula

A340561 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) = sqrt( Product_{a=1..n-1} Product_{b=1..k-1} (4sin(aPi/n)^2 + 4cos(bPi/k)^2) ).

A180510 G.f.: (t^5 + 2t^4 + t^3 + 2t^2 + t) / (t^6 + t^5 - 2t^4 - 5t^3 - 2*t^2 + t + 1).