  We study the counting problem known as #PPM, whose input is a pair of
permutations $\pi$ and $\tau$ (called pattern and text, respectively), and the
task is to find the number of subsequences of $\tau$ that have the same
relative order as $\pi$. A simple brute-force approach solves #PPM for a
pattern of length $k$ and a text of length $n$ in time $O(n^{k+1})$, while
Berendsohn, Kozma and Marx have recently shown that under the exponential time
hypothesis (ETH), it cannot be solved in time $f(k) n^{o(k/\log k)}$ for any
function $f$. In this paper, we consider the restriction of #PPM, known as
$\mathcal{C}$-Pattern #PPM, where the pattern $\pi$ must belong to a hereditary
permutation class $\mathcal{C}$. Our goal is to identify the structural
properties of $\mathcal{C}$ that determine the complexity of
$\mathcal{C}$-Pattern #PPM.
  We focus on two such structural properties, known as the long path property
(LPP) and the deep tree property (DTP). Assuming ETH, we obtain these results:
  1. If $C$ has the LPP, then $\mathcal{C}$-Pattern #PPM cannot be solved in
time $f(k)n^{o(\sqrt{k})}$ for any function $f$, and
  2. if $C$ has the DTP, then $\mathcal{C}$-Pattern #PPM cannot be solved in
time $f(k)n^{o(k/\log^2 k)}$ for any function $f$.
  Furthermore, when $\mathcal{C}$ is one of the so-called monotone grid
classes, we show that if $\mathcal{C}$ has the LPP but not the DTP, then
$\mathcal{C}$-Pattern #PPM can be solved in time $f(k)n^{O(\sqrt k)}$. In
particular, the lower bounds above are tight up to the polylog terms in the
exponents.
