login
Number of n X n ternary matrices with no two adjacent 0's.
1

%I #45 Jan 09 2022 22:22:14

%S 1,3,56,7504,6832640,42780151808,1836366011301888,

%T 540795841280638713856,1092417949346109029345132544,

%U 15137179876232766647722798101823488,1438787206346713875314130065804001328234496,938091111277955250977701268973340995182098116509696

%N Number of n X n ternary matrices with no two adjacent 0's.

%C A two-dimensional generalization of A028859.

%C 2^(n^2) < a(n) < 3^(n^2).

%H Andrew Howroyd, <a href="/A350336/b350336.txt">Table of n, a(n) for n = 0..30</a>

%e a(1) is trivial because all 3 1 X 1 matrices have no 2 adjacent 0's, whereas for a(2) the 56 matrices are:

%e {

%e {{0, 1}, {1, 0}}, {{0, 1}, {1, 1}},

%e {{0, 1}, {1, 2}}, {{0, 1}, {2, 0}},

%e {{0, 1}, {2, 1}}, {{0, 1}, {2, 2}},

%e {{0, 2}, {1, 0}}, {{0, 2}, {1, 1}},

%e {{0, 2}, {1, 2}}, {{0, 2}, {2, 0}},

%e {{0, 2}, {2, 1}}, {{0, 2}, {2, 2}},

%e {{1, 0}, {0, 1}}, {{1, 0}, {0, 2}},

%e {{1, 0}, {1, 1}}, {{1, 0}, {1, 2}},

%e {{1, 0}, {2, 1}}, {{1, 0}, {2, 2}},

%e {{1, 1}, {0, 1}}, {{1, 1}, {0, 2}},

%e {{1, 1}, {1, 0}}, {{1, 1}, {1, 1}},

%e {{1, 1}, {1, 2}}, {{1, 1}, {2, 0}},

%e {{1, 1}, {2, 1}}, {{1, 1}, {2, 2}},

%e {{1, 2}, {0, 1}}, {{1, 2}, {0, 2}},

%e {{1, 2}, {1, 0}}, {{1, 2}, {1, 1}},

%e {{1, 2}, {1, 2}}, {{1, 2}, {2, 0}},

%e {{1, 2}, {2, 1}}, {{1, 2}, {2, 2}},

%e {{2, 0}, {0, 1}}, {{2, 0}, {0, 2}},

%e {{2, 0}, {1, 1}}, {{2, 0}, {1, 2}},

%e {{2, 0}, {2, 1}}, {{2, 0}, {2, 2}},

%e {{2, 1}, {0, 1}}, {{2, 1}, {0, 2}},

%e {{2, 1}, {1, 0}}, {{2, 1}, {1, 1}},

%e {{2, 1}, {1, 2}}, {{2, 1}, {2, 0}},

%e {{2, 1}, {2, 1}}, {{2, 1}, {2, 2}},

%e {{2, 2}, {0, 1}}, {{2, 2}, {0, 2}},

%e {{2, 2}, {1, 0}}, {{2, 2}, {1, 1}},

%e {{2, 2}, {1, 2}}, {{2, 2}, {2, 0}},

%e {{2, 2}, {2, 1}}, {{2, 2}, {2, 2}}

%e }

%t t[m_] := t[m] = Map[ArrayReshape[#, {m, m}] &, Tuples[{0, 1, 2}, m^2]];a[m_] := a[m] = Count[Table[AnyTrue[Flatten[{Table[Equal[0, t[m][[n, a, b]], t[m][[n, a, b + 1]]], {a, 1, m}, {b, 1, m - 1}], Table[Equal[0, t[m][[n, a, b]], t[m][[n, a + 1, b]]], {a, 1, m - 1}, {b, 1, m}]}], TrueQ], {n, 1, 3^(m^2)}], False]; Table[a[n], {n, 1, 3}]

%Y Cf. A006506 for binary version.

%Y Cf. A028859 for one-dimensional version.

%K nonn,hard

%O 0,2

%A _Robert P. P. McKone_, Jan 03 2022

%E Terms a(5)-a(11) from _Andrew Howroyd_, Jan 04 2022