A379105 Triangular array read by rows. T(n,k) is the number of n X n matrices T over GF(2) such that there are exactly 2^k vectors v in GF(2)^n with Tv=v, n>=0, 0<=k<=n.

1, 1, 1, 6, 9, 1, 168, 294, 49, 1, 20160, 37800, 7350, 225, 1, 9999360, 19373760, 4036200, 144150, 961, 1, 20158709760, 39687459840, 8543828160, 326932200, 2542806, 3969, 1, 163849992929280, 325139829719040, 71124337751040, 2812314375360, 23435953128, 42677334, 16129, 1

Offset: 0

Author

Geoffrey Critzer, Dec 15 2024

Keywords

• nonn
• tabl

Comments

Sum_{k=0..n} T(n,k)*2^k = (2^(n+1)-1)*2^(n^2-n) so that as n->oo the average number of fixed points is 2.

T(n,k) is also the number of n X n matrices over GF(2) with nullity k. As n->oo, the probability that a random n X n matrix over GF(q) has nullity k is 1/|GL_k(F_q)|*Product_{i>=k+1} (1 - 1/q^i). - Geoffrey Critzer, Dec 31 2024

Examples

			Triangle T(n,k) begins:
        1;
        1,        1;
        6,        9,       1;
      168,      294,      49,      1;
    20160,    37800,    7350,    225,   1;
  9999360, 19373760, 4036200, 144150, 961, 1;
  ...
		

Crossrefs

Cf. A060867 (T(n,n-1)), A002884 (column k=0), A086699 (column k=1), A346381, A286331.

Row sums give A002416.

Programs

Mathematica

nn = 5; b[p_, i_] := Count[p, i];d[p_, i_] := Sum[j b[p, j], {j, 1, i}] + i Sum[b[p, j], {j, i + 1, Total[p]}];aut[deg_, p_] :=Product[Product[q^(d[p, i] deg) - q^((d[p, i] - k) deg), {k, 1, b[p, i]}], {i, 1, Total[p]}]; \[Nu] = Table[1/n Sum[MoebiusMu[n/d] q^d, {d, Divisors[n]}], {n, 1, nn}]; L=Level[Table[IntegerPartitions[n], {n, 0, nn}], {2}]; g[u_, v_, deg_] :=  Total[Map[v^Length[#] u^(deg Total[#])/aut[deg, #] &, L]]; Map[Select[#, # > 0 &] &,  Table[Product[q^n - q^i, {i, 0, n - 1}], {n, 0,nn}] CoefficientList[Series[g[u, 1, 1] g[u, v, 1] Product[g[u, 1, deg]^\[Nu][[deg]], {deg, 2, nn}], {u, 0, nn}], {u,v}]] // Grid

Formula

T(n,k)=Product_{j=0..n-k-1} (2^n - 2^j)^2/(2^(n-k)-2^j). - Geoffrey Critzer, Dec 31 2024