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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(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)
23

%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 September 30 19:57 EDT 2014. Contains 247475 sequences.