A001499 -id:A001499 - cp's OEIS frontend

A008300 Triangle read by rows: T(n,k) (n >= 0, 0 <= k <= n) gives number of {0,1} n X n matrices with all row and column sums equal to k.

1, 1, 1, 1, 2, 1, 1, 6, 6, 1, 1, 24, 90, 24, 1, 1, 120, 2040, 2040, 120, 1, 1, 720, 67950, 297200, 67950, 720, 1, 1, 5040, 3110940, 68938800, 68938800, 3110940, 5040, 1, 1, 40320, 187530840, 24046189440, 116963796250, 24046189440, 187530840, 40320, 1, 1, 362880, 14398171200, 12025780892160, 315031400802720, 315031400802720, 12025780892160, 14398171200, 362880, 1

Offset: 0

N. J. A. Sloane

Or, triangle of multipermutation numbers T(n,k), n >= 0, 0 <= k <= n: number of relations on an n-set such that all vertical sections and all horizontal sections have k elements.

			Triangle begins:
  1;
  1,    1;
  1,    2,       1;
  1,    6,       6,        1;
  1,   24,      90,       24,        1;
  1,  120,    2040,     2040,      120,       1;
  1,  720,   67950,   297200,    67950,     720,    1;
  1, 5040, 3110940, 68938800, 68938800, 3110940, 5040, 1;
  ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 236, P(n,k).

Brendan D. McKay, Rows n = 0..30, flattened
C. J. Everett and P. R. Stein, The asymptotic number of integer stochastic matrices, Disc. Math. 1 (1971), 55-72.
Richard J. Mathar, 2-regular Digraphs of the Lovelock Lagrangian, arXiv:1903.12477 [math.GM], 2019.
Richard J. Mathar, Rencontres for equipartite distributions of multisets of colored balls into urns, vixra:2306.0157 (2023)
B. D. McKay, Applications of a technique for labeled enumeration, Congress. Numerantium, 40 (1983), 207-221.
Brendan D. McKay, first 30 rows : entries named Bv[n,k,n,k]
Wouter Meeussen, relevant entries from B. D. McKay reference

Row sums give A067209.
Central coefficients are A058527.
Cf. A000142 (column 1), A001499 (column 2), A001501 (column 3), A058528 (column 4), A075754 (column 5), A172544 (column 6), A172541 (column 7), A172536 (column 8), A172540 (column 9), A172535 (column 11), A172534 (column 12), A172538 (column 13), A172537 (column 14).
Cf. A133687, A333157 (symmetric matrices), A257493 (nonnegative elements), A260340 (up to row permutations), A364068 (traceless).

T(n, k)={
  local(M=Map(Mat([n, 1])));
  my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(recurse(i, p, v, e) = if(i<0, if(!e, acc(p, v)), my(t=polcoef(p,i)); for(j=0, min(t, e), self()(i-1, p+j*(x-1)*x^i, binomial(t, j)*v, e-j))));
  for(r=1, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], recurse(k-1, src[i, 1], src[i, 2], k))); vecsum(Mat(M)[,2]);
} \\ Andrew Howroyd, Apr 03 2020

Comtet quotes Everett and Stein as showing that T(n,k) ~ (kn)!(k!)^(-2n) exp( -(k-1)^2/2 ) for fixed k as n -> oo.

T(n,k) = T(n,n-k).

More terms from Greg Kuperberg, Feb 08 2001

A053871 a(0)=1; a(1)=0; a(n) = 2(n-1)(a(n-1) + a(n-2)).

Original entry on oeis.org

1, 0, 2, 8, 60, 544, 6040, 79008, 1190672, 20314880, 387099936, 8148296320, 187778717632, 4702248334848, 127140703364480, 3691602647581184, 114562300528369920, 3784124901630435328, 132555364873399378432, 4908221631901073295360, 191549525877429961604096

Offset: 0

Cris Moore (moore(AT)santafe.edu) and Christian G. Bower, Mar 29 2000

Number of deranged matchings of 2n people with partners (of either sex) other than their spouse. 2n objects are initially paired in some way and then are re-paired so that no object is with its original partner (the dancing problem in the article).
Of interest in the "collision problem", where, given a 2-to-1 function f, we are asked for x, y such that f(x)=f(y).
2^n*n!*a(n) = (2n)! b(n) where b(n) are the probabilities that appear in Margolis (2001). One interpretation is in terms of matchings or 1-factors of the complete graph on 2n vertices. The number of these is (2n)!/2^{n}n!. The number of 1-factors being disjoint from (that is, having no edges in common with) a given 1-factor is then a(n); and then b(n) is the probability of picking such a disjoint one factor at random.
Also n!*a(n) = 2^n * c(n) where c(n) = A001499(n). If we define d(n,k) = k(n-1)(d(n-1,k) + d(n-2,k)), with d(0,k) = 1 and d(1,k) = 0, so d(n,1) are the derangement numbers A000166, then a(n) = d(n,2) (cf. A033030, A088991). On the other hand, taking d*(n,k) = d(n,k)/k^{n}, we have d*(n,k) = (n-1)(d*(n-1,k) + d*(n-2,k)/k), with d*(0,k) = 1 and d*(1,k) = 0 and it is easy to see from Bricard's recurrence for c(n) that c(n)/n! satisfies this for k = 2.
A proof that the description in the first comment as "number of deranged matchings" implies the defining recursion relation: let (x_1, y_1), (x_2, y_2), ..., (x_n, y_n) be the given pairs. In a deranged matching x_1 will be paired with any of the 2(n-1) objects x_2, y_2, x_3, y_3, ..., x_n, y_n. It is sufficient to count only those deranged matchings in which x_1, is matched with x_2. They are of two kinds: (i) y_1 is not matched with y_2; their number is a(n-1); (ii) y_1 is matched with y_2; their number is a(n-2). - Emeric Deutsch, Jan 23 2009
Inverse binomial transform of the odd double factorials (A001147). - David Callan, Aug 25 2009
From Lewis Mammel (l_mammel(AT)att.net), Oct 07 2009: (Start)
The formula is given directly by the Principle of Inclusion and Exclusion.
The first term includes all pairings, the second term excludes all pairings containing each pair, the third term includes all pairings containing each pair of pairs, and so on.
Based on n-a -> n for large n, the ratio a(n)/(2n-1)!! -> exp(-1/2) ~= 0.60653.
We find a(n)/(2n-1)!! for n= 100, 200, 300, 400 ~= 0.6050124904, 0.6057720290, 0.6060250088, 0.6061514604. (End)
This is a subset of the set of pairings of the first 2n integers (A001147) in another way: forbidding pairs of the form (2k,2k+1) for all k as well as the pair (1,2n) (seeing the constraint as circular by opposition to the linear A165968). - Olivier Gérard, Feb 08 2011
a(n) is the n-th central moment of a central chi-squared distribution (with 1 degree of freedom), i.e., a(n) = E[ (Y- E[Y] )^n ] = E[ (X^2 - 1 )^n ] where Y is chi-squared, X is std normal, X~N(0,1), and the expectation operator is E[]. - David Fioramonti, May 11 2016
Exponential self-convolution of a(n)/2^n gives subfactorials (A000166). - Vladimir Reshetnikov, Oct 09 2016
For n > 1, also the number of maximum matchings in the n-cocktail party graph. - Eric W. Weisstein, Jun 15 2017
Number of polygonal tiles with n sides with two exits per side and n edges connecting pairs of exits, with no edges between exits on the same side (cf. A289191, A289269 for nonisomorphic tiles under rotational and rotational and reflectional symmetries). - Marko Riedel, Jun 28 2017
Number of ways n people can hold hands (every hand is holding another hand) where no one is holding their own hand. - Harry Richman, Aug 29 2023

R. Bricard, L'Intermédiaire des Mathématiciens, 8 (1901), 312-313.

Michael De Vlieger, Table of n, a(n) for n = 0..404 (First 100 terms from _T. D. Noe_)
A. Ayyer, Determinants and Perfect Matchings, arXiv:1106.1465 [math.CO], 2011.
Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7. - From _N. J. A. Sloane_, Feb 06 2013
Bela Bollobas, The number of 1-factors in 2k-connected graphs, J. Combin. Theory Ser. B 25 (1978), no. 3, 363--366. MR0516268 (80m:05060) - _N. J. A. Sloane_, Mar 26 2012
James N. Brawner, Dinner, Dancing and Tennis, Anyone?, Mathematics Magazine, Vol. 73, No 1 (2000).
M. A. Brodie, Avoiding your spouse at a party leads to war, Math. Mag., 75 (2002), 203-208.
Davi B. Costa, Bogdan A. Dobrescu, and Patrick J. Fox, Chiral Abelian gauge theories with few fermions, arXiv:2001.11991 [hep-ph], 2020.
Barbara H. Margolius, Dinner-Diner Matching Probabilities
B. H. Margolius, Avoiding your spouse at a bridge party, Math. Mag., 74 (2001), 33-41.
B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118.
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set

Cf. A054479, A001147, A001818, A000166, A001499.
See A289191 for when rotational symmetries of the tiles are taken into account. - Marko Riedel, Jun 28 2017
Cf. A165968, number of pairings of 2n things disjoint to a given pairing, and containing a given pair not in the given pairing. It is given by a(n)/(2n-2). - Lewis Mammel (l_mammel(AT)att.net), Oct 07 2009

a053871 n = a053871_list !! n
a053871_list = 1 : 0 : zipWith (*)
   [2,4..] (zipWith (+) a053871_list $ tail a053871_list)
-- Reinhard Zumkeller, Mar 07 2012

f:= gfun:-rectoproc({a(0) = 1, a(1) = 0, a(n) = 2*(n - 1)*(a(n - 1) + a(n - 2))},a(n),remember):
map(f, [$0..30]); # Robert Israel, May 10 2016

RecurrenceTable[{a[0]==1,a[1]==0,a[n]==2(n-1)(a[n-1]+a[n-2])}, a[n],{n,20}] (* Harvey P. Dale, Sep 15 2011 *)
CoefficientList[Assuming[{Element[x, Reals], x>0}, Series[Sqrt[Pi/2] * (I + Erfi[Sqrt[(1+1/x)/2]]) / (E^((1+x)/(2*x)) * Sqrt[x*(x+1)]), {x, 0, 20}]], x] (* Vaclav Kotesovec, Feb 15 2015 *)
Range[0, 20]! CoefficientList[Series[1/(Exp[x] Sqrt[1 - 2 x]), {x, 0, 20}], x] (* Eric W. Weisstein, Jun 15 2017 *)
Table[(-1)^n HypergeometricPFQ[{1/2, -n}, {}, 2], {n, 20}] (* Eric W. Weisstein, Jun 15 2017 *)
Table[I (-1)^n HypergeometricU[1/2, 3/2 + n, -1/2]/Sqrt[2], {n, 20}] (* Eric W. Weisstein, Dec 31 2017 *)

a(n)=(-1)^(n+1)*sum(k=0,n,(-1)^k*binomial(n,k)*prod(i=0,k,2*i-1))

a(n) = A054479(n)/A001147(n).
E.g.f.: 1/(exp(x)*sqrt(1-2x)).
a(n) = (-1)^n*Sum_{k=0..n} (-1)^k*C(n, k)*(2*k-1)!!. - Benoit Cloitre, May 01 2003; corrected by David Fioramonti, May 17 2016
a(n) = Integral_{x>=0} (x-1)^n * (exp(-x/2)/sqrt(2*Pi*x)) dt. - Paul Barry, Apr 12 2010
Conjectured g.f.: T(0)/(1+x), where T(k) = 1 - x*(k+1)/(x*(k+1) - (1+x)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 13 2013
a(n) ~ 2^(n+1/2) * n^n / exp(n+1/2). - Vaclav Kotesovec, Mar 11 2014
G.f.: Sum_{k>=0} (2*k - 1)!!*x^k/(1 + x)^(k+1). - Ilya Gutkovskiy, Apr 12 2019
Conjecture: if m == n (mod q) for q odd, then (-1)^m*a(m) == (-1)^n*a(n) (mod q). - Harry Richman, Aug 29 2023

More terms from James Sellers, Apr 08 2000

A001501 Number of n X n 0-1 matrices with all column and row sums equal to 3.

Original entry on oeis.org

1, 0, 0, 1, 24, 2040, 297200, 68938800, 24046189440, 12025780892160, 8302816499443200, 7673688777463632000, 9254768770160124288000, 14255616537578735986867200, 27537152449960680597739468800, 65662040698002721810659005184000

Offset: 0

N. J. A. Sloane

Also, for n >= 3, number of bicubical graphs on 2n labeled nodes of two colors [Read, 1958, 1971] - N. J. A. Sloane, Sep 08 2014

Also number of ways to arrange 3n rooks on an n X n chessboard, with no more than 3 rooks in each row and column (no 4 in a line). - Vaclav Kotesovec, Aug 03 2013

			G.f. = 1 + x^3 + 24*x^4 + 2040*x^5 + 297200*x^6 + 68938800*x^7 + ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 236, P(n,3).
R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
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, Wadsworth, Vol. 1, 1986; see Example 1.1.3, page 2, f(n).
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.

Alois P. Heinz, Table of n, a(n) for n = 0..185 (first 51 terms from T. D. Noe)
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)
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]
Bo-Ying Wang, 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. A001499. Column 3 of A008300. Row sums of A284990.

a:= n-> n!^2/6^n *add(add((-1)^b *2^a *3^b *(3*n-3*a-2*b)!/
        (a! *b! *(n-a-b)!^2 *6^(n-a-b)), b=0..n-a), a=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Mar 20 2011
# second Maple program:
a:= proc(n) option remember; `if`(n<4, (n-1)*(n-2)/2,
      n*(n-1)*(9*(3*n^2-5*n+4)*a(n-1)+(3*n-6)*(3*n+1)*
      (n-1)*a(n-2)+(9*n^2-30*n+13)*(n-1)*(n-2)^2*a(n-3)
      -(3*n-2)*(n-1)*(n-2)^2*(n-3)^2*a(n-4))/(36*n-60))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Mar 13 2017

Table[6^(-n) Total[Map[(-1)^#[[2]] n!^2 (#[[2]] + 3 #[[3]])! 2^#[[1]] 3^#[[2]]/(#[[1]]! #[[2]]! #[[3]]!^2 6^#[[3]]) &, Compositions[n, 3]]], {n, 0, 20}] (* Geoffrey Critzer, Mar 19 2011 *)
a[n_] := n!^2*Sum[2^(2k-n)*3^(k-n)*(3(n-k))!*HypergeometricPFQ[{k-n, k-n}, {3(k-n)/2, 1/2 + 3(k-n)/2}, -9/2]/(k! (n-k )!^2), {k, 0, n}]/6^n;
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 07 2018 *)

{a(n) = local(k); if( n<0, 0, n!^2 * sum(j=0, n, sum(i=0, n-j, if(1, k=n-i-j; (j + 3*k)! / (3^i * 36^k * i! * k!^2))) / (j! * (-2)^j)))}; /* Michael Somos, May 28 2002 */

a(n) = n!^2/6^n * Sum_{a=0..n} Sum_{b=0..n-a} (-1)^b * 2^a * 3^b * (3*n-3*a-2*b)! / (a! * b! * (n-a-b)!^2 * 6^(n-a-b)). - Shanzhen Gao, Feb 19 2010
D-finite with recurrence: 12*(3*n-5)*a(n) = 9*n*(3*n^2-5*n+4)*(n-1)*a(n-1) + 3*(n-2)*n*(3*n+1)*(n-1)^2*a(n-2) + (n-2)^2*n*(9*n^2-30*n+13)*(n-1)^2*a(n-3) - (n-3)^2*(n-2)^2*n*(3*n-2)*(n-1)^2*a(n-4). - Vaclav Kotesovec, Aug 03 2013
a(n) ~ sqrt(6*Pi) * (3/4)^n * n^(3*n+1/2) / exp(3*n+2). - Vaclav Kotesovec, Aug 03 2013

Additional comments from Michael Somos, May 28 2002

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

A007107 Number of labeled 2-regular digraphs with n nodes.

Original entry on oeis.org

1, 0, 0, 1, 9, 216, 7570, 357435, 22040361, 1721632024, 166261966956, 19459238879565, 2714812050902545, 445202898702992496, 84798391618743138414, 18567039007438379656471, 4631381194792101913679985, 1305719477625154539392776080, 413153055417968797025496881656

Offset: 0

N. J. A. Sloane

Or number of n X n matrices with exactly two 1's in each row and column which are not in the main diagonal, other entries 0 (cf. A001499). - Vladimir Shevelev, Mar 22 2010

Number of 2-factors of the n-crown graph. - Andrew Howroyd, Feb 28 2016

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..254 (first 49 terms from R. W. Robinson)
O. Gonzalez, C. Beltran and I. Santamaria, On the Number of Interference Alignment Solutions for the K-User MIMO Channel with Constant Coefficients, arXiv preprint arXiv:1301.6196 [cs.IT], 2013. - From _N. J. A. Sloane_, Feb 19 2013
R. J. Mathar, OEIS A007107, Mar 15 2019

Cf. column t=0 of A284989.

Cf. A007108 (log transform), A197458 (row and column sum <=2), A219889 (unlabeled), A001499 (loops allowed).

a:= proc(n) option remember; `if`(n<5, ((n-1)*(n-2)/2)^2,
      (n-1)*(2*(n^3-2*n^2+n+1)*a(n-1)/(n-2)+((n^2-2*n+2)*
      (n+1)*a(n-2) +(2*n^2-6*n+1)*n*a(n-3)+(n-3)*(a(n-4)*
      (n^3-5*n^2+3)-(n-4)*(n-1)*(n+1)*a(n-5))))/(2*n))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Apr 10 2017

Table[Sum[Sum[Sum[(-1)^(k+j-s)*n!*(n-k)!*(2n-k-2j-s)!/(s!*(k-s)!*(n-k-j)!^2*j!*2^(2n-2k-j)),{j,0,n-k}],{s,0,k}],{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, May 09 2014 after Shanzhen Gao *)

a(n)=sum(k=0,n, sum(s=0,k, sum(j=0,n-k, (-1)^(k+j-s)*n!*(n-k)!*(2*n-k-2*j-s)!/(s!*(k-s)!*(n-k-j)!^2*j!*2^(2*n-2*k-j))))) \\ Charles R Greathouse IV, Feb 08 2017

a(n) = Sum_{k=0..n} Sum_{s=0..k} Sum_{j=0..n-k} (-1)^(k+j-s)*n!*(n-k)!*(2n-k-2j-s)!/(s!*(k-s)!*(n-k-j)!^2*j!*2^(2n-2k-j)). - Shanzhen Gao, Nov 05 2007

a(n) ~ 2*sqrt(Pi) * n^(2*n+1/2) / exp(2*n+5/2). - Vaclav Kotesovec, May 09 2014

A197458 Number of n X n binary matrices with at most two 1's in each row and column, other entries 0.

Original entry on oeis.org

1, 2, 16, 265, 7343, 304186, 17525812, 1336221251, 129980132305, 15686404067098, 2297230134084416, 400977650310256537, 82188611938415464231, 19536244019455339261970, 5328019975275896220786388, 1651867356348327784988233291, 577522171260292028520919811777

Offset: 0

Felix A. Pahl, Oct 15 2011

nonn

Filling out an n x n square grid with 0's and 1's at math.stackexchange
R. J. Mathar, The number of binary n X m matrices with at most k 1's in each row or column, (2014) Table 2.

Cf. A001499, A002720. Column of A283500.

import java.math.BigInteger;
public class AtMostTwoOnes {
    public static void main (String [] args) {
        for (int n = 0;n <= 40;n++) {
            BigInteger [] [] [] counts = new BigInteger [n + 1] [n + 1] [n + 1]; // counts [m] [k] [l] : number of mxn matrices with k column sums 0, l column sums 1
            for (int k = 0;k <= n;k++)
                for (int l = 0;l <= n;l++)
                    counts [0] [k] [l] = BigInteger.ZERO;
            counts [0] [n] [0] = BigInteger.ONE; // only one 0xn matrix, with all n column sums 0
            for (int m = 1;m <= n;m++) {
                BigInteger [] [] old = counts [m - 1];
                for (int k = 0;k <= n;k++)
                    for (int l = 0;l <= n;l++) {
                        BigInteger sum = BigInteger.ZERO;
                        // new row contains no 1s
                        sum = sum.add (old [k] [l]);
                        // new row contains one 1
                        //   added to column sum 0
                        if (k < n && l > 0)
                            sum = sum.add (old [k + 1] [l - 1].multiply (BigInteger.valueOf (k + 1)));
                        //   added to column sum 1
                        if (l < n)
                            sum = sum.add (old [k] [l + 1].multiply (BigInteger.valueOf (l + 1)));
                        // new row contains two 1s
                        //   added to two column sums 0
                        if (k < n - 1 && l > 1)
                            sum = sum.add (old [k + 2] [l - 2].multiply (BigInteger.valueOf (((k + 2) * (k + 1)) / 2)));
                        //   added to one column sum 0, one column sum 1
                        if (k < n)
                            sum = sum.add (old [k + 1] [l].multiply (BigInteger.valueOf ((k + 1) * l)));
                        //   added to two column sums 1
                        if (l < n - 1)
                            sum = sum.add (old [k] [l + 2].multiply (BigInteger.valueOf (((l + 2) * (l + 1)) / 2)));
                        counts [m] [k] [l] = sum;
                    }
            }
            BigInteger sum = BigInteger.ZERO;
            for (int k = 0;k <= n;k++)
                for (int l = 0;l <= n;l++)
                    sum = sum.add (counts [n] [k] [l]);
            System.out.println (n + " : " + sum);
        }
    }
}

a(n) = Sum_{k=0}^n Sum_{l=0}^{n-k} a(k,l,n,n) where a(k,l,m,n) is the number of binary m X n matrices with at most two 1's per row, k columns with sum 0, l columns with sum 1 and the remaining n - k - l columns with sum 2.

a(k,l,m,n) = a(k,l,m-1,n) +(k+1)*a(k+1,l-1,m-1,n) +(l+1)*a(k,l+1,m-1,n) +(k+1)*2*a(k+2,l-2,m-1,n)/(k+2) +(k+1)*l*a(k+1,l,m-1,n) +(l+1)*2*a(k,l+2,m-1,n)/(l+2).

A082491 a(n) = n! * d(n), where n! = factorial numbers (A000142), d(n) = subfactorial numbers (A000166).

Original entry on oeis.org

1, 0, 2, 12, 216, 5280, 190800, 9344160, 598066560, 48443028480, 4844306476800, 586161043776000, 84407190782745600, 14264815236056985600, 2795903786354347468800, 629078351928420506112000, 161044058093696572354560000, 46541732789077953723039744000

Offset: 0

Emanuele Munarini, Apr 28 2003

a(n) is also the number of pairs of n-permutations p and q such that p(x)<>q(x) for each x in { 1, 2, ..., n }.
Or number of n X n matrices with exactly one 1 and one 2 in each row and column, other entries 0 (cf. A001499). - Vladimir Shevelev, Mar 22 2010
a(n) is approximately equal to (n!)^2/e. - J. M. Bergot, Jun 09 2018

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Ira Gessel, Enumerative applications of symmetric functions, Séminaire Lotharingien de Combinatoire, B17a (1987), 17 pp.
Shawn L. Witte, Link Nomenclature, Random Grid Diagrams, and Markov Chain Methods in Knot Theory, Ph. D. Dissertation, University of California-Davis (2020).

Cf. A000142, A000166.

with (combstruct):a:=proc(m) [ZL, {ZL=Set(Cycle(Z, card>=m))}, labeled]; end: ZLL:=a(2):seq(count(ZLL, size=n)*n!, n=0..15); # Zerinvary Lajos, Jun 11 2008

Table[Subfactorial[n]*n!, {n, 0, 15}] (* Zerinvary Lajos, Jul 10 2009 *)

A000166[0]:1$
A000166[n]:=n*A000166[n-1]+(-1)^n$
  makelist(n!*A000166[n], n, 0, 12); /* Emanuele Munarini, Mar 01 2011 */

d(n)=if(n<1, n==0, n*d(n-1)+(-1)^n);
a(n)=d(n)*n!;
vector(33,n,a(n-1))
/* Joerg Arndt, May 28 2012 */

{a(n) = if( n<2, n==0, n! * round(n! / exp(1)))}; /* Michael Somos, Jun 24 2018 */

A082491_list, m, x = [], 1, 1
for n in range(10*2):
    x, m = x*n**2 + m, -(n+1)*m
    A082491_list.append(x) # Chai Wah Wu, Nov 03 2014

val A082491_pairs: LazyList[BigInt && BigInt] =
  (BigInt(0), BigInt(1)) #::
  (BigInt(1), BigInt(0)) #::
  lift2 {
    case ((n, z), (_, y)) =>
      (n+2, (n+2)*(n+1)*((n+1)*z+y))
  } (A082491_pairs, A082491_pairs.tail)
val A082491: LazyList[BigInt] =
  lift1(_._2)(A082491_pairs)
/** Luc Duponcheel, Jan 25 2020 */

a(n) = n! * d(n) where d(n) = A000166(n).
a(n) = Sum_{k=0..n} binomial(n, k)^2 * (-1)^k * (n - k)!^2 * k!.
a(n+2) = (n+2)*(n+1) * ( a(n+1) + (n+1)*a(n) ).
a(n) ~ 2*Pi*n^(2*n+1)*exp(-2*n-1). - Ilya Gutkovskiy, Dec 04 2016

A123544 Number of connected labeled 2-regular relations of order n.

Original entry on oeis.org

0, 0, 1, 6, 87, 1980, 66270, 3050460, 184716630, 14231775600, 1359481407480, 157694893448400, 21835679256606600, 3557942554594428000, 673941365091485290800, 146851484638349504613600

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.

R. W. Robinson, Table of n, a(n) for n = 0..48

Connected version of A001499. Unlabeled version is A005642.

Cf. A123543.

m = 16;
a1499[n_] := (n - 1)*n!*Gamma[n - 1/2]*Hypergeometric1F1[2 - n, 3/2 - n, -1/2]/Sqrt[Pi];
egf = Log[1 + Sum[a1499[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} A001499(k)*x^k/k!). - Andrew Howroyd, Sep 09 2018

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

cp's OEIS Frontend

A008300 Triangle read by rows: T(n,k) (n >= 0, 0 <= k <= n) gives number of {0,1} n X n matrices with all row and column sums equal to k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A053871 a(0)=1; a(1)=0; a(n) = 2*(n-1)*(a(n-1) + a(n-2)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A001501 Number of n X n 0-1 matrices with all column and row sums equal to 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

A007107 Number of labeled 2-regular digraphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A197458 Number of n X n binary matrices with at most two 1's in each row and column, other entries 0.

Views

Author

Keywords

Links

Crossrefs

Programs

A053871 a(0)=1; a(1)=0; a(n) = 2(n-1)(a(n-1) + a(n-2)).