A000986 -id:A000986 - cp's OEIS frontend

A001205 Number of clouds with n points; number of undirected 2-regular labeled graphs; or number of n X n symmetric matrices with (0,1) entries, trace 0 and all row sums 2.

1, 0, 0, 1, 3, 12, 70, 465, 3507, 30016, 286884, 3026655, 34944085, 438263364, 5933502822, 86248951243, 1339751921865, 22148051088480, 388246725873208, 7193423109763089, 140462355821628771, 2883013994348484940

Offset: 0

N. J. A. Sloane

a(n) is the number of ways of covering K_n with cycles of length >= 3. Also number of 'frames' on n lines: given n lines in general position (none parallel and no three concurrent), a frame is a subset of n of the e C(n,2) points of intersection such that no three points are on the same line. - Mitch Harris, Jul 06 2006

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 410-411.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 276 and 279.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.7.
Ph. Flajolet, Singular combinatorics, pp. 561-571, Proc. Internat. Congr. Math., Beijing 2002, Higher Education Press, Beijing, 2002, Vol III.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 3.3.6b, 3.3.34.
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 Example 5.2.8. Also problems 5.23 and 5.15(a), case k=3.
Z. Tan and S. Gao, Enumeration of (0,1)-Symmetric Matrices, submitted [From Shanzhen Gao, Jun 05 2009] [apparently unpublished as of 2016]
H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 77, Eq. 3.9.1.
W. A. Whitworth, Choice and Chance, Bell, 1901, p. 269, ex. 160.

T. D. Noe, Table of n, a(n) for n=0..100
Editorial note, Robinson's constant, Amer. Math. Monthly, 59 (1952), 296-297.
Ph. Flajolet, Singular combinatorics, arXiv:math/0304465 [math.CO], 2003.
Ph. Flajolet and A. Odlyzko, Singularity analysis of generating functions, [Research Report] RR-0826, INRIA. 1988.
Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.
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.
H. Richter, Analyzing coevolutionary games with dynamic fitness landscapes, arXiv preprint arXiv:1603.06374 [q-bio.PE], 2016.
R. Robinson, A new absolute geometric constant?, Amer. Math. Monthly, 58 (1951), 462-469.
Weiping Wang, Tianming Wang, An automatic approach to the generating functions for some special sequences, Ars. Comb. 116 (2018) 263, Example 4.2
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 86, Eq. 3.9.1.

Cf. A000985, A000986, A002137. A diagonal of A059441 and A144163.

a := n -> (-1)^n*n!*add((3/4)^k*binomial(-1/2, n-k)*hypergeom([1/2,-k], [1/2-n+k], 1/3)/ k!, k=0..n): seq(simplify(a(n)), n=0..21); # Peter Luschny, Aug 26 2017

m = 21; CoefficientList[ Series[ Exp[-x/2 - x^2/4] / Sqrt[1-x], {x, 0, m}], x]*Table[n!, {n, 0, m}] (* Jean-François Alcover, Jun 21 2011, after e.g.f. *)

a(n):=sum(sum(binomial(k,i)*binomial(i-1/2,n-k)*(3^(k-i)*n!)/(4^k*k!)*(-1)^(n-i),i,0,k),k,0,n);
makelist(a(n),n,0,12); /* Emanuele Munarini, Aug 25 2017 */

a(n)=if(n<0,0,n!*polcoeff(exp(-x/2-x^2/4+x*O(x^n))/sqrt(1-x+x*O(x^n)),n))

a(n) ~ n!*exp(-3/4)/sqrt(Pi*n).
E.g.f.: exp(-x/2-x^2/4)/sqrt(1-x).
D-finite with recurrence a(n+1) = n*(a(n)+a(n-2)*(n-1)/2).
1/4^n * Sum_{b=0..floor(n/2)} Sum_{g=0..n-2*b} (-1)^(b+g) * 2^(2b+g) * n! * (2n-4b-2g)! / (b! * g! * (n-2b-g)!^2). - Shanzhen Gao, Jun 05 2009
a(n) = (-1)^n*n!*Sum_{k=0..n}(3/4)^k*binomial(-1/2, n - k)*hypergeom([1/2, -k], [1/2 - n + k], 1/3)/ k!. - Peter Luschny, Aug 26 2017

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

Original entry on oeis.org

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

A333157 Triangle read by rows: T(n,k) is the number of n X n symmetric binary matrices with k ones in every row and column.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 10, 18, 10, 1, 1, 26, 112, 112, 26, 1, 1, 76, 820, 1760, 820, 76, 1, 1, 232, 6912, 35150, 35150, 6912, 232, 1, 1, 764, 66178, 848932, 1944530, 848932, 66178, 764, 1, 1, 2620, 708256, 24243520, 133948836, 133948836, 24243520, 708256, 2620, 1

Offset: 0

Andrew Howroyd, Mar 09 2020

T(n,k) is the number of k-regular symmetric relations on n labeled nodes.
T(n,k) is the number of k-regular graphs with half-edges on n labeled vertices.
Terms may be computed without generating all graphs by enumerating the number of graphs by degree sequence. A PARI program showing this technique is given below. Burnside's lemma as applied in A122082 and A000666 can be used to extend this method to the case of unlabeled vertices A333159 and A333161 respectively.

			Triangle begins:
  1,
  1,   1;
  1,   2,     1;
  1,   4,     4,      1;
  1,  10,    18,     10,       1;
  1,  26,   112,    112,      26,      1;
  1,  76,   820,   1760,     820,     76,     1;
  1, 232,  6912,  35150,   35150,   6912,   232,   1;
  1, 764, 66178, 848932, 1944530, 848932, 66178, 764, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..230

Columns k=0..8 are A000012, A000085, A000986, A110040, A139670, A139671, A139673, A139674, A139675.
Row sums are A322698.
Central coefficients are A333164.
Cf. A188448 (transposed as array).
Cf. A059441, A295193, A333158, A333159, A333161.

\\ See script in A295193 for comments.
GraphsByDegreeSeq(n, limit, ok)={
  local(M=Map(Mat([x^0,1])));
  my(acc(p,v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(recurse(r,p,i,q,v,e) = if(e<=limit && poldegree(q)<=limit, if(i<0, if(ok(x^e+q, r), acc(x^e+q, v)), my(t=polcoeff(p,i)); for(k=0,t,self()(r,p,i-1,(t-k+x*k)*x^i+q,binomial(t,k)*v,e+k)))));
  for(k=2, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], my(p=src[i,1]); recurse(n-k, p, poldegree(p), 0, src[i,2], 0))); Mat(M);
}
Row(n)={my(M=GraphsByDegreeSeq(n, n\2, (p,r)->poldegree(p)-valuation(p,x) <= r + 1), v=vector(n+1)); for(i=1, matsize(M)[1], my(p=M[i,1], d=poldegree(p)); v[1+d]+=M[i,2]; if(pollead(p)==n, v[2+d]+=M[i,2])); for(i=1, #v\2, v[#v+1-i]=v[i]); v}
for(n=0, 8, print(Row(n))) \\ Andrew Howroyd, Mar 14 2020

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

A000985 Number of n X n symmetric matrices with nonnegative entries and all row sums 2.

Original entry on oeis.org

1, 1, 3, 11, 56, 348, 2578, 22054, 213798, 2313638, 27627434, 360646314, 5107177312, 77954299144, 1275489929604, 22265845018412, 412989204564572, 8109686585668956, 168051656468233972, 3664479286118269972, 83868072451846938336, 2009964340465840802576

Offset: 0

N. J. A. Sloane

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 Example 5.2.7.

T. D. Noe, Table of n, a(n) for n=0..100
Jacob L. Bourjaily, Michael Plesser, and Cristian Vergu, The Many Colours of Amplitudes, arXiv:2412.21189 [hep-th], 2024. See p. 33.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 584
H. Gupta, Enumeration of symmetric matrices, Duke Math. J., 35 (1968), vol 3, 653-659.
H. Gupta, Enumeration of symmetric matrices (annotated scanned copy)
Tomislav Došlic and Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019). - From _N. J. A. Sloane_, May 01 2012

Cf. A000986.

max = 21; egf[x_] := (1-x)^(-1/2)*Exp[x^2/4 + x/(2*(1-x))]; CoefficientList[ Series[ egf[x], {x, 0, max}], x]*Range[0, max]! (* Jean-François Alcover, Nov 25 2011 *)

E.g.f.: (1-x)^(-1/2)*exp(x^2/4 + x/(2*(1-x))).
a(n) ~ n^n*exp(sqrt(2*n)-n)/sqrt(2) * (1-5/(24*sqrt(2*n))). - Vaclav Kotesovec, Jul 29 2013
Recurrence: 2*a(n) = 2*(2*n-1)*a(n-1) - 2*(n-2)*(n-1)*a(n-2) - 2*(n-2)*(n-1)*a(n-3) + (n-3)*(n-2)*(n-1)*a(n-4). - Vaclav Kotesovec, Jul 29 2013

A002137 Number of n X n symmetric matrices with nonnegative integer entries, trace 0 and all row sums 2.

Original entry on oeis.org

1, 0, 1, 1, 6, 22, 130, 822, 6202, 52552, 499194, 5238370, 60222844, 752587764, 10157945044, 147267180508, 2282355168060, 37655004171808, 658906772228668, 12188911634495388, 237669544014377896, 4871976826254018760, 104742902332392298296

Offset: 0

N. J. A. Sloane

The definition implies that the matrices are symmetric, have entries 0, 1 or 2, have 0's on the diagonal, and the entries in each row or column sum to 2.
From Victor S. Miller, Apr 26 2013: (Start)
A002137 also is the number of monomials in the determinant of a generic n X n symmetric matrix with 0's on the diagonal (see the paper of Aitken).
It is also the number of monomials in the determinant of the Cayley-Menger matrix.  Even though this matrix is symmetric with 0's on the diagonal, it has 1's in the first row and column and so requires an extra argument. (End) [See the MathOverflow link for details of these bijections. - N. J. A. Sloane, Apr 27 2013]
From Bruce Westbury, Jan 22 2013: (Start)
It follows from the respective exponential generating functions that A002135 is the binomial transform of A002137:
A002135(n) = Sum_{k=0..n} C(n,k) * A002137(k),
2 = 1*1 + 2*0 + 1*1,
5 = 1*1 + 3*0 + 3*1 + 1*1,
17 = 1*1 + 4*0 + 6*1 + 4*1 + 1*6, ...
A002137 arises from looking at the dimension of the space of invariant tensors of the r-th tensor power of the adjoint representation of the symplectic group Sp(2n) (for n large compared to r). (End)
Also the number of subgraphs of a labeled K_n made up of cycles and isolated edges (but no isolated vertices). - Kellen Myers, Oct 17 2014

			a(2)=1 from
  02
  20
a(3)=1 from
  011
  101
  011
s(4)=6 from
  0200 0110
  2000 1001
  0002 1001
  0020 0110
  x3   x3

N. J. Calkin, J. E. Janoski, matrices of row and column sum 2, Congr. Numerantium 192 (2008) 19-32
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 Example 5.2.8.

T. D. Noe, Table of n, a(n) for n = 0..100
A. C. Aitken, On the number of distinct terms in the expansion of symmetric and skew determinants, Edinburgh Math. Notes, No. 34 (1944), 1-5.
A. C. Aitken, On the number of distinct terms in the expansion of symmetric and skew determinants, Edinburgh Math. Notes, No. 34 (1944), 1-5. [Annotated scanned copy]
Jacob L. Bourjaily, Michael Plesser, and Cristian Vergu, The Many Colours of Amplitudes, arXiv:2412.21189 [hep-th], 2024. See pp. 17, 52.
Mark Colarusso, William Q. Erickson, and Jeb F. Willenbring, Contingency tables and the generalized Littlewood-Richardson coefficients, arXiv:2012.06928 [math.RT], 2020.
Tomislav Došlic and Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From _N. J. A. Sloane_, May 01 2012
I. M. H. Etherington, Some problems of non-associative combinations, Edinburgh Math. Notes, 32 (1940), 1-6.
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.
P. A. MacMahon, Combinations derived from m identical sets of n different letters and their connexion with general magic squares, Proc. London Math. Soc., 17 (1917), 25-41.
Victor S. Miller, The Cayley Menger Theorem and integer matrices with row sum 2 (on MathOverflow)
T. Muir, The Theory of Determinants in the Historical Order of Development, 4 vols., Macmillan, NY, 1906-1923. [Annotated scans of selected pages] See Vol. 3, p. 122.
Marko R. Riedel, Number of ways to derange n numbers ignoring direction, counted by Analytic Combinatorics (2024)

Column k=2 of A333351.
A diagonal of A260340.
Cf. A000985, A000986, A002135.

nxt[{n_,a_,b_,c_}]:={n+1,b,c,n(b+c)-n(n-1) a/2}; Drop[Transpose[ NestList[ nxt,{0,1,0,1},30]][[2]],2] (* Harvey P. Dale, Jun 12 2013 *)

x='x+O('x^66); Vec( serlaplace( (1-x)^(-1/2)*exp(-x/2+x^2/4) ) ) \\ Joerg Arndt, Apr 27 2013

E.g.f.: (1-x)^(-1/2)*exp(-x/2+x^2/4).
a(n) = (n-1)*(a(n-1)+a(n-2)) - (n-1)*(n-2)*a(n-3)/2.
a(n) ~ sqrt(2) * n^n / exp(n+1/4). - Vaclav Kotesovec, Feb 25 2014

A136281 Number of graphs on n labeled nodes with degree at most 2.

Original entry on oeis.org

1, 1, 2, 8, 41, 253, 1858, 15796, 152219, 1638323, 19467494, 252998224, 3568259503, 54263159347, 884834059454, 15397757661092, 284767413357977, 5576696746139689, 115269732256964626, 2507575465491619672, 57262481225957071721, 1369461739453440893261

Offset: 0

Don Knuth, Mar 31 2008

nonn

These are thunderstorm graphs. Their connected components are a single cycle (clouds), a path (lightning bolts) or an isolated vertex (raindrops). - Geoffrey Critzer, May 11 2011

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.

Alois P. Heinz, Table of n, a(n) for n = 0..445 (terms n=1..200 from Vincenzo Librandi)
Samuele Giraudo, Combalgebraic structures on decorated cliques, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 8, arXiv:1709.08416 [math.CO], 2017.

Cf. A000085 (degree at most 1), A136282-A136286.

f = (Log[1/(1-x)]+1/(1-x) -x^2/2 - 1)/2;
Range[0,25]! CoefficientList[Series[Exp[f],{x,0,25}],x] (* Geoffrey Critzer, May 11 2011 *)

Binomial transform of A000986. E.g.f.: (1-x)^(-1/2)*exp(-x^2/4 + x/((2*(1-x)))). - Vladeta Jovovic, May 20 2008
a(n) = (2*n-1)*a(n-1) - (n-1)^2*a(n-2) + (n-2)*(n-1)*a(n-3) - (n-3)*(n-2)*(n-1)/2*a(n-4). - Vaclav Kotesovec, Aug 10 2013
a(n) ~ n^n*exp(sqrt(2*n)-1/2-n)/sqrt(2) * (1+19/(24*sqrt(2*n))). - Vaclav Kotesovec, Aug 10 2013

More terms from Vladeta Jovovic, May 20 2008

a(0)=1 prepended by Alois P. Heinz, Jul 21 2021

A110040 Number of {2,3}-regular graphs; i.e., labeled simple graphs (no multi-edges or loops) on n vertices, each of degree 2 or 3.

Original entry on oeis.org

1, 0, 0, 1, 10, 112, 1760, 35150, 848932, 24243520, 805036704, 30649435140, 1322299270600, 64008728200384, 3447361661136640, 205070807479444088, 13388424264027157520, 953966524932871436800, 73817914562041635228928

Offset: 0

Marni Mishna, Jul 08 2005

P-recursive.
Starting at n=3, number of symmetric binary matrices with all row sums 3. - R. H. Hardin, Jun 12 2008
From R. J. Mathar, Apr 07 2017: (Start)
These are the row sums of the following matrix, which counts symmetric n X n {0,1} matrices with each row and column sum equal to 3 and trace t, 0 <= t <= n:
0:  1
1:  0 0
2:  0 0 0
3:  0 0 0 1
4:  1 0 6 0 3
5:  0 30 0 70 0 12
6:  70 0 810 0 810 0 70
7:  0 5670 0 19355 0 9660 0 465
This has A001205 on the diagonal. (End)
The traceless (2n) X (2n) binary matrices in that triangle seem to be counted in A002829. - Alois P. Heinz, Apr 07 2017

			(Graphs listed by edgeset)
a(3)=1: {(1,2), (2,3), (3,1)}
a(4)=10: {(1,2), (2,3), (3,4), (4,1)}, {(1,2), (2,3), (3,4), (4,1), (1,4)}, {(1,2), (2,3), (3,4), (4,1), (2,3)}, {(1,2), (2,4), (3,4), (1,3)}, {(1,2), (2,4), (3,4), (1,3), (2,3)}, {(1,2), (2,4), (3,4), (1,3), (1,4)}, {(1,3), (2,3), (2,4), (1,4)}, {(1,3), (2,3), (2,4), (1,4), (1,2)}, {(1,3), (2,3), (2,4), (1,4), (3,4)}, {(1,2), (1,3), (1,4) (2,3), (2,4), (3,4)},

Tan and S. Gao, Enumeration of (0,1)-Symmetric Matrices, submitted [From Shanzhen Gao, Jun 05 2009]

Vaclav Kotesovec, Table of n, a(n) for n = 0..320
I. P. Goulden and D. M. Jackson, Labelled graphs with small vertex degrees and P-recursiveness, SIAM J. Algebraic Discrete Methods 7(1986), no. 1, 60--66. MR0819706 (87k:05093). [Gives e.g.f.]

Cf. A002829, A110039, A110041.

Cf. A000986 (sums 2), A000085 (sums 1), A139670 (sums 3).

RecurrenceTable[{-b[n] - b[1 + n] + (-2 + 3*n)*b[2 + n] - 14*b[3 + n] + (105 + 30*n)*b[4 + n] + (-69 - 12*n)*b[5 + n] + (582 + 147*n + 9*n^2)* b[6 + n] + (-20 - 6*n)*b[7 + n] + (1160 + 363*n + 27*n^2)*b[8 + n] + (1554 + 255*n + 9*n^2)* b[9 + n] + (-2340 - 414*n - 18*n^2)*b[10 + n] + (-528 - 48*n)*b[11 + n] + (288 + 24*n)*b[12 + n] == 0, b[0] == 1, b[1] == 0, b[2] == 0, b[3] == 1/6, b[4] == 5/12, b[5] == 14/15, b[6] == 22/9, b[7] == 3515/504, b[8] == 30319/1440, b[9] == 10823/162, b[10] == 8385799/37800, b[11] == 510823919/665280}, b, {n, 0, 25}] * Range[0, 25]! (* Vaclav Kotesovec, Oct 23 2023 *)

Satisfies the linear recurrence: (-150917976*n^2 - 105258076*n^3 - 1925*n^9 - 13339535*n^5 - 45995730*n^4 - 357423*n^7 - 2637558*n^6 - 120543840*n - n^11 - 66*n^10 - 39916800 - 32670*n^8)*a(n) + (-11028590*n^4 - 65*n^9 - n^10 - 2310945*n^5 - 1860*n^8 - 30810*n^7 - 326613*n^6 - 80627040*n - 39916800 - 34967140*n^3 - 70290936*n^2)*a(n + 1) + (3*n^10 - 39916800 + 187*n^9 + 5076*n^8 + 78558*n^7 + 761103*n^6 + 4757403*n^5 + 18949074*n^4 + 44946092*n^3 + 51046344*n^2 - 793440*n)*a(n + 2) + (-93139200 - 16175880*n^3 - 56394184*n^2 - 110513760*n - 2854446*n^4 - 14*n^8 - 840*n^7 - 21756*n^6 - 317520*n^5)*a(n + 3) + (45780*n^6 + 1785*n^7 + 111580320*n^2 + 660450*n^5 + 5856270*n^4 + 32645865*n^3 + 174636000 + 213450300*n + 30*n^8)*a(n + 4) + (-22952160 - 681*n^6 - 16419*n^5 - 217995*n^4 - 8082204*n^2 - 20896956*n - 12*n^7 - 1721253*n^3)*a(n + 5) + (1804641*n^3 + 9*n^7 + 14442*n^5 + 208920*n^4 + 32266080 + 9307488*n^2 + 26537388*n + 552*n^6)*a(n + 6) + (-158400 - 15160*n - 3994*n^3 - 31072*n^2 - 6*n^5 - 248*n^4)*a(n + 7) + (20123*n^3 + 706210*n + 27*n^5 + 170067*n^2 + 1148400 + 1173*n^4)*a(n + 8) + (7899*n^2 + 60684*n + 444*n^3 + 9*n^4 + 170940)*a(n + 9) + (-6894*n - 25740 - 18*n^3 - 612*n^2)*a(n + 10) + (-48*n - 528)*a(n + 11) + 24*a(n + 12).
Differential equation satisfied by the exponential generating function {F(0) = 1, 9*t^4*(t^4 + t - 2 + 3*t^2)^2*(d^2/dt^2)F(t) + 3*t*(t^4 + t - 2 + 3*t^2)*(10*t^8 + 34*t^3 - 16*t + 16*t^6 - 2*t^5 - 24*t^2 - 4*t^7 + 8 + t^10 - 14*t^4)*(d/dt)F(t) - t^3*(-22*t^2 + t^8 - 24*t^3 + t^9 + 8*t^7 + 14*t^6 + 15*t^5 + 12 + 16*t + 9*t^4)*(t^4 + t - 2 + 3*t^2)*F(t)}.
Sum_{a_2 = 0..n} Sum_{d_2 = 0..min(floor((3n - 2a_2)/2), floor(n/2), n - a_2)} Sum_{d_3 = 0..min(floor((3n - 2a_2 - 2d_2)/3), floor((n-2d_2)/3), n - a_2 - d_2} Sum_{d_1 = 0..min(3n - 2a_2 - 2d_2 - 3d_3, n - 2d_2 - 3d_3) Sum_{b = 0..min(floor((3n - 2a_2 - 2d_2 - 3d_3 - d_1)/4), floor((n - d_2 - d_3 - a_2)/2)} Sum_{c = 0..min(floor((3n - 2a_2 - 2d_2 - 3d_3 - d_1 - 4b)/6), floor((n - a_2 - 2b - d_2 - d_3)/2))} Sum_{a_1 = ceiling((3n - (2a_2 + 4b + 6c + d_1 + 2d_2 + 3d_3))/2)..floor((3n - (2a_2 + 4b + 6c + d_1 + 2d_2 + 3d_3))/2)} (-1)^(a_2 + b + d_2)*n!*(2a_1 + d_1)!/(2^(n + a_1 - c - d_3)*3^(n - a_2 - 2b - d_2 - c)*a_1!*a_2!*b!*c!*d_1!*d_2!*d_3!*(n - a_2 - 2b - d_2 - 2c - d_3)!). - Shanzhen Gao, Jun 05 2009
Recurrence (of order 8): 12*(27*n^4 - 423*n^3 + 2427*n^2 - 5639*n + 4384)*a(n) = 6*(n-1)*(81*n^4 - 1242*n^3 + 7011*n^2 - 15528*n + 10352)*a(n-1) + 3*(n-2)*(n-1)*(81*n^5 - 1269*n^4 + 7551*n^3 - 20841*n^2 + 29934*n - 16040)*a(n-2) - 3*(n-2)*(n-1)*(135*n^5 - 2115*n^4 + 13287*n^3 - 37537*n^2 + 46430*n - 21848)*a(n-3) + (n-3)*(n-2)*(n-1)*(567*n^5 - 9396*n^4 + 59895*n^3 - 169590*n^2 + 191744*n - 57040)*a(n-4) - 2*(n-4)*(n-3)*(n-2)*(n-1)*(135*n^4 - 1386*n^3 + 5034*n^2 - 6529*n + 648)*a(n-5) + (n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(81*n^5 - 1566*n^4 + 11367*n^3 - 37080*n^2 + 47872*n - 17424)*a(n-6) - (n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(27*n^4 - 315*n^3 + 1113*n^2 - 1433*n + 348)*a(n-7) - (n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(27*n^4 - 315*n^3 + 1320*n^2 - 1946*n + 776)*a(n-8). - Vaclav Kotesovec, Oct 23 2023
a(n) ~ 3^(n/2) * n^(3*n/2) / (2^(n + 1/2) * exp(3*n/2 - sqrt(3*n) + 13/4)) * (1 + 119/(24*sqrt(3*n)) - 2519/(3456*n)). - Vaclav Kotesovec, Oct 27 2023, extended Oct 28 2023

Edited and extended by Max Alekseyev, May 08 2010

A139670 Number of n X n symmetric binary matrices with all row sums 4.

Original entry on oeis.org

1, 26, 820, 35150, 1944530, 133948836, 11234051976, 1127512146540, 133475706272700, 18406586045919060, 2925154024273348296, 530686776655470875076, 109004840145995702773410, 25164525076896596670014400, 6486836210471246515195539840, 1856264107759263993451053077856

Offset: 4

R. H. Hardin, Jun 12 2008

nonn

From R. J. Mathar, Apr 07 2017: (Start)
These are the row sums of the following triangle, which shows in row n and column t the number of symmetric n X n {0,1}-matrices with trace t and 4 ones in each row and each column, 0 <= t <= n:
   1;
   0,     0;
   0,     0,     0;
   0,     0,     0,     0;
   0,     0,     0,     0,     1;
   1,     0,    10,     0,    15,     0;
  15,     0,   270,     0,   465,     0,    70;
 465,     0,  9660,     0, 19355,     0,  5670,     0;
(End)

Andrew Howroyd, Table of n, a(n) for n = 4..30

Column k=4 of A333157 and row 4 of A188448.

Cf. A000085 (row sums 1), A000986 (row sums 2), A110040 (row sums 3).

Terms a(13) and beyond from Andrew Howroyd, Mar 09 2020

A188448 T(n,k)=Number of (n*k)Xk binary arrays with nonzero rows in decreasing order, no more than 2 ones in any row and exactly n ones in every column.

Original entry on oeis.org

1, 2, 0, 4, 1, 0, 10, 4, 0, 0, 26, 18, 1, 0, 0, 76, 112, 10, 0, 0, 0, 232, 820, 112, 1, 0, 0, 0, 764, 6912, 1760, 26, 0, 0, 0, 0, 2620, 66178, 35150, 820, 1, 0, 0, 0, 0, 9496, 708256, 848932, 35150, 76, 0, 0, 0, 0, 0, 35696, 8372754, 24243520, 1944530, 6912, 1, 0, 0, 0, 0

Offset: 1

R. H. Hardin Mar 31 2011

Table starts
.1.2.4.10..26...76...232.....764......2620........9496.........35696
.0.1.4.18.112..820..6912...66178....708256.....8372754.....108306280
.0.0.1.10.112.1760.35150..848932..24243520...805036704...30649435140
.0.0.0..1..26..820.35150.1944530.133948836.11234051976.1127512146540
.0.0.0..0...1...76..6912..848932.133948836.26615510712
.0.0.0..0...0....1...232...66178..24243520
.0.0.0..0...0....0.....1.....764
.0.0.0..0...0....0.....0
.0.0.0..0...0....0
.0.0.0..0...0

			All solutions for 9X3
..1..1..0
..1..0..1
..1..0..0
..0..1..1
..0..1..0
..0..0..1
..0..0..0
..0..0..0
..0..0..0

R. H. Hardin, Table of n, a(n) for n = 1..108

Row 1 is A000085
Row 2 is A000986
Row 3 is A110040
Row 4 is A139670
Row 5 is A139671
Row 6 is A139673
Row 7 is A139674
Row 8 is A139675

A134648 Number of 2n X n (0,1)-matrices with row sums 2 and column sums 4.

Original entry on oeis.org

0, 1, 90, 44730, 56586600, 154700988750, 807998767676100, 7373018003758407000, 109829050417159537464000, 2532230252503738514963235000, 86574740102712303011539719750000, 4237239732072431006302896746240010000

Offset: 1

Shanzhen Gao, Nov 05 2007

nonn

t(m,n) in the formula gives the number of (0,1)-matrices of size m*n with row sum 4 and column sum 2. a(n) in the formula gives the number of (0,1)-matrices of size n*(2n) with row sum 4 and column sum 2. - Shanzhen Gao, Feb 16 2010

			Number of  4 X 2 (0,1)-matrices:       1;
Number of  6 X 3 (0,1)-matrices:      90;
Number of  8 X 4 (0,1)-matrices:   44730;
Number of 10 X 5 (0,1)-matrices: 5658660.

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.

R. H. Hardin, Table of n, a(n) for n = 1..49

Cf. A000681, A000986, A132202, A134645, A134646, A139670, etc.

B:=Binomial; F:=Factorial;
f:= func< m,n,k,j | B(m, k)*B(m-k, j)*B(2*m+2*k-2*j, m+k-j)*F(m+k-j) >;
t:= func< m,n | ((-1)^m*F(n)/8^m)*(&+[(&+[f(m,n,k,j)*(-1)^(j+k)/(12)^k: k in [0..m-j]]): j in [0..m]]) >;
A134648:= func< n | F(2*n)*t(n,n)/F(n) >;
[A134648(n): n in [1..30]]; // G. C. Greubel, Oct 13 2023

t[m_, n_]:= t[m, n]= ((-1)^m*n!/8^m)*Sum[Binomial[m,k]*Binomial[m-k,j]*Binomial[2*m+2*k-2*j,m+k-j]*(m+k-j)!*(-1)^(j+k)/(12)^k, {j,0, m}, {k,0,m-j}];
A134648[n_]:= (2*n)!*t[n,n]/n!;
Table[A134648[n], {n,30}] (* G. C. Greubel, Oct 13 2023 *)

b=binomial; F=factorial;
def f(m,n,k,j): return b(m, k)*b(m-k, j)*b(2*m+2*k-2*j, m+k-j)*F(m+k-j)
def t(m,n): return ((-1)^m*F(n)/8^m)*sum(sum(f(m,n,k,j)*(-1)^(j+k)/(12)^k for k in range(m-j+1)) for j in range(m+1))
def A134648(n): return F(2*n)*t(n,n)/F(n)
[A134648(n) for n in range(1,31)] # G. C. Greubel, Oct 13 2023

a(n) = (2*n)!*t(n,n)/n!, where t(m, n) = (1/24^m)*Sum_{j=0..m} Sum_{k=0..m-j} ( (-1)^(m-j-k)*3^j*6^(m-j-k)*m!*n!*(4*k+2*(m-j-k))! )/( j!*k!*(m-j-k)!*(2*k+(m-j-k))!*2^(2*k+(m-j-k)) ).
a(n) = (1/24^n)*Sum_{j=0..n} Sum_{k=0..n-j} ((-1)^(n-j-k)*3^j*6^(n-j-k)*n!(2n)!(2n-2j+2k)!/(j!k!(n-j-k)!(n-j+k)!*2^(n-j+k))). - Shanzhen Gao, Feb 16 2010
a(n) ~ sqrt(Pi) * 2^(3*n + 3/2) * n^(4*n + 1/2) / (3^n * exp(4*n + 3/2)). - Vaclav Kotesovec, Oct 21 2023

a(7) onwards from R. H. Hardin, Oct 18 2009

cp's OEIS Frontend

A001205 Number of clouds with n points; number of undirected 2-regular labeled graphs; or number of n X n symmetric matrices with (0,1) entries, trace 0 and all row sums 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

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

A333157 Triangle read by rows: T(n,k) is the number of n X n symmetric binary matrices with k ones in every row and column.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A000985 Number of n X n symmetric matrices with nonnegative entries and all row sums 2.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A002137 Number of n X n symmetric matrices with nonnegative integer entries, trace 0 and all row sums 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A136281 Number of graphs on n labeled nodes with degree at most 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A110040 Number of {2,3}-regular graphs; i.e., labeled simple graphs (no multi-edges or loops) on n vertices, each of degree 2 or 3.

Views

Author

Keywords

Comments