cp's OEIS Frontend

A000986 Number of n X n symmetric matrices with (0,1) entries and all row sums 2.

%I A000986 M3548 N1437 #63 Apr 14 2025 07:38:11
%S A000986 1,0,1,4,18,112,820,6912,66178,708256,8372754,108306280,1521077404,
%T A000986 23041655136,374385141832,6493515450688,119724090206940,
%U A000986 2337913445039488,48195668439235612,1045828865817825264,23826258064972682776,568556266922455167040
%N A000986 Number of n X n symmetric matrices with (0,1) entries and all row sums 2.
%C A000986 a(n) is the number of simple labeled graphs on n nodes with all vertices of degree 1 or 2.
%C A000986 From _R. J. Mathar_, Apr 07 2017: (Start)
%C A000986 These are the row sums of the following triangle which shows the number of symmetric n X n {0,1} matrices with row and column sums 2 refined for trace t, 0 <= t <= n:
%C A000986   0:    1
%C A000986   1:    0  0
%C A000986   2:    0  0    1
%C A000986   3:    1  0    3 0
%C A000986   4:    3  0   12 0    3
%C A000986   5:   12  0   70 0   30 0
%C A000986   6:   70  0  465 0  270 0  15
%C A000986   7:  465  0 3507 0 2625 0 315 0
%C A000986 See also A001205 for column t=0.  (End)
%D A000986 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000986 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000986 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.8.
%D A000986 Herbert S. Wilf, Generatingfunctionology, p. 104.
%H A000986 Alois P. Heinz, <a href="/A000986/b000986.txt">Table of n, a(n) for n = 0..445</a> (first 101 terms from T. D. Noe)
%H A000986 H. Gupta, <a href="http://dx.doi.org/10.1215/S0012-7094-68-03567-9">Enumeration of symmetric matrices</a>, Duke Math. J., 35 (1968), vol 3, 653-659.
%H A000986 H. Gupta, <a href="/A000085/a000085.pdf">Enumeration of symmetric matrices</a> (annotated scanned copy)
%H A000986 Zhonghua Tan, Shanzhen Gao, and H. Niederhausen, <a href="http://dx.doi.org/10.1007/s11766-006-0013-4">Enumeration of (0,1) matrices with constant row and column sums</a>, Appl. Math. Chin. Univ. 21 (4) (2006) 479-486.
%F A000986 E.g.f.: (1-x)^(-1/2)*exp(-x-x^2/4 + x/((2*(1-x)))).
%F A000986 Sum_{a_1=0..n} Sum_{c=0..min(a_1, n - a_1)} Sum_{b=0..floor((n - a_1 - c)/2)} ((-1)^((n - a_1 - 2b - c) + b)*n!*(2a_1)!) / (2^(n + a_1 - 2c)*a_1!*(n - a_1 - 2b - c)!*b!*(2c)!*(a_1 - c)!). - _Shanzhen Gao_, Jun 05 2009
%F A000986 Conjecture: 2*a(n) +2*(-2*n+1)*a(n-1) +2*(n^2-2*n-1)*a(n-2) -2*(n-2)*(n-4)*a(n-3) +(n-1)*(n-2)*(n-3)*a(n-4) -(n-2)*(n-3)*(n-4)*a(n-5)=0. - _R. J. Mathar_, Aug 04 2013
%F A000986 Recurrence: 2*a(n) = 4*(n-1)*a(n-1) - 2*(n-3)*(n-1)*a(n-2) - (n-3)*(n-2)*(n-1)*a(n-4). - _Vaclav Kotesovec_, Feb 13 2014
%F A000986 a(n) ~ n^n * exp(sqrt(2*n)-n-3/2) / sqrt(2) * (1 + 43/(24*sqrt(2*n))). - _Vaclav Kotesovec_, Feb 13 2014
%p A000986 a:= proc(n) option remember;
%p A000986        `if`(n<2, 1-n, add(binomial (n-1, k-1)
%p A000986         *(k! +`if`(k>2, (k-1)!, 0))/2 *a(n-k), k=2..n))
%p A000986     end:
%p A000986 seq(a(n), n=0..30);  # _Alois P. Heinz_, Feb 24 2011
%t A000986 a=1/(2(1-x))-1/2-x/2; b=(Log[1/(1-x)]-x-x^2/2)/2;
%t A000986 Range[0, 20]! CoefficientList[Series[Exp[a + b], {x, 0, 20}], x]
%t A000986 (* Second program: *)
%t A000986 a[n_] := a[n] = If[n<2, 1-n, Sum[Binomial[n-1, k-1]*(k! + If[k>2, (k-1)!, 0])/2*a[n-k], {k, 2, n}]]; Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Feb 20 2017, after _Alois P. Heinz_ *)
%Y A000986 Cf. A000985, A001205.
%K A000986 nonn,nice,easy
%O A000986 0,4
%A A000986 _N. J. A. Sloane_