This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001499 Number of n X n matrices with exactly 2 1's in each row and column, other entries 0.
(Formerly M4286 N1792)

%I M4286 N1792

%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, p. 236, P(n,2).

%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 Gao, Shanzhen, and Matheis, Kenneth, 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 R. W. Robinson and 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 P. 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 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 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, 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 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 lim(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 (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).

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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified June 28 17:16 EDT 2017. Contains 288839 sequences.