This site is supported by donations to The OEIS Foundation.



Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

(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 H. Anand, V. C. Dumir and H. Gupta, A combinatorial distribution problem, Duke Math. J., 33 (1966), 757-769.

%D R. Bricard, L'Interm\'{e}diaire des Math\'{e}maticiens, 8 (1901), 312-313.

%D L. Carlitz, Enumeration of symmetric arrays, {\em Duke Math. J.}, {\bf 33} (1966), 771-782.

%D S. Cockburn and J. Lesperance, Deranged socks, Mathematics Magazine, 86 (2013), 97-109.

%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 Mathematices, 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, {\em Congressus Numerantium}, {\bf 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, {\em A Course in Combinatorics}, (Cambridge University Press, Cambridge, 1992), pp. 152-153. [The second edition is said to be a better reference.]

%D Wang, Bo-Ying; Zhang, Fuzhen. On the precise number of (0,1)-matrices in A(R,S). Discrete Math. 187 (1998), no. 1-3, 211--220. MR1630720 (99f:05010). - From _N. J. A. Sloane_, Jun 07 2012

%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 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 M. E. Kuczma, <a href="http://links.jstor.org/sici?sici=0002-9890%28199212%2999%3A10%3C959%3AE%3E2.0.CO%3B2-S">0-1-Matrices with Line-Sums Equal to 2</a>, Am. Math. Month. 99 (1992) 959-961, E3419.

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

%Y Cf. A000290, A002411, A005408.

%Y Cf. A001501.

%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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 27 20:25 EST 2014. Contains 250271 sequences.