|
%I #27 Nov 18 2023 08:08:53
%S 1,2,12,216,10143,1128450,279687570,149055294640
%N Number of n X n matrices with elements {0, 1} whose characteristic polynomial has coefficients in {-1,0,1}.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Faddeev-LeVerrier_algorithm">Faddeev-LeVerrier algorithm</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Intrinsic_function#C_and_C++">Intrinsic Function</a>
%e The a(2) = 12 2 X 2 matrices are:
%e [0 0] [0 0] [0 1] [0 1] [0 1] [1 1]
%e [0 0], [1 0], [0 0], [1 0], [1 1], [1 0],
%e along with
%e [0 0] [0 0] [0 1] [1 0] [1 0] [1 1]
%e [0 1], [1 1], [0 1], [0 0], [1 0], and [0 0].
%e These have characteristic polynomials of
%e x^2, x^2, x^2, x^2-1, x^2-x-1, x^2-x-1,
%e along with
%e x^2-x, x^2-x, x^2-x, x^2-x, x^2-x, and x^2-x respectively.
%t a[0] := 1;
%t a[n_] := Length[Select[
%t Tuples[{0, 1}, {n, n}],
%t Max[Abs[CoefficientList[CharacteristicPolynomial[#, x], x]]] == 1 &
%t ]]
%o (Python)
%o from itertools import product
%o from sympy import Matrix
%o def A367051(n): return sum(1 for p in product((0,1),repeat=n**2) if all(d==0 or d==-1 or d==1 for d in Matrix(n,n,p).charpoly().as_list())) if n else 1 # _Chai Wah Wu_, Nov 05 2023
%Y Cf. A272661, A367052.
%K nonn,hard,more
%O 0,2
%A _Peter Kagey_, Nov 03 2023
%E a(5)-a(6), using the Faddeev-LeVerrier algorithm, from _Martin Ehrenstein_, Nov 06 2023
%E a(7), using AVX2 Intrinsics, from _Martin Ehrenstein_, Nov 18 2023
|
