A084575 Number of terms in polynomial expression for determinant of generic circulant matrix of order n.

1, 2, 4, 10, 26, 68, 246, 810, 2704, 7492, 32066, 86500, 400024, 1366500, 4614524, 18784170, 68635478

Offset

1,2

Comments

Define an n X n matrix A[i,j] by A[i,j]=x_(i+j), subscripts on x being interpreted mod n. This is a generic circulant matrix. If we expand det(A) we obtain a polynomial in the x_i. Define a(n) to be the number of terms in this polynomial after like terms have been combined. (Replacing det(A) with per(A), the permanent of A, we get sequence A003239).

Links

Table of n, a(n) for n=1..17.

Hugh Thomas, The number of terms in the permanent ..., arXiv:math/0301048 [math.CO], 2003.

Formula

a(n) <= A003239(n), with = if n is a prime power. For other values of n little is known.

Example

Example : for n=2 the matrix is
x2,x1
x1,x2
and the determinant is (x_2)^2 - (x_1)^2 so a(2) = 2 and likewise for the permanent.

Mathematica

Table[Clear[x]; r=Array[x, n]; m=Table[RotateRight[r, i], {i, 0, n-1}]; Length[Expand[Det[m]]], {n, 10}] (* T. D. Noe, Oct 22 2008 *)

Crossrefs

Cf. A003239.

Sequence in context: A055819 A052995 A113337 * A081881 A025565 A085455

Adjacent sequences: A084572 A084573 A084574 * A084576 A084577 A084578

Keyword

nonn,hard,more

Author

Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 13 2003

Extensions

a(13) term added by T. D. Noe, Oct 22 2008

a(14) and a(15) from Roman Pearce, Aug 30 2014

a(16) and a(17) from Robert Israel, Aug 30 2014

Status

approved