A001499 Number of n X n matrices with exactly 2 1's in each row and column, other entries 0.

1, 0, 1, 6, 90, 2040, 67950, 3110940, 187530840, 14398171200, 1371785398200, 158815387962000, 21959547410077200, 3574340599104475200, 676508133623135814000, 147320988741542099484000, 36574751938491748341360000, 10268902998771351157327104000

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

Or, number of labeled 2-regular relations of order n.

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

References

• R. Bricard, L'Intermédiaire des Mathématiciens, 8 (1901), 312-313.
• L. Comtet, Advanced Combinatorics, Reidel, 1974, Sect. 6.3 Multipermutations, pp. 235-236, P(n,2), bipermutations.
• 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.
• 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.
• J. T. Lewis, Maximal L-free subsets of a squarefree array, Congressus Numerantium, 141 (1999), 151-155.
• R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Cor. 5.5.11 (b).
• 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.
• 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.]

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..200 (terms n = 0..48 from R. W. Robinson)
• H. Anand, V. C. Dumir and H. Gupta, A combinatorial distribution problem, Duke Math. J., 33 (1996), 757-769.
• Paul Barry, On the Connection Coefficients of the Chebyshev-Boubaker polynomials, The Scientific World Journal, Volume 2013 (2013), Article ID 657806.
• L. Carlitz, Enumeration of symmetric arrays, Duke Math. J., Vol. 33 (1966), 771-782.
• Sally Cockburn and Joshua Lesperance, Deranged Socks, Mathematics Magazine, Vol. 86, no. 2, April 2013, pp. 97-109.
• L. Erlebach and O. Ruehr, Problem 79-5, SIAM Review, Vol. 21, No. 1 (Jan., 1979), p. 140. Solution by D. E. Knuth, SIAM Review, Vol. 22, No. 1 (Jan., 1980), pp. 101-102.
• M. E. Kuczma, 0-1-Matrices with Line-Sums Equal to 2, Am. Math. Month. 99 (1992) 959-961, E3419.
• Rui-Li Liu and Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
• 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. [Annotated scanned copy]
• Zhonghua Tan, Shanzhen Gao, and H. Niederhausen, Enumeration of (0,1) matrices with constant row and column sums, Appl. Math. Chin. Univ. 21 (4) (2006) 479-486.
• Bo-Ying Wang and Fuzhen Zhang, 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
• Index entries for sequences related to binary matrices

Crossrefs

Cf. A000681, A053871, A123544 (connected relations), A000986 (symmetric matrices), A007107 (traceless matrices).

Cf. A000290, A002411, A005408.

Cf. A001501. Column 2 of A008300. Row sums of A284989.

Programs

Haskell

a001499 n = a001499_list !! n
a001499_list = 1 : 0 : 1 : zipWith (*) (drop 2 a002411_list)
   (zipWith (+) (zipWith (*) [3, 5 ..] $ tail a001499_list)
                (zipWith (*) (tail a000290_list) a001499_list))
-- Reinhard Zumkeller, Jun 02 2013

Mathematica

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 *)

PARI

a(n)=if(n<2,n==0,(n^2-n)*(a(n-1)+(n-1)/2*a(n-2)))

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

Formula

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.

D-finite with recurrence 2*a(n) -2*n*(n-1)*a(n-1) -n*(n-1)^2*a(n-2)=0.

a(n) ~ 2 sqrt(Pi) n^(2n + 1/2) e^(-2n - 1/2) [Knuth]

a(n) = (1/2)*n*(n-1)^2 * ( (2*n-3)*a(n-2) + (n-2)^2*a(n-3) ) (from Anand et al.)

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)

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.

Limit_(n->infinity) sqrt(n)*a(n)/(n!)^2 = A096411 [Kuczma]. - R. J. Mathar, Sep 21 2007

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