[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,
3780,3480,2952,2295,1635,1060,620,326,150,60,20,5,1
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?
Brendan.
More information about the SeqFan
mailing list