A336174 Number of non-symmetric binary n X n matrices M over the reals such that M^2 is the transpose of M.

0, 0, 0, 2, 16, 80, 360, 1680, 8064, 39872, 209920, 1168640, 6779520, 41403648, 265434624, 1765487360, 12227461120, 88163164160, 656547803136, 5054718763008, 40261284495360, 330010833797120, 2783003768258560, 24166721457815552, 215318925878132736, 1966855934150246400

Offset: 0

Author

Torlach Rush, Jul 10 2020

Keywords

• nonn

Comments

We classify the (0,1) n X n matrices M_n by k, the number of 1's.

Let [T(n,k), n >= 0, k=0..n], be the lower triangular matrix where T(n,k) is the number of M^2 matrices equal to the transpose of M for n and k. Then:

T(n,n) = A001471(n).

Column sequences k=3..7 (without leading 0's) are:

T(n,3) = A001471(3) * A000292(n+1).

T(n,4) = A001471(4) * A000332(n+4).

T(n,5) = A001471(5) * A000389(n+5).

T(n,6) = A001471(6) * A000579(n+6).

T(n,7) = A001471(7) * A000580(n+7).

Row sums of T(n,k) generate known terms of this sequence and the next term a(10) evaluates to 209920 (see conjectured formula below).

Examples

			a(3) = 2 because [0,1,0]    [0,1,0]    [0,0,1]
                 [0,0,1]  * [0,0,1]  = [1,0,0]
                 [1,0,0]    [1,0,0]    [0,1,0],
             and [0,0,1]    [0,0,1]    [0,1,0]
                 [1,0,0]  * [1,0,0]  = [0,0,1]
                 [0,1,0]    [0,1,0]    [1,0,0].
		

Crossrefs

Cf. A000292, A000332, A000389, A000579, A000580, A001471, A344912.

Programs

Maple

a := n -> 2^n*(add(n!/(24^k*k!*(n-3*k)!), k=0..n/3) - 1): seq(a(n), n=0..25);
# Alternative:
gf := exp(x*(x^2+6)/3) - exp(2*x): ser := series(gf,x,32):
seq(n!*coeff(ser,x,n), n = 0..25); # Peter Luschny, Jun 05 2021

PARI

m(n, t) = matrix(n, n, i, j, (t>>(i*n+j-n-1))%2)
a(n) = sum(t = 0, 2^n^2-1, m(n, t)^2 == m(n, t)~) - 2^n
for(n = 0, 9, print1(a(n), ", "))

Formula

a(n) = Sum_{k=0..n} A001471(k) * binomial(n, k). [Previously conjectured, for a proof see the link in A344912.]

From Peter Luschny, Jun 05 2021: (Start)

a(n) = 2^n*(add(n!/(24^k * k! * (n - 3*k)!), k=0..n/3) - 1).

a(n) = 2^n*(hypergeom([-n/3, (1 - n)/3, (2 - n)/3], [], -9/8) - 1).

a(n) = [x^n] exp(x*(x^2 + 6)/3) - exp(2*x). (End)

D-finite with recurrence (-n+3)*a(n) +4*(n-2)*a(n-1) +4*(-n+1)*a(n-2) +(n-1)*(n-2)*(n-3)*a(n-3) -2*(n-1)*(n-2)*(n-3)*a(n-4)=0. - R. J. Mathar, Jul 27 2022

Extensions

More terms from Peter Luschny, Jun 05 2021