[seqfan] Re: symmetric 0-1 matrices

[Robert Israel]

On Thu, 3 Feb 2011, Brendan McKay 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.

According to Maple,

> simplify(sum(binomial(n,2*j)*binomial(r,M-j),j=0..M)) assuming posint;

binomial(r,M)*hypergeom([-M, -1/2*n, 1/2-1/2*n],[1/2, r-M+1],-1)

> simplify(sum(binomial(n,2*k+1)*binomial(r,M-k),k=0..M)) assuming posint;

n*binomial(r,M)*hypergeom([-M, 1-1/2*n, 1/2-1/2*n],[3/2, r-M+1],-1)

If m is even you want the first formula with r=n*(n-1)/2 and M=m/2, if m 
is odd the second formula with r=n*(n-1)/2 and M=(m+1)/2.
Thus for n=5 and m=6,
    binomial(10,3)*hypergeom([-3,-5/2,-2],[1/2,8],-1) = 620
and for n=5 and m=5,
    5*binomial(10,3)*hypergeom([-3, -3/2, -2],[3/2, 8],-1) = 1060.

Robert Israel                                israel at math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            Vancouver, BC, Canada