A007107 -id:A007107 - 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

A219889 Number of directed 2-regular graphs on n nodes.

Original entry on oeis.org

1, 2, 5, 23, 92, 624, 5021, 47034, 494320, 5719769, 71971687

Offset: 3

N. J. A. Sloane, Nov 30 2012

Gunnar Brinkmann, Generating regular directed graphs, Discrete Math., 313 (2012), 1-7.
R. J. Mathar, OEIS A219889
Richard J. Mathar, 2-regular Digraphs of the Lovelock Lagrangian, arXiv:1903.12477 [math.GM], 2019.

Column k=2 of A350910.

Cf. A096368, A219890, A219891, A219892, A219893, A307155 (connected, inverse Euler Trans.), A007107 (labeled), A306827 (multiedges, connected), A002865 (directed 1-regular unlabeled no loops), A005641 (loops allowed)

A174564 Let J_n be n X n matrix which contains 1's only, I=I_n be the n X n identity matrix and P=P_n be the incidence matrix of the cycle (2,3,...,n,1). Then a(n) is the number of (0,1) n X n matrices A<=J_n-I-P with exactly two 1's in every row and column.

Original entry on oeis.org

0, 1, 13, 522, 27828, 1867363

Offset: 3

Vladimir Shevelev, Mar 22 2010

V. S. Shevelev, Development of the rook technique for calculating the cyclic indicators of (0,1)-matrices, Izvestia Vuzov of the North-Caucasus region, Nature sciences 4 (1996), 21-28 (in Russian).
S. E. Grigorchuk, V. S. Shevelev, An algorithm of computing the cyclic indicator of couples discordant permutations with restricted position, Izvestia Vuzov of the North-Caucasus region, Nature sciences 3 (1997), 5-13 (in Russian).

Cf. A001499 A007107 A082491 A000186

A284989 Triangle T(n,k) read by rows: the number of n X n {0,1} matrices with trace k where each row sum and each column sum is 2.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 0, 3, 2, 9, 24, 24, 24, 9, 216, 540, 610, 420, 210, 44, 7570, 18000, 20175, 13720, 6300, 1920, 265, 357435, 829920, 909741, 617610, 284235, 91140, 19005, 1854, 22040361, 50223600, 54295528, 36663312, 17072790, 5679184, 1337280, 203952, 14833

Offset: 0

R. J. Mathar, Apr 07 2017

			0:         1
1:         0        0
2:         0        0        1
3:         1        0        3        2
4:         9       24       24       24        9
5:       216      540      610      420      210      44
6:      7570    18000    20175    13720     6300    1920     265
7:    357435   829920   909741   617610   284235   91140   19005   1854
8:  22040361 50223600 54295528 36663312 17072790 5679184 1337280 203952 14833

Alois P. Heinz, Rows n = 0..14, flattened
Index entries for sequences related to binary matrices

Cf. A001499 (row sums), A000166 (diagonal), A007107 (column 0).

Cf. A008290, A098825, A284990, A284991.

P(n, t='t) = {
  my(z=vector(n, k, eval(Str("z", k))),
     s1=sum(k=1, #z, z[k]), s2=sum(k=1, #z, z[k]^2), s12=(s1^2 - s2)/2,
     f=vector(n, k, t*(s12 - z[k]*(s1 - z[k])) + z[k]*(s1 - z[k])), g=1);
  for (i=1, n, g *= f[i]; for(j=1, n, g=substpol(g, z[j]^3, 0)));
  for (k=1, n, g=polcoef(g, 2, z[k]));
  g;
};
seq(N) = concat([[1], [0, 0], [0, 0, 1]], apply(n->Vec(P(n)), [3..N]));
concat(seq(8)) \\ Gheorghe Coserea, Dec 21 2018

Let z1..zn be n variables and s1 = Sum_{k=1..n} zk, s2 = Sum_{k=1..n} zk^2, s12 = (s1^2 - s2)/2, fk = t*(s12 - zk*(s1 - zk)) + zk*(s1 - zk) for k=1..n, P_n(t) = [(z1..zn)^2] Product_{k=1..n} fk. Then P_n(t) = Sum_{k=0..n} T(n,k)*t^(n-k), n >= 3. - Gheorghe Coserea, Dec 21 2018

A284990 Triangle T(n,t) read by rows: the number of n X n {0,1} matrices with trace t where each row sum and each column sum is 3.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 6, 8, 9, 44, 210, 420, 610, 540, 216, 7570, 33120, 66870, 82080, 66870, 33120, 7570, 1975560, 8171730, 15729000, 18433415, 14372820, 7499940, 2398900, 357435, 749649145, 2971510080, 5508175260, 6267658544, 4815171270, 2570369760, 932429820, 209185200, 22040361

Offset: 0

R. J. Mathar, Apr 07 2017

			0:        1
1:        0       0
2:        0       0        0
3:        0       0        0        1
4:        1       0        6        8        9
5:       44     210      420      610      540     216
6:     7570   33120    66870    82080    66870   33120    7570
7:  1975560 8171730 15729000 18433415 14372820 7499940 2398900 357435

Alois P. Heinz, Rows n = 0..11, flattened
Index entries for sequences related to binary matrices

Cf. A007107 (diagonal?), A001501 (row sums), A007105 (column 0?), A110040 (symmetric matrices).

More terms from Alois P. Heinz, Apr 09 2017

A174580 Let J_n be an n X n matrix which contains 1's only, I = I_n be the n X n identity matrix, and P = P_n be the incidence matrix of the cycle (1,2,3,...,n). Then a(n) is the number of (0,1,2) n X n matrices A <= 2(J_n - I - P) with exactly one 1 and one 2 in every row and column.

Original entry on oeis.org

0, 2, 36, 1462, 83600, 5955474

Offset: 3

Vladimir Shevelev, Mar 23 2010

V. S. Shevelev, Development of the rook technique for calculating the cyclic indicators of (0,1)-matrices, Izvestia Vuzov of the North-Caucasus region, Nature sciences 4 (1996), 21-28 (in Russian).
S. E. Grigorchuk, V. S. Shevelev, An algorithm of computing the cyclic indicator of couples discordant permutations with restricted position, Izvestia Vuzov of the North-Caucasus region, Nature sciences 3 (1997), 5-13 (in Russian).

Cf. A001499, A007107, A082491, A000186, A174564.

A174581 Let J_n be an n X n all-1's matrix, I = I_n the n X n identity matrix and P = P_n the incidence matrix of the cycle (1,2,3,...,n). Then a(n) is the number of (0,1) n X n matrices A <= J_n - I - P - P^2 with exactly two 1's in every row and column.

Original entry on oeis.org

0, 1, 20, 1266, 102574, 9746472

Offset: 4

Vladimir Shevelev, Mar 23 2010

V. S. Shevelev, Development of the rook technique for calculating the cyclic indicators of (0,1)-matrices, Izvestia Vuzov of the North-Caucasus region, Nature sciences 4 (1996), 21-28 (in Russian).
S. E. Grigorchuk, V. S. Shevelev, An algorithm of computing the cyclic indicator of couples discordant permutations with restricted position, Izvestia Vuzov of the North-Caucasus region, Nature sciences 3 (1997), 5-13 (in Russian).

Cf. A001499, A007107, A082491, A000186, A174564, A174580.

A174586 Number of n X n (0,1) matrices with two 1's in each row having positive permanent.

Original entry on oeis.org

0, 1, 24, 954, 59040, 5295150, 651354480, 105393619800, 21717404916480, 5554438422838200, 1726882980691176000, 641506478978753110800, 280659563041747649760000, 142843312073975729801785200, 83684308104396267184700784000, 55915646244745131440225950320000

Offset: 1

Vladimir Shevelev, Mar 23 2010

nonn

a(n) is the normalized volume of the convex hull of (classical) parking functions of length n. - Andrés R. Vindas-Meléndez, Jan 13 2023

Vladimir Shevelev, On the permanent of the stochastic (0,1)-matrices with equal row sums, Izvestia Vuzov of the North-Caucasus region, Nature sciences 1 (1997), 21-38 (in Russian).

Aruzhan Amanbayeva and Danielle Wang, The convex hull of parking functions of length n, Enumer. Comb. Appl. 2 (2022), no. 2, Paper No. S2R10, 1.
Mitsuki Hanada, John Lentfer, and Andrés R. Vindas-Meléndez, Generalized parking function polytopes, arXiv:2212.06885 [math.CO], 2022.

Cf. A001499, A007107, A082491.

Table[n!/2^n * Sum[(2*i-1)*(2*i-1)!!*Binomial[n,i]*(2n-1)^(n-i-1),{i,0,n}],{n,1,20}] (* Vaclav Kotesovec, Nov 30 2017 *)

a(2)=1, for n>=3, a(n) = A001499(n) + Sum_{k=1..n-2} (-1)^(k+1)*k!*(C(n,k))^2*(n-k)^k*a(n-k).
a(n) = n!*((n-1)/2^(n-1))*Sum_{i=0..n-2} (2i+1)!!*C(n-2,i)*(2n-1)^(n-i-2). [corrected by John Lentfer, Oct 05 2022]
For n>=2, a(n) = (n!/2^n)*Sum_{i=0..n} (2i-1)*(2i-1)!!*C(n,i)*(2n-1)^(n-i-1).
a(n) = Gamma(3/4)*(sqrt(2)*Pi*e)^(-1/2)*n!*n^(n-1/4)*(1+O(n^((-1/4)+epsilon) with arbitrary small epsilon>0 for sufficiently large n.

A007108 Number of connected labeled 2-regular digraphs with n nodes.

Original entry on oeis.org

0, 0, 0, 1, 9, 216, 7560, 357120, 22025430, 1720751760, 166198926600, 19453788144000, 2714247736061400, 445133524289731200, 84788348720139464400, 18565341317290193025600, 4631048864538293219022000, 1305644758257711732981120000, 413133912085072442199311376000

Offset: 0

N. J. A. Sloane

From R. J. Mathar, Apr 29 2019: (Start)
The numbers of labeled 2-regular digraphs with n >= 1 nodes and 1 <= k <= n components are
           0;
           0,      0;
           1,      0,   0;
           9,      0,   0, 0;
         216,      0,   0, 0, 0;
        7560,     10,   0, 0, 0, 0;
      357120,    315,   0, 0, 0, 0, 0;
    22025430,  14931,   0, 0, 0, 0, 0, 0;
  1720751760, 879984, 280, 0, 0, 0, 0, 0, 0;
  ...
with row sums A007107. (End)

R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

Cf. A007107 (EXP-transform).

A174582 Let J_n be n X n matrix which contains 1's only, I=I_n be the n X n identity matrix and P=P_n be the incidence matrix of the cycle (1,2,3,...,n). Then a(n) is the number of (0,1,2) n X n matrices A<=2(J_n-I-P-P^2) with exactly one 1 and one 2 in every row and column.

Original entry on oeis.org

0, 2, 72, 3722, 329192, 32842446

Offset: 4

Vladimir Shevelev, Mar 23 2010

V. S. Shevelev, Development of the rook technique for calculating the cyclic indicators of (0,1)-matrices, Izvestia Vuzov of the North-Caucasus region, Nature sciences 4 (1996), 21-28 (in Russian).
S. E. Grigorchuk, V. S. Shevelev, An algorithm of computing the cyclic indicator of couples discordant permutations with restricted position, Izvestia Vuzov of the North-Caucasus region, Nature sciences 3 (1997), 5-13 (in Russian).

A001499 A007107 A082491 A000186 A174564 A174580 A174581

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

A219889 Number of directed 2-regular graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

A174564 Let J_n be n X n matrix which contains 1's only, I=I_n be the n X n identity matrix and P=P_n be the incidence matrix of the cycle (2,3,...,n,1). Then a(n) is the number of (0,1) n X n matrices A<=J_n-I-P with exactly two 1's in every row and column.

Views

Author

Keywords

References

Crossrefs

A284989 Triangle T(n,k) read by rows: the number of n X n {0,1} matrices with trace k where each row sum and each column sum is 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A284990 Triangle T(n,t) read by rows: the number of n X n {0,1} matrices with trace t where each row sum and each column sum is 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A174580 Let J_n be an n X n matrix which contains 1's only, I = I_n be the n X n identity matrix, and P = P_n be the incidence matrix of the cycle (1,2,3,...,n). Then a(n) is the number of (0,1,2) n X n matrices A <= 2(J_n - I - P) with exactly one 1 and one 2 in every row and column.

Views

Author

Keywords

References

Crossrefs

A174581 Let J_n be an n X n all-1's matrix, I = I_n the n X n identity matrix and P = P_n the incidence matrix of the cycle (1,2,3,...,n). Then a(n) is the number of (0,1) n X n matrices A <= J_n - I - P - P^2 with exactly two 1's in every row and column.

Views

Author

Keywords

References

Crossrefs

A174586 Number of n X n (0,1) matrices with two 1's in each row having positive permanent.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A007108 Number of connected labeled 2-regular digraphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A174582 Let J_n be n X n matrix which contains 1's only, I=I_n be the n X n identity matrix and P=P_n be the incidence matrix of the cycle (1,2,3,...,n). Then a(n) is the number of (0,1,2) n X n matrices A<=2(J_n-I-P-P^2) with exactly one 1 and one 2 in every row and column.

Views

Author

Keywords