[seqfan] Re: symmetric 0-1 matrices
charles.greathouse at case.edu
Wed Feb 2 15:54:45 CET 2011
This does look like a nice sequence ((and I hope you submit it). I
don't find it in any of the common ways that it might be listed (as a
tabf 1,1,1,2,2,2,1,1,3,6,..., by antidiagonals, by antidiagonals
dropping the first row and/or column, etc.).
Case Western Reserve University
On Wed, Feb 2, 2011 at 8:19 AM, Brendan McKay <bdm at cs.anu.edu.au> wrote:
> 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?
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan