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

%I M4154 N1726 #106 May 02 2024 09:45:02

%S 1,0,1,1,6,22,130,822,6202,52552,499194,5238370,60222844,752587764,

%T 10157945044,147267180508,2282355168060,37655004171808,

%U 658906772228668,12188911634495388,237669544014377896,4871976826254018760,104742902332392298296

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

%C 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.

%C From _Victor S. Miller_, Apr 26 2013: (Start)

%C 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).

%C 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]

%C From _Bruce Westbury_, Jan 22 2013: (Start)

%C It follows from the respective exponential generating functions that A002135 is the binomial transform of A002137:

%C A002135(n) = Sum_{k=0..n} C(n,k) * A002137(k),

%C 2 = 1*1 + 2*0 + 1*1,

%C 5 = 1*1 + 3*0 + 3*1 + 1*1,

%C 17 = 1*1 + 4*0 + 6*1 + 4*1 + 1*6, ...

%C 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)

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

%D N. J. Calkin, J. E. Janoski, matrices of row and column sum 2, Congr. Numerantium 192 (2008) 19-32

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

%H T. D. Noe, <a href="/A002137/b002137.txt">Table of n, a(n) for n = 0..100</a>

%H A. C. Aitken, <a href="http://dx.doi.org/10.1017/S0950184300000070">On the number of distinct terms in the expansion of symmetric and skew determinants</a>, Edinburgh Math. Notes, No. 34 (1944), 1-5.

%H A. C. Aitken, <a href="/A002135/a002135_2.pdf">On the number of distinct terms in the expansion of symmetric and skew determinants</a>, Edinburgh Math. Notes, No. 34 (1944), 1-5. [Annotated scanned copy]

%H Mark Colarusso, William Q. Erickson, and Jeb F. Willenbring, <a href="https://arxiv.org/abs/2012.06928">Contingency tables and the generalized Littlewood-Richardson coefficients</a>, arXiv:2012.06928 [math.RT], 2020.

%H Tomislav Došlic and Darko Veljan, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.066">Logarithmic behavior of some combinatorial sequences</a>, Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From _N. J. A. Sloane_, May 01 2012

%H I. M. H. Etherington, <a href="http://dx.doi.org/10.1017/S0950184300002639">Some problems of non-associative combinations</a>, Edinburgh Math. Notes, 32 (1940), 1-6.

%H Rui-Li Liu and Feng-Zhen Zhao, <a href="https://www.emis.de/journals/JIS/VOL21/Liu/liu19.html">New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.

%H P. A. MacMahon, <a href="https://doi.org/10.1112/plms/s2-17.1.25">Combinations derived from m identical sets of n different letters and their connexion with general magic squares</a>, Proc. London Math. Soc., 17 (1917), 25-41.

%H Victor S. Miller, <a href="http://mathoverflow.net/questions/128864/the-cayley-menger-theorem-and-integer-matrices-with-row-sum-2">The Cayley Menger Theorem and integer matrices with row sum 2</a> (on MathOverflow)

%H T. Muir, <a href="/A002135/a002135_1.pdf">The Theory of Determinants in the Historical Order of Development</a>, 4 vols., Macmillan, NY, 1906-1923. [Annotated scans of selected pages] See Vol. 3, p. 122.

%H Marko R. Riedel, <a href="https://math.stackexchange.com/questions/4908485/">Number of ways to derange n numbers ignoring direction, counted by Analytic Combinatorics</a> (2024)

%F E.g.f.: (1-x)^(-1/2)*exp(-x/2+x^2/4).

%F a(n) = (n-1)*(a(n-1)+a(n-2)) - (n-1)*(n-2)*a(n-3)/2.

%F a(n) ~ sqrt(2) * n^n / exp(n+1/4). - _Vaclav Kotesovec_, Feb 25 2014

%e a(2)=1 from

%e 02

%e 20

%e a(3)=1 from

%e 011

%e 101

%e 011

%e s(4)=6 from

%e 0200 0110

%e 2000 1001

%e 0002 1001

%e 0020 0110

%e x3 x3

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

%o (PARI) x='x+O('x^66); Vec( serlaplace( (1-x)^(-1/2)*exp(-x/2+x^2/4) ) ) \\ _Joerg Arndt_, Apr 27 2013

%Y Column k=2 of A333351.

%Y A diagonal of A260340.

%Y Cf. A000985, A000986, A002135.

%K nonn,nice,easy

%O 0,5

%A _N. J. A. Sloane_