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

2, 10, 498, 65040, 33554370, 68718945018, 562949953421058, 18446744065119682560, 2417851639229258080977408, 1267650600228227149696920981450, 2658455991569831745807614120560685058, 22300745198530623141526273539119741048774160

Offset

1,1

Comments

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.

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.

This is the 2-dimensional generalization of A027375.

Links

Table of n, a(n) for n=1..12.

Formula

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.

Example

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.

Maple

with(numtheory):
prim := proc(k, m, n) option remember;
        dm := divisors(m);
        dn := divisors(n);
        s := 0;
        for d1 in dm do
                for d2 in dn do
                        s := s+(k^(m*n/(d1*d2)))*mobius(d1)*mobius(d2);
                        od;
                od;
        s;
        end:
seq(prim(2, n, n), n=1..40);

Mathematica

prim[k_, m_, n_] := prim[k, m, n] = Module[{s = 0},
Do[Do[s = s + (k^(m*n/(d1*d2)))*MoebiusMu[d1]*MoebiusMu[d2],
   {d1, Divisors[m]}], {d2, Divisors[n]}]; s];
a[n_] := prim[2, n, n]
Table[a[n], {n, 1, 12}] (* Jean-François Alcover, Jul 24 2022, after Maple code *)

Crossrefs

Cf. A027375.

Sequence in context: A207140 A059723 A334286 * A112449 A011824 A064300

Adjacent sequences: A265624 A265625 A265626 * A265628 A265629 A265630

Keyword

nonn

Author

Jeffrey Shallit, Dec 10 2015

Status

approved