|
%I M4286 N1792 #106 Nov 03 2023 10:27:25
%S 1,0,1,6,90,2040,67950,3110940,187530840,14398171200,1371785398200,
%T 158815387962000,21959547410077200,3574340599104475200,
%U 676508133623135814000,147320988741542099484000,36574751938491748341360000,10268902998771351157327104000
%N Number of n X n matrices with exactly 2 1's in each row and column, other entries 0.
%C Or, number of labeled 2-regular relations of order n.
%C Also number of ways to arrange 2n rooks on an n X n chessboard, with no more than 2 rooks in each row and column (no 3 in a line). - _Vaclav Kotesovec_, Aug 03 2013
%D R. Bricard, L'Intermédiaire des Mathématiciens, 8 (1901), 312-313.
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, Sect. 6.3 Multipermutations, pp. 235-236, P(n,2), bipermutations.
%D L. Erlebach and O. Ruehr, Problem 79-5, SIAM Review. Solution by D. E. Knuth. Reprinted in Problems in Applied Mathematics, ed. M. Klamkin, SIAM, 1990, p. 350.
%D Shanzhen Gao and Kenneth Matheis, Closed formulas and integer sequences arising from the enumeration of (0,1)-matrices with row sum two and some constant column sums. In Proceedings of the Forty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 202 (2010), 45-53.
%D J. T. Lewis, Maximal L-free subsets of a squarefree array, Congressus Numerantium, 141 (1999), 151-155.
%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Cor. 5.5.11 (b).
%D M. L. Stein and P. R. Stein, Enumeration of Stochastic Matrices with Integer Elements. Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970.
%D J. H. van Lint and R. M. Wilson, A Course in Combinatorics (Cambridge University Press, Cambridge, 1992), pp. 152-153. [The second edition is said to be a better reference.]
%H Alois P. Heinz, <a href="/A001499/b001499.txt">Table of n, a(n) for n = 0..200</a> (terms n = 0..48 from R. W. Robinson)
%H H. Anand, V. C. Dumir and H. Gupta, <a href="http://dx.doi.org/10.1215/S0012-7094-66-03391-6">A combinatorial distribution problem</a>, Duke Math. J., 33 (1996), 757-769.
%H Paul Barry, <a href="http://dx.doi.org/10.1155/2013/657806">On the Connection Coefficients of the Chebyshev-Boubaker polynomials</a>, The Scientific World Journal, Volume 2013 (2013), Article ID 657806.
%H L. Carlitz, <a href="http://dx.doi.org/10.1215/S0012-7094-66-03392-8">Enumeration of symmetric arrays</a>, Duke Math. J., Vol. 33 (1966), 771-782.
%H Sally Cockburn and Joshua Lesperance, <a href="http://www.maa.org/sites/default/files/pdf/upload_library/2/Cockburn-MathMag-2014.pdf">Deranged Socks</a>, Mathematics Magazine, Vol. 86, no. 2, April 2013, pp. 97-109.
%H L. Erlebach and O. Ruehr, <a href="https://www.jstor.org/stable/2029944">Problem 79-5</a>, SIAM Review, Vol. 21, No. 1 (Jan., 1979), p. 140. <a href="https://www.jstor.org/stable/2029885">Solution by D. E. Knuth</a>, SIAM Review, Vol. 22, No. 1 (Jan., 1980), pp. 101-102.
%H M. E. Kuczma, <a href="http://www.jstor.org/stable/2324501">0-1-Matrices with Line-Sums Equal to 2</a>, Am. Math. Month. 99 (1992) 959-961, E3419.
%H Rui-Li Liu and Feng-Zhen Zhao, <a href="https://www.emis.de/journals/JIS/VOL21/Liu/liu19.html">New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
%H M. L. Stein and P. R. Stein, <a href="/A001496/a001496.pdf">Enumeration of Stochastic Matrices with Integer Elements</a>, Report LA-4434, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Jun 1970. [Annotated scanned copy]
%H Bo-Ying Wang and Fuzhen Zhang, <a href="http://dx.doi.org/10.1016/S0012-365X(97)00197-0">On the precise number of (0,1)-matrices in A(R,S)</a>, Discrete Math. 187 (1998), no. 1-3, 211--220. MR1630720 (99f:05010). - From _N. J. A. Sloane_, Jun 07 2012
%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>
%F a(n) = (n! (n-1) Gamma(n-1/2) / Gamma(1/2) ) * 1F1[2-n; 3/2-n; -1/2] [Erlebach and Ruehr]. This representation is exact, asymptotic and convergent.
%F D-finite with recurrence 2*a(n) -2*n*(n-1)*a(n-1) -n*(n-1)^2*a(n-2)=0.
%F a(n) ~ 2 sqrt(Pi) n^(2n + 1/2) e^(-2n - 1/2) [Knuth]
%F a(n) = (1/2)*n*(n-1)^2 * ( (2*n-3)*a(n-2) + (n-2)^2*a(n-3) ) (from Anand et al.)
%F Sum_{n >= 0} a(n)*x^n/(n!)^2 = exp(-x/2)/sqrt(1-x); a(n) = n(n-1)/2 [ 2 a(n-1) + (n-1) a(n-2) ] (Bricard)
%F b_n = a_n/n! satisfies b_n = (n-1)(b_{n-1} + b_{n-2}/2); e.g.f. for {b_n} and for derangements (A000166) are related by D(x) = B(x)^2.
%F Limit_(n->infinity) sqrt(n)*a(n)/(n!)^2 = A096411 [Kuczma]. - _R. J. Mathar_, Sep 21 2007
%F a(n) = 4^(-n) * n!^2 * Sum_{i=0..n} (-2)^i * (2*n - 2*i)! / (i!*(n-i)!^2). - _Shanzhen Gao_, Feb 15 2010
%t a[n_] := (n-1)*n!*Gamma[n-1/2]*Hypergeometric1F1[2-n, 3/2-n, -1/2]/Sqrt[Pi]; Table[a[n], {n, 0, 17}] (* _Jean-François Alcover_, Oct 06 2011, after first formula *)
%o (PARI) a(n)=if(n<2,n==0,(n^2-n)*(a(n-1)+(n-1)/2*a(n-2)))
%o (PARI) seq(n)={Vec(serlaplace(serlaplace(exp(-x/2 + O(x*x^n))/sqrt(1-x + O(x*x^n)))))}; \\ _Andrew Howroyd_, Sep 09 2018
%o (Haskell)
%o a001499 n = a001499_list !! n
%o a001499_list = 1 : 0 : 1 : zipWith (*) (drop 2 a002411_list)
%o (zipWith (+) (zipWith (*) [3, 5 ..] $ tail a001499_list)
%o (zipWith (*) (tail a000290_list) a001499_list))
%o -- _Reinhard Zumkeller_, Jun 02 2013
%Y Cf. A000681, A053871, A123544 (connected relations), A000986 (symmetric matrices), A007107 (traceless matrices).
%Y Cf. A000290, A002411, A005408.
%Y Cf. A001501. Column 2 of A008300. Row sums of A284989.
%K nonn,nice,easy
%O 0,4
%A _N. J. A. Sloane_
|
