  A binary matrix satisfies the consecutive ones property (COP) if its columns
can be permuted such that the ones in each row of the resulting matrix are
consecutive. Equivalently, a family of sets F = {Q_1,..,Q_m}, where Q_i is
subset of R for some universe R, satisfies the COP if the symbols in R can be
permuted such that the elements of each set Q_i occur consecutively, as a
contiguous segment of the permutation of R's symbols. We consider the COP
version on multisets and prove that counting its solutions is difficult
(#P-complete). We prove completeness results also for counting the frontiers of
PQ-trees, which are typically used for testing the COP on sets, thus showing
that a polynomial algorithm is unlikely to exist when dealing with multisets.
We use a combinatorial approach based on parsimonious reductions from the
Hamiltonian path problem, showing that the decisional version of our problems
is therefore NP-complete.
