A184948 Triangle read by rows: SM(n,m) is the number of symmetric 0-1 matrices of order n such that the total number of 1's is m (n >= 1, 0 <= m <= n^2).

1, 1, 1, 2, 2, 2, 1, 1, 3, 6, 10, 12, 12, 10, 6, 3, 1, 1, 4, 12, 28, 52, 84, 116, 140, 150, 140, 116, 84, 52, 28, 12, 4, 1, 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

Offset

1,4

Links

Alois P. Heinz, Rows n = 1..31, flattened

P. Cameron, T. Prellberg and D. Stark, Asymptotics for incidence matrix classes, Electron. J. Combin. 13 (2006), #R85, p. 11.

Formula

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.

From Robert Israel, Feb 02 2011: (Start)

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. (End)

G.f. for row n: (1+x)^n*(1+x^2)^(n(n-1)/2 for n>=1. - Paul D. Hanna, Feb 03 2011

G.f.: A(x,y) = Sum_{n>=1} x^n*(1+y)^n*Product_{k=1..n} (1-x(1+y)(1+y^2)^(2k-2))/(1-x(1+y)(1+y^2)^(2k-1)) due to a q-series identity. - Paul D. Hanna, Feb 03 2011

Sum_{k>=0..n^2} k*SM(n,k) = n^2/2 * 2^(n(n+1)/2).

SM(n,m) = Sum_{k=0..floor(m/2)} C(C(n,2),k)*C(n,m-2*k), from equation (11) in the Cameron et al., reference. - L. Edson Jeffery, Feb 29 2012

Example

Triangle begins:
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
...

Mathematica

row[n_] := CoefficientList[(1+x)^n (1+x^2)^(n(n-1)/2), x];
Array[row, 5] // Flatten (* Jean-François Alcover, Mar 19 2019 *)

Prog

(PARI) {SM(n, k)=polcoeff((1+x^2)^(n*(n-1)/2)*(1+x)^n, k)} \\ Paul D. Hanna
(PARI) {SM(n, k)=local(A); A=sum(m=1, n, x^m*(1+y)^m*prod(k=1, m, (1-x*(1+y)*(1+y^2)^(2*k-2))/(1-x*(1+y)*(1+y^2)^(2*k-1)+x*O(x^n)))); polcoeff(polcoeff(A, n, x), k, y)} \\ Paul D. Hanna

Crossrefs

Row sums give A006125(n+1).

Cf. A262666.

Sequence in context: A131823 A089722 A172356 * A242775 A079562 A338664

Adjacent sequences: A184945 A184946 A184947 * A184949 A184950 A184951

Keyword

nonn,tabf

Author

N. J. A. Sloane, Feb 03 2011, based on a posting to the Sequence Fans Mailing List by Brendan McKay, Feb 02 2011

Status

approved