login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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} (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 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

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), 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]

Tomislav DoŇ°lic, 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.

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.

FORMULA

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

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(n-1) 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( (1-x)^(-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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 21 04:22 EST 2018. Contains 299389 sequences. (Running on oeis4.)