

A002137


Number of n X n symmetric matrices with nonnegative integer entries, trace 0 and all row sums 2.
(Formerly M4154 N1726)


6



1, 0, 1, 1, 6, 22, 130, 822, 6202, 52552, 499194, 5238370, 60222844, 752587764, 10157945044, 147267180508, 2282355168060, 37655004171808, 658906772228668, 12188911634495388, 237669544014377896, 4871976826254018760, 104742902332392298296
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

The definition implies that the matrices are symmetric, have entries 0, 1 or 2, have zeros 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 CayleyMenger 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} (n choose 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 rth 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


REFERENCES

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.


LINKS

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), 15.
A. C. Aitken, On the number of distinct terms in the expansion of symmetric and skew determinants, Edinburgh Math. Notes, No. 34 (1944), 15. [Annotated scanned copy]
Tomislav Došlic, Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math. 308 (2008), no. 11, 21822212. MR2404544 (2009j:05019)  From N. J. A. Sloane, May 01 2012
I. M. H. Etherington, Some problems of nonassociative combinations, Edinburgh Math. Notes, 32 (1940), 16.
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), 2541.
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, 19061923. [Annotated scans of selected pages] See Vol. 3, p. 122.


FORMULA

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


EXAMPLE

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


MATHEMATICA

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


PROG

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


CROSSREFS

Cf. A000985, A000986, A002135.
A diagonal of A260340.
Sequence in context: A193463 A009358 A213130 * A009361 A193445 A075759
Adjacent sequences: A002134 A002135 A002136 * A002138 A002139 A002140


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane


STATUS

approved



