  We consider the task of weighted first-order model counting (WFOMC) used for
probabilistic inference in the area of statistical relational learning. Given a
formula $\phi$, domain size $n$ and a pair of weight functions, what is the
weighted sum of all models of $\phi$ over a domain of size $n$? It was shown
that computing WFOMC of any logical sentence with at most two logical variables
can be done in time polynomial in $n$. However, it was also shown that the task
is $\texttt{#}P_1$-complete once we add the third variable, which inspired the
search for extensions of the two-variable fragment that would still permit a
running time polynomial in $n$. One of such extension is the two-variable
fragment with counting quantifiers. In this paper, we prove that adding a
linear order axiom (which forces one of the predicates in $\phi$ to introduce a
linear ordering of the domain elements in each model of $\phi$) on top of the
counting quantifiers still permits a computation time polynomial in the domain
size. We present a new dynamic programming-based algorithm which can compute
WFOMC with linear order in time polynomial in $n$, thus proving our primary
claim.
