Many plants (think of flowers and fruit) and simple animals (think of starfish, jellyfish and anemones) exhibit 3-, 5- or 6-fold symmetry, and often higher. Flowers have been "making useful use of automorphisms of order three" for ages. Jellyfish, possibly the most successful animal to ever exist on the planet, have such striking and high order radial symmetry that they are the biologist's go-to example for demonstrating this phenomenon in nature.

To get your formula for $M(n,2,2)$ via inclusion-exclusion, stack $n$ levels of $2 \times 2$ matrices, then use $M(2,2)=7$ to overcount the number of ways to fill each level. This includes $4 \cdot 2^n$ cases where one of the four $n$-lines is all $0$s, and that overcounts the $2$ cases when two lines are all $0$s. The same inclusion/exclusion idea gives $M(n,3,2) = 25^n -6(8^n+3^n) +6(3\cdot2^n +1)$, and the asymptotics $M(m,n,p) \sim M(m,n)^p$.

Yes, and it seems to me to be much easier when all of your polynomials $P_i$ are homogeneous. I'll add it to the answer, because there is a bit of enumeration and subscripts don't look so nice in comments.

A typo in the code, $t+1/2$ instead of $t/2+1$, made the last function give the wrong values. It's now corrected, and agrees with "the number of maximal balanced binary trees" from your paper in Theoretical Computer Science (Feb. 2012, 420).

Perhaps those 120 people also had not heard of this "standard" term. I would suggest that if you use it, you include the definition, otherwise your reader might grow tired of looking for the term, just like you did. Searching for exhaustion sets brings up as many references to weightlifting as it does to set theory.

@François: Is any version of gomoku on a hexagonal board known to be a first player win? The Erdős-Selfridge result says it is with those two advantages on a large enough board, but is it true without those?

Why not do this by induction on $s$? It's true if every entry is $1$, and if they are not all $1$, then you can find a set of $n$ entries, one from each row and column, which are all greater than $1$ (consider the labels of Latin squares and use pigeonhole principle). Assign the same single element to each of those, and you've reduced $s$ by $1$.

There are still quite a lot besides those. For example, take $x=2$, and any $z$. Then the equation simplifies to $n_z((y-1)^2 -1)=q^2$, which is Pell's equation if $n_z$ is not a square. Choose $z$ so that $6(z^2-z)$ is not a square (another Pell equation, but this time we want non-solutions) and you'll get infinitely many more solutions. I think the same tricks will work with any $x$ value: complete squares, get a Pell-type equation for $z$ in terms of $x$ and choose a non-solution $n_z$, then write the Pell equation for $y$ in terms of that, and solve.

@joro: No, I mean that the squares 9 and 49 do not divide it. Since it can be factored as a Fibonacci number times a Lucas number, and 3 and 7 both divide it, and 3 and 7 so not divide the Lucas number, then both of their squares (i.e. 9 or 49) must divide the Fibonacci part for it to be a square. I've edited now to clarify.

This sort of appendix seems contrary to the nature of mathematics. The argument isn't countered by providing a list of other ideas that people might have said were useless. Instead, why not focus on the education aspects? According to the Wikipedia article, the search has led a few computer programmers into what is ostensibly number theory, and may have introduced many young people to a fundamental idea behind proofs - even if you haven't found a palindrome by $10^9, there might still be one. Sounds a lot like Skewes' number, also probably called useless.

@David: This is even weaker than partial sorting, since we don't need to know the exact rank of elements $1$ to $m$, just the set of elements in those positions.

@Mariano: Can we call the practice of rebranding those processes Suárez-Alvarezization?