login
E.g.f.: exp(-2*x) / (1-x)^2.
18

%I #103 Feb 16 2024 10:14:58

%S 1,0,2,4,24,128,880,6816,60032,589312,6384384,75630080,972387328,

%T 13483769856,200571078656,3185540657152,53800242216960,

%U 962741176500224,18195808235880448,362183230599856128,7572922094360723456,165945771111208714240,3802923921298533384192,90965940197460917878784,2267151124921333646884864

%N E.g.f.: exp(-2*x) / (1-x)^2.

%C Permanent of an (n+1) X (n+1) (+1, -1)-matrix with exactly n -1's on the diagonal and 1's everywhere else.

%C 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_

%C The Kräuter conjecture on permanents is true (see Budrevich and Guterman). - _Sergei Shteiner_, Jan 17 2020

%C The maximal possible value for the permanent of a singular n X n (+1, -1)-matrix is obviously n!.

%C 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

%C (-1)^n * a(n) = Polynomials in A010027 evaluated at -1. - _Ralf Stephan_, Dec 15 2004

%C 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

%C 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

%C Binomial transform is A000255. Hankel transform is A059332. - _Paul Barry_, Apr 11 2011

%C Exponential self-convolution of subfactorials (A000166). - _Vladimir Reshetnikov_, Oct 07 2016

%D I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, Resultants and Multidimensional Determinants, Birkhauser, 1994; see Corollary 2.10 in Chapter 14 (p. 457).

%H T. D. Noe, <a href="/A087981/b087981.txt">Table of n, a(n) for n = 0..100</a>

%H Mikhail V. Budrevich and Alexander E. Guterman, <a href="https://arxiv.org/abs/1810.04439">Kräuter conjecture on permanents is true</a>, arXiv:1810.04439 [math.CO], 2018.

%H Steven Finch, <a href="https://arxiv.org/abs/2111.14487">Rounds, Color, Parity, Squares</a>, arXiv:2111.14487 [math.CO], 2021.

%H I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, <a href="https://doi.org/10.1016/0001-8708(92)90056-Q">Hyperdeterminants</a>, Advances in Mathematics 96(2) (1992), 226-263; see Corollary 3.10 (p. 246).

%H Arnold R. Kräuter, <a href="http://www.mat.univie.ac.at/~slc/opapers/s09kraeu.html">Permanenten - Ein kurzer Überblick</a>, Séminaire Lotharingien de Combinatoire, B09b (1983), 34 pp.

%H Arnold R. Kräuter and Norbert Seifter, <a href="http://dx.doi.org/10.1080/03081088408817591">Some properties of the permanent of (1,-1)-matrices</a>, Linear and Multilinear Algebra 15 (1984), 207-223.

%H Norbert Seifter, <a href="http://dx.doi.org/10.1007/BF02760525">Upper bounds for permanents of (1,-1)-matrices</a>, Israel J. Math. 48 (1984), 69-78.

%H Edward Tzu-Hsia Wang, <a href="http://dx.doi.org/10.1007/BF02760844">On permanents of (1,-1)-matrices</a>, Israel J. Math. 18 (1974), 353-361.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Hyperdeterminant">Hyperdeterminant</a>

%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>

%F Krauter and Seifter prove that the permanent of an n X n {-1, 1} matrix is divisible by 2^{n - [log_2(n)] - 1}.

%F 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).

%F 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]

%F 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

%F 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

%F 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

%F 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

%F 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

%F 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

%F a(n) ~ sqrt(2*Pi) * n^(n+3/2) / exp(n+2). - _Vaclav Kotesovec_, Oct 08 2016

%F a(n) = KummerU(-n, -n - 1, -2). - _Peter Luschny_, May 10 2022

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

%e 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

%e 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

%p seq(simplify(KummerU(-n, -n-1, -2)), n = 0..24); # _Peter Luschny_, May 10 2022

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

%t Table[(-2)^n HypergeometricPFQ[{2, -n}, {}, 1/2], {n, 0, 20}] (* _Vladimir Reshetnikov_, Oct 07 2016 *)

%o (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 */

%Y Cf. A087982, A087983, A176097.

%Y Cf. A000007, A000023, A000166, A024000, A137775. - _Michael Somos_, Jan 19 2011

%K nonn,easy,nice

%O 0,3

%A _Gordon F. Royle_, Oct 28 2003

%E More terms from _Jaap Spies_, Oct 28 2003

%E Further terms from _Gordon F. Royle_, Oct 29 2003

%E Definition via e.g.f. from Eric Rains, Mar 15 2004

%E Changed the offset and terms to correspond to e.g.f, _Michael Somos_, Jan 19 2011