[seqfan] Re: symmetric 0-1 matrices

Charles Greathouse 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.).

Charles Greathouse
Analyst/Programmer
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,
>           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.
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/



More information about the SeqFan mailing list