cp's OEIS Frontend

A265627 Number of n X n "primitive" binary matrices.

%I A265627 #19 Jul 25 2022 04:03:18
%S A265627 2,10,498,65040,33554370,68718945018,562949953421058,
%T A265627 18446744065119682560,2417851639229258080977408,
%U A265627 1267650600228227149696920981450,2658455991569831745807614120560685058,22300745198530623141526273539119741048774160
%N A265627 Number of n X n "primitive" binary matrices.
%C A265627 A rectangular matrix is "primitive" in this sense if it cannot be expressed as a "tiling" of a single smaller matrix repeated in both directions.
%C A265627 Thus, for example, the 2 X 2 matrix with both rows equal to [1,0] is not primitive, since it can "tiled" by a single row.
%C A265627 This is the 2-dimensional generalization of A027375.
%F A265627 A general formula for the number of m X n "primitive" matrices over an alphabet of size k is Sum_{d|m, e|n} k^{m*n/(d*e)}*mu(d)*mu(e), where mu is the Möbius function.
%e A265627 We see a(2) = 10 since there are 16 possible 2 X 2 binary matrices, two are excluded because all their entries are the same, and four more are excluded because they are [[1,0],[1,0]] or a transpose or a negation.
%p A265627 with(numtheory):
%p A265627 prim := proc(k,m,n) option remember;
%p A265627         dm := divisors(m);
%p A265627         dn := divisors(n);
%p A265627         s := 0;
%p A265627         for d1 in dm do
%p A265627                 for d2 in dn do
%p A265627                         s := s+(k^(m*n/(d1*d2)))*mobius(d1)*mobius(d2);
%p A265627                         od;
%p A265627                 od;
%p A265627         s;
%p A265627         end:
%p A265627 seq(prim(2,n,n), n=1..40);
%t A265627 prim[k_, m_, n_] := prim[k, m, n] = Module[{s = 0},
%t A265627 Do[Do[s = s + (k^(m*n/(d1*d2)))*MoebiusMu[d1]*MoebiusMu[d2],
%t A265627    {d1, Divisors[m]}], {d2, Divisors[n]}]; s];
%t A265627 a[n_] := prim[2, n, n]
%t A265627 Table[a[n], {n, 1, 12}] (* _Jean-François Alcover_, Jul 24 2022, after Maple code *)
%Y A265627 Cf. A027375.
%K A265627 nonn
%O A265627 1,1
%A A265627 _Jeffrey Shallit_, Dec 10 2015