|
| |
|
|
A087981
|
|
E.g.f.: e^(-2x)/(1-x)^2.
|
|
7
| |
|
|
1, 0, 2, 4, 24, 128, 880, 6816, 60032, 589312, 6384384, 75630080, 972387328, 13483769856, 200571078656, 3185540657152, 53800242216960, 962741176500224, 18195808235880448, 362183230599856128, 7572922094360723456, 165945771111208714240, 3802923921298533384192, 90965940197460917878784, 2267151124921333646884864
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Permanent of an (n+1) X (n+1) (+1,-1)-matrix with exactly n -1's on the diagonal and 1's everywhere else.
It is conjectured by Kraeuter and Seifter that for n >= 5 a(n-1) is the maximal possible value for the permanent of a nonsingular n X n (+1,-1)-matrix. I do not know for which values of n this has been confirmed - compare A087982. - N. J. A. Sloane (njas(AT)research.att.com).
The maximal possible value for the permanent of a singular n X n (+1,-1)-matrix is obviously n!.
Degree of the "hyperdeterminant" of a multilinear polynomial on (\P^1(\C))^n, or equivalently of an element of (\C^2)^{\otimes n}: see Gelfand, Kapranov and Zelevinsky. - Eric Rains, Mar 15 2004.
(-1)^n * a(n) = Polynomials in A010027 evaluated at -1. - Ralf Stephan, Dec 15 2004
a(n) is the number of n X n (-1,0,1)-matrices containing in every row and every column exactly one -1 and one 1 such that the main diagonal does not contain 0's. [From Vladimir Shevelev (shevelev(AT)bgu.ac.il), Apr 01 2010]
a(n) is the number of colored permutations with no fixed points of n elements where each cycle is one of two colors. [From Michael Somos, Jan 19 2011]
Binomial transform is A000255. Hankel transform is A059332. [Paul Barry, April 11 2011]
|
|
|
REFERENCES
| Gelfand, Kapranov and Zelevinsky, Discriminants, Resultants and Multidimensional Determinants, Birkhauser, 1994, Corollary (14.)2.10.
A. R. Kraeuter and N. Seifter, Some properties of the permanent of (1,-1)-matrices, Linear and Multilinear Algebra 15 (1984), 207-223.
N. Seifter, Upper bounds for permanents of (1,-1)-matrices, Israel J. Math. 48 (1984), 69-78.
Edward Tzu-Hsia Wang, On permanents of (1,-1)-matrices, Israel J. Math. 18 (1974), 353-361.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=2..101
A. R. Kr\"auter, Permanenten - Ein kurzer \"Uberblick
Wikipedia, Hyperdeterminant
Index entries for sequences related to binary matrices
|
|
|
FORMULA
| Krauter and Seifter prove that the permanent of an n X n {-1, 1} matrix is divisible by 2^{n - [log_2(n)] - 1}.
Let c(n) be the permanent of the {-1, +1}-matrix of order n X n with n diagonal -1's only. Let a(n) be the permanent of the {-1, +1}-matrix of order (n+1) X (n+1) with n diagonal -1's only. Then by expanding along the first row (like determinant, but with no sign) we get c(n+1) = -c(n) + n a(n-1), a(n) = c(n) + n a(n-1), with c(2) = 2, a(2) = 2. {c(n)} has e.g.f. exp(-2x)/(1-x), see A000023. Also a(n) = c(n+1) + 2*c(n).
The following 4 formulas hold: a(n)=Sum{k=0,...,n}C(n,k)*D_k*D_{n-k}, where D_n=A000166(n); a(n)=n!*Sum{j=0,...,n}(n+1-j)*(-2)^j/j!; a(0)=1,a(1)=0 and, for n>0, a(n+1)=n*(a(n)+2*a(n-1)); a(0)=1 and, for n>0, a(n)=(n*(n+3)/(n+2))a(n-1)-(-2)^(n+1)/(n+2). [From Vladimir Shevelev (shevelev(AT)bgu.ac.il), Apr 01 2010] [edited by Michael Somos, Jan 19 2011]
G.f.: 1/(1-2x^2/(1-2x-6x^2/(1-4x-12x^2/(1-6x-20x^2/(1-.../(1-2n*x-(n+1)(n+2)x^2/(1-... (continued fraction). [Paul Barry, April 11 2011]
|
|
|
EXAMPLE
| Since a(1)=0, then, for n=2, we have a(2)=-(-2)^3/4=2; further, for n=3, we find a(3)=(3*6/5)*2-(-2)^4/5=36/5-16/5=4. [From Vladimir Shevelev (shevelev(AT)bgu.ac.il), Apr 01 2010]
a(4) = 24 because there are 6 derangements with one 4-cycle with 2^1 ways to color each derangement and 3 derangements with two 2-cycles with 2^2 ways to color each derangement. - Michael Somos, Jan 19 2011
G.f. = 1 + 2*x^2 + 4*x^3 + 24*x^4 + 128*x^5 + 880*x^6 + 6816*x^7 + ...
|
|
|
MATHEMATICA
| Range[0, 20]! CoefficientList[ Series[ Exp[-2 x]/(1 - x)^2, {x, 0, 20}], x]
|
|
|
PROG
| (PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp( -2 * x + x * O(x^n) ) / ( 1 - x )^2, n ) )} /* Michael Somos, Jan 19 2011 */
|
|
|
CROSSREFS
| Cf. A087982, A087983.
Cf. A000007, A000023, A000166, A024000, A137775. [From Michael Somos, Jan 19 2011]
Sequence in context: A192382 A170931 A164313 * A002875 A110491 A019010
Adjacent sequences: A087978 A087979 A087980 * A087982 A087983 A087984
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| Gordon Royle (gordon(AT)maths.uwa.edu.au), Oct 28 2003
|
|
|
EXTENSIONS
| More terms from Jaap Spies (j.spies(AT)hccnet.nl), Oct 28 2003
Further terms from Gordon Royle, Oct 29 2003
Definition via e.g.f. from Eric Rains, Mar 15 2004
Changed the offset and terms to correspond to e.g.f from Michael Somos, Jan 19 2011
|
| |
|
|
