We give a combinatorial method for proving elementary equivalence in first-
order logic FO with counting module n quantifiers D-n, inexpressibility res
ults for FO(D-n) with built-in linear order are also considered. For instan
ce, the class of linear orders of length divisible by n+1 cannot be express
ed in FO(D-n). Using this result we prove that comparing cardinalities or c
onnectivity of ordered graphs are not definable in FO(D-n). We also show th
at the height of complete n-ary trees cannot be expressed in FO(D-n) with l
inear order. Interpreting the predicate y = nx as a complete n-ary tree, we
show that the predicate y = pr cannot be defined in FO(D-n) with linear or
der, whenever p has a prime factor that does not divide n. This solves the
problem raised by Niwinski and Slolboushkin (LICS '93), We also discuss a c
onnection between our results and the well-known open problem in circuit co
mplexity theory, whether ACC = NC1. (C) 2000 Academic Press.