[seqfan] symmetric 0-1 matrices

Brendan McKay bdm at cs.anu.edu.au
Wed Feb 2 14:19:09 CET 2011

Here is a basic 2-dimensional sequence that appears to be
missing from OEIS.

Let SM(n,m) be the number of symmetric 0-1 matrices of order n such
that the total number of 1s is m. 

Clearly SM(n,m) is nonzero for 0 <= m <= n^2.  Also it is clear
that SM(n,n^2-m) = SM(n,m).

Here are the smaller values:

SM(1,m) = 1,1
SM(2,m) = 1,2,2,2,1
SM(3,m) = 1,3,6,10,12,12,10,6,3,1
SM(4,m) = 1,4,12,28,52,84,116,140,150,140,116,84,52,28,12,4,1
SM(5,m) = 1,5,20,60,150,326,620,1060,1635,2295,2952,3480,3780,

SM(20,100) = 116055963240718364860093486257933930590507733779088

In general SM(n,m) is the sum of
   binomial(n,k) * binomial(n*(n-1)/2,(m-k)/2)
over those k with the same parity as m.  To see this consider
that k is the number of 1s on the diagonal.  I don't find any
closed form for that sum or other useful expression for it.

Does anyone know any more about his sequence?


More information about the SeqFan mailing list