|
%I M3548 N1437 #59 Jan 31 2024 13:20:48
%S 1,0,1,4,18,112,820,6912,66178,708256,8372754,108306280,1521077404,
%T 23041655136,374385141832,6493515450688,119724090206940,
%U 2337913445039488,48195668439235612,1045828865817825264,23826258064972682776,568556266922455167040
%N Number of n X n symmetric matrices with (0,1) entries and all row sums 2.
%C a(n) is the number of simple labeled graphs on n nodes with all vertices of degree 1 or 2.
%C From _R. J. Mathar_, Apr 07 2017: (Start)
%C 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 0: 1
%C 1: 0 0
%C 2: 0 0 1
%C 3: 1 0 3 0
%C 4: 3 0 12 0 3
%C 5: 12 0 70 0 30 0
%C 6: 70 0 465 0 270 0 15
%C 7: 465 0 3507 0 2625 0 315 0
%C See also A001205 for column t=0. (End)
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.8.
%D Herbert S. Wilf, Generatingfunctionology, p. 104.
%H 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 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 H. Gupta, <a href="/A000085/a000085.pdf">Enumeration of symmetric matrices</a> (annotated scanned copy)
%H 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 E.g.f.: (1-x)^(-1/2)*exp(-x-x^2/4 + x/((2*(1-x)))).
%F Sum_{a_1=0..n} Sum_{c=0..min(a_1, n - a_1)} Sum_{b=0..floor((n - a_1 - c)/2)} (
%F (-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)!}$
%F 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 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 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 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 a:= proc(n) option remember;
%p `if`(n<2, 1-n, add(binomial (n-1, k-1)
%p *(k! +`if`(k>2, (k-1)!, 0))/2 *a(n-k), k=2..n))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Feb 24 2011
%t a=1/(2(1-x))-1/2-x/2; b=(Log[1/(1-x)]-x-x^2/2)/2;
%t Range[0, 20]! CoefficientList[Series[Exp[a + b], {x, 0, 20}], x]
%t (* Second program: *)
%t 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 Cf. A000985, A001205.
%K nonn,nice,easy
%O 0,4
%A _N. J. A. Sloane_
| 