Giovanni Battaglia, Roberto Grossi and Noemi Scutellà

**Abstract.** A binary matrix satisfies the *consecutive ones property* (C1P) if its columns can be permuted such that the 1s in each row of the resulting matrix are consecutive. Equivalently, a family of sets *F* = {*Q*_{1}, …, *Q _{m}*}, where

*Q*⊆

_{i}*R*for some universe

*R*, satisfies the C1P if the symbols in

*R*can be permuted such that the elements of each set

*Q*∈

_{i}*F*occur consecutively, as a contiguous segment of the permutation of R’s symbols. Motivated by combinatorial problems on sequences with repeated symbols, we consider the C1P version on

*multisets*and prove that counting the orderings (permutations) thus generated is #P-complete. We prove completeness results also for counting the permuta tions generated by PQ-trees (which are related to the C1P), thus showing that a polynomial-time algorithm is unlikely to exist when dealing with multisets and sequences with repeated symbols.