login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A087981 E.g.f.: exp(-2*x) / (1-x)^2. 11
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; text; 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 Kräuter 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

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)^{⊗ 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. - Vladimir Shevelev, 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. - Michael Somos, Jan 19 2011

Binomial transform is A000255. Hankel transform is A059332. - Paul Barry, Apr 11 2011

Exponential self-convolution of subfactorials (A000166). - Vladimir Reshetnikov, Oct 07 2016

REFERENCES

Gelfand, Kapranov and Zelevinsky, Discriminants, Resultants and Multidimensional Determinants, Birkhauser, 1994, Corollary (14.)2.10.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..100

Arnold R. Kräuter, Permanenten - Ein kurzer Überblick, Séminaire Lotharingien de Combinatoire, B09b (1983), 34 pp.

Arnold R. Kräuter and Norbert Seifter, Some properties of the permanent of (1,-1)-matrices, Linear and Multilinear Algebra 15 (1984), 207-223.

Norbert 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.

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). - Vladimir Shevelev, 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, Apr 11 2011

E.g.f.: 1/U(0) where U(k)=  1 - 2*x/( 1 + x/(2 - x - 4/( 2 + x*(k+1)/U(k+1)))) ; (continued fraction, 3rd kind, 4-step). - Sergei N. Gladkovskii, Oct 28 2012

G.f.: 1/Q(0), where Q(k) = 1 + 2*x - x*(k+2)/(1 - x*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, Apr 22 2013

G.f.: 1/Q(0) where Q(k) = 1 - 2*k*x - x^2*(k + 1)*(k+2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 10 2013

G.f.: S(x)/x - 1/x = G(0)/x - 1/x, where S(x) = sum(k >= 0, k!*(x/(1+2*x))^k  ), G(k) = 1 + (2*k + 1)*x/( 1+2*x - 2*x*(1+2*x)*(k+1)/(2*x*(k+1) + (1+2*x)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 26 2013

a(n) = (-2)^n*hypergeom([2, -n], [], 1/2) = 4*(-2)^n*(1 - 2*hypergeom([1, -n-3], [], 1/2))/(n^2+3*n+2) = (4*(-2)^n + Gamma(n+4, -2)*exp(-2))/(n^2+3*n+2). - Vladimir Reshetnikov, Oct 07 2016

a(n) ~ sqrt(2*Pi) * n^(n+3/2) / exp(n+2). - Vaclav Kotesovec, Oct 08 2016

EXAMPLE

G.f. = 1 + 2*x^2 + 4*x^3 + 24*x^4 + 128*x^5 + 880*x^6 + 6816*x^7 + ...

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. - Vladimir Shevelev, 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

MAPLE

a:= n-> n!*coeff(series(exp(-2*x)/(1-x)^2, x=0, n+1), x, n): seq(a(n), n=0..24);  # Paolo P. Lava, Nov 19 2018

MATHEMATICA

Range[0, 20]! CoefficientList[Series[Exp[-2 x]/(1 - x)^2, {x, 0, 20}], x]

Table[(-2)^n HypergeometricPFQ[{2, -n}, {}, 1/2], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 07 2016 *)

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. - Michael Somos, Jan 19 2011

Sequence in context: A170931 A317999 A164313 * A002875 A110491 A019010

Adjacent sequences:  A087978 A087979 A087980 * A087982 A087983 A087984

KEYWORD

nonn,easy,nice

AUTHOR

Gordon F. Royle, Oct 28 2003

EXTENSIONS

More terms from Jaap Spies, Oct 28 2003

Further terms from Gordon F. 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, Michael Somos, Jan 19 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 20:24 EST 2019. Contains 319310 sequences. (Running on oeis4.)