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,4

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

Links

Table of n, a(n) for n=0..25.

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

Example

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].

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

Prog

(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), ", "))

Crossrefs

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

Sequence in context: A265173 A264573 A225959 * A045905 A012680 A012684

Adjacent sequences: A336171 A336172 A336173 * A336175 A336176 A336177

Keyword

nonn

Author

Torlach Rush, Jul 10 2020

Extensions

More terms from Peter Luschny, Jun 05 2021

Status

approved