  The FO Model Counting problem (FOMC) is the following: given a sentence
$\Phi$ in FO and a number $n$, compute the number of models of $\Phi$ over a
domain of size $n$; the Weighted variant (WFOMC) generalizes the problem by
associating a weight to each tuple and defining the weight of a model to be the
product of weights of its tuples. In this paper we study the complexity of the
symmetric WFOMC, where all tuples of a given relation have the same weight. Our
motivation comes from an important application, inference in Knowledge Bases
with soft constraints, like Markov Logic Networks, but the problem is also of
independent theoretical interest. We study both the data complexity, and the
combined complexity of FOMC and WFOMC. For the data complexity we prove the
existence of an FO$^{3}$ formula for which FOMC is #P$_1$-complete, and the
existence of a Conjunctive Query for which WFOMC is #P$_1$-complete. We also
prove that all $\gamma$-acyclic queries have polynomial time data complexity.
For the combined complexity, we prove that, for every fragment FO$^{k}$, $k\geq
2$, the combined complexity of FOMC (or WFOMC) is #P-complete.
