A123544 -id:A123544 - cp's OEIS frontend

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

N. J. A. Sloane

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

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.]

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

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.

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

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

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

seq(n)={Vec(serlaplace(serlaplace(exp(-x/2 + O(x*x^n))/sqrt(1-x + O(x*x^n)))))}; \\ Andrew Howroyd, Sep 09 2018

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

A000681 Number of n X n matrices with nonnegative entries and every row and column sum 2.

Original entry on oeis.org

1, 1, 3, 21, 282, 6210, 202410, 9135630, 545007960, 41514583320, 3930730108200, 452785322266200, 62347376347779600, 10112899541133589200, 1908371363842760216400, 414517594539154672566000, 102681435747106627787376000, 28772944645196614863048048000

Offset: 0

N. J. A. Sloane, Simon Plouffe

Or, number of labeled 2-regular pseudodigraphs (multiple arcs and loops allowed) of order n.

Also, number of permutations of the multiset {1^2,2^2,...,n^2} with the descent set consisting of multiples of 2. - Max Alekseyev, Apr 28 2014

			G.f. = 1 + x + 3*x^2 + 21*x^3 + 282*x^4 + 6210*x^5 + 202410*x^6 + 9135630*x^7 + ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 125, #25, a_n.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, section 3.5.10.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.
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 (a).
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.
C. B. Tompkins, Methods of successive restrictions in computational problems involving discrete variables. 1963, Proc. Sympos. Appl. Math., Vol. XV pp. 95-106; Amer. Math. Soc., Providence, R.I.

Alois P. Heinz, Table of n, a(n) for n = 0..250 (first 49 terms from R. W. Robinson)
H. Anand, V. C. Dumir and H. Gupta, A combinatorial distribution problem, Duke Math. J., 33 (1996), 757-769.
Esther M. Banaian, Generalized Eulerian Numbers and Multiplex Juggling Sequences, (2016). All College Thesis Program. Paper 24.
E. Banaian, S. Butler, C. Cox, J. Davis, J. Landgraf and S. Ponce A generalization of Eulerian numbers via rook placements, arXiv:1508.03673 [math.CO], 2015.
S. Cockburn and J. Lesperance, Deranged socks, Mathematics Magazine, 86 (2013), 97-109.
Ira Gessel, Enumerative applications of symmetric functions, Séminaire Lotharingien de Combinatoire, B17a (1987), 17 pp.
William George Griffiths, On Integer Solutions to Linear Equations, Annals of Combinatorics 12:1 (2008), pp. 53-70.
Rui-Li Liu, Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
Richard J. Mathar, 2-regular Digraphs of the Lovelock Lagrangian, arXiv:1903.12477 [math.GM], 2019.
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]
Index entries for sequences related to magic squares

Column k=2 of A257493.
Row sums of A269742 and A307804.
Row and column sums equal s: A000142 (s=1), A001500 (s=3), A172806 (s=4), A172862 (s=5), A172894 (s=6), A172919 (s=7), A172944 (s=8), A172958 (s=9).
Cf. A001499, A005650, A123544.

A000681 := proc(n)
    coeftayl( exp(x/2)/sqrt(1-x),x=0,n) ;
    %*(n!)^2 ;
end proc:
seq(A000681(n),n=0..10) ; # R. J. Mathar, May 01 2019

a[n_] := Sum[ ((2*i)!*n!^2) / (2^i*(i!^2*(n - i)!)), {i, 0, n}]/2^n; Table[ a[n], {n, 0, 17}] (* Jean-François Alcover, Dec 08 2011 *)
a[n_] := n!*HypergeometricPFQ[{1/2, -n}, {}, -2]/2^n; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Aug 08 2012 *)

Vec( serlaplace(serlaplace( exp(x/2)/sqrt(1-x) )) ) /* Max Alekseyev, Apr 28 2014 */

from sage.combinat.integer_matrices import IntegerMatrices
def a(n): return IntegerMatrices([2]*n, [2]*n).cardinality() # Ralf Stephan, Mar 02 2014

Sum_{n >= 0} a(n) x^n / n!^2 = exp(x/2) / sqrt(1-x).
D-finite with recurrence a(n) = n^2*a(n-1) - (1/2)*n*(n-1)^2*a(n-2).
a(n) is asymptotic to c/sqrt(n)*(n!)^2 where c=0.93019... - Benoit Cloitre, Jun 25 2004
a(n) = sum(i=0..n, 2^(i-2*n) * C(n, i)^2 * (2*n-2*i)! * i! ).
a(n) = 2^(-n) * sum(i=0..n, ((n!)^2*(2*i)!) / ((i!)^2*((n-i)!*2^i)) ). - Shanzhen Gao, Nov 05 2007
In Cloitre's formula is c = exp(1/2)/sqrt(Pi) = 0.9301913671026328586. - Vaclav Kotesovec, Aug 12 2013
With c as used above by Cloitre and Kotesovec, a(n) is asymptotic to c/sqrt(n)*(n!)^2 * (1 + 2/(16*n) + 50/(16*n)^2 + 1100/(16*n)^3 + 32438/(16*n)^4 + 1185660/(16*n)^5 + 50498228/(16*n)^6 + 2438464600/(16*n)^7 + 131323987366/(16*n)^8 + 7782036656108/(16*n)^9 + 501905392385436/(16*n)^10 + ...). - Jon E. Schoenfield, Mar 03 2014
E.g.f.: 2/((2-x)*W(0)), where W(k) = 1 - (2*k+1)*x/(2-x-2*(k+1)*x/W(k+1)); (continued fraction). - Sergei N. Gladkovskii, Nov 25 2014

More terms from David W. Wilson

A005642 Number of 2-diregular connected digraphs with n nodes.

Original entry on oeis.org

1, 3, 7, 24, 117, 663, 4824, 40367, 381554, 4001849, 46043780, 576018785, 7783281188, 112953364381, 1752128923245, 28930230194371, 506596534953769

Offset: 2

N. J. A. Sloane

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. V. S. Ramanath & T. R. Walsh, Enumeration and generation of a class of regular digraphs, J. Graph Theory 11 (1987), no. 4, 471-479. (Annotated scanned copy)
R. J. Mathar, Illustrations

Cf. A005641 (not necess. connected), A306892 (multiarcs allowed). Labeled version is A123544.

A123543 Number of connected labeled 2-regular pseudodigraphs (multiple arcs and loops allowed) of order n.

Original entry on oeis.org

0, 1, 2, 14, 201, 4704, 160890, 7538040, 462869190, 36055948320, 3474195588360, 405786523413600, 56502317464777800, 9248640671612865600, 1758505909558569771600, 384399253128691423022400, 95737858067835530264718000, 26952922550751326069548608000

Offset: 0

N. J. A. Sloane, Nov 13 2006

nonn

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.

Alois P. Heinz, Table of n, a(n) for n = 0..253 (first 49 terms from R. W. Robinson)

Connected version of A000681.
First column of A307804.
Cf. A123544.

b:= proc(n) option remember; `if`(n<2, 1,
      n^2*b(n-1)-n*(n-1)^2*b(n-2)/2)
    end:
a:= proc(n) option remember; `if`(n=0, 0, b(n)-
      add(j*binomial(n, j)*b(n-j)*a(j), j=1..n-1)/n)
    end:
seq(a(n), n=0..17);  # Alois P. Heinz, Mar 22 2025

m = 16;
a681[n_] := n!*HypergeometricPFQ[{1/2, -n}, {}, -2]/2^n;
egf = Log[1 + Sum[a681[k] x^k/k!, {k, 1, m}]];
CoefficientList[egf + O[x]^m, x] Range[0, m-1]! (* Jean-François Alcover, Aug 26 2019 *)

seq(n)={Vec(serlaplace(log(serlaplace(exp(x/2 + O(x*x^n))/sqrt(1-x + O(x*x^n))))), -(n+1))}; \\ Andrew Howroyd, Sep 09 2018

E.g.f.: log(1 + Sum_{k>0} A000681(k)*x^k/k!). - Andrew Howroyd, Sep 09 2018

a(n) ~ 2 * sqrt(Pi) * n^(2*n + 1/2) / exp(2*n - 1/2). - Vaclav Kotesovec, Jul 11 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

A000681 Number of n X n matrices with nonnegative entries and every row and column sum 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A005642 Number of 2-diregular connected digraphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

A123543 Number of connected labeled 2-regular pseudodigraphs (multiple arcs and loops allowed) of order n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula