login
Number of n X n symmetric matrices with (0,1) entries and all row sums 2.
(Formerly M3548 N1437)
11

%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_