A002137 Number of n X n symmetric matrices with nonnegative integer entries, trace 0 and all row sums 2.

1, 0, 1, 1, 6, 22, 130, 822, 6202, 52552, 499194, 5238370, 60222844, 752587764, 10157945044, 147267180508, 2282355168060, 37655004171808, 658906772228668, 12188911634495388, 237669544014377896, 4871976826254018760, 104742902332392298296

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

The definition implies that the matrices are symmetric, have entries 0, 1 or 2, have 0's 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} C(n,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

Examples

			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
		

References

• N. J. Calkin, J. E. Janoski, matrices of row and column sum 2, Congr. Numerantium 192 (2008) 19-32
• 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]
• Jacob L. Bourjaily, Michael Plesser, and Cristian Vergu, The Many Colours of Amplitudes, arXiv:2412.21189 [hep-th], 2024. See pp. 17, 52.
• Mark Colarusso, William Q. Erickson, and Jeb F. Willenbring, Contingency tables and the generalized Littlewood-Richardson coefficients, arXiv:2012.06928 [math.RT], 2020.
• Tomislav Došlic and 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.
• Rui-Li Liu and Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
• 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.
• Marko R. Riedel, Number of ways to derange n numbers ignoring direction, counted by Analytic Combinatorics (2024)

Crossrefs

Column k=2 of A333351.

A diagonal of A260340.

Cf. A000985, A000986, A002135.

Programs

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 *)

PARI

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

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