# of permutations satisfying special inequalties of each element0
A faster approach

It's possible to solve this in $O(\binom{n}{t} \cdot n)$ operations, i.e., at most $O(n^{t+1})$ operations.  This is faster than the algorithm you describe in your question by about a factor of $t!$, but probably still not fast enough to be feasible for your parameters.

The idea is to enumerate all possible subsets of $t$ elements.  We'll try all possible choices for $S$, the set of elements that occur in positions $1,2,\dots,t$ (without regard to what order they appear in).  There are $\binom{n}{t}$ such choices for $S$.

For each choice of $S$, we separately (i) count the number of ways to order the elements of $S$ so that the first $t$ elements satisfy the first condition, and (ii) count the number of ways to order the elements of $\{1,2,\dots,n\}\setminus S$ so that the last $n-t$ elements satisfy the second condition.  Then, we multiply these two counts.

Each of those counts can be computed efficiently.  For instance, to compute count (i), we compute

$$g(t) \times (g(t-1)-1) \times (g(t-2)-2) \times \dots \times (g(1)-(t-1)),$$

where $g(i) = |S \cap \{1,2,\dots,f(i)\}|$ counts the number of elements of $S$ that could potentially be used at position $i$ without violating the first condition (i.e., the number of elements of $S$ that are $\le f(i)$).  Similarly, to compute count (ii), we compute

$$h(t+1) \times (h(t+2)-1) \times (h(t+3)-2) \times \dots \times (h(n)-(n-t+1)),$$

where $h(i) = |\overline{S} \cap \{f(i),\dots,n\}|$.

These two counts can be computed using $O(n)$ operations, leading to the claimed running time.

A further optimization

You can further optimize this, by splitting $S$ into two parts.  Decompose $S$ into

$$S = S_1 \cup S_2,$$

where $S_1 \cap S_2 = \emptyset$, by defining

$$\begin{align*}
S_1 &amp;= S \cap \{f(t+1),f(t+1)+1,\dots,n-1,n\}\\
S_2 &amp;= S \cap \{1,2,3,\dots,f(t+1)-1\}.
\end{align*}$$

Now notice that to count (ii), we don't actually need to know both $S_1$ and $S_2$: it's enough to know $|S_1|$ and $S_2$: the exact elements in $S_1$ don't change the count (by a relabelling argument), since they're all $\ge f(j)$ for all $j&gt;t$.

Furthermore, since $|S|=t$ and $|S|=|S_1|+|S_2|$, it suffices to know $S_2$.  Once we know $S_2$, we can compute $|S_1|=t-|S_2|$ and then compute count (ii).

Similarly, once we know $S_2$, we can also compute count (i).

So, we're going to enumerate all possible values for $S_2$, i.e., all subsets of $\{1,2,3,\dots,f(t+1)-1\}$ of size $\le t$.  There are

$$Q = \binom{f(t+1)-1}{t} + \dots + \binom{f(t+1)-1}{1} + \binom{f(t+1)-1}{0}$$

possible choices for $S_2$.  Then we obtain an algorithm whose running time is $O(Q \cdot n)$.  The exact value of $Q$ depends on $f(t+1)$, but we have $Q = O(f(t+1)^t)$.

In this way we obtain an algorithm whose running time is $O(f(t+1)^t \cdot n)$.  For many choices of $f$, this will be even faster than the basic approach sketched at the beginning of this answer.

Also, it's easy to see that we must have $f(t+1) \ge n-t+1$ (otherwise the count is 0).  It follows that there is an algorithm whose worst-case running time is $O((n-t)^t \cdot n)$, regardless of $f$.