# Permutations with a restriction

Let $n\geq 0$ be an integer and let $0 \leq j \leq n$, $0 \leq t \leq n$.

Let $S_n(j, t)$ be the set of all permutations $\sigma$ of $\{1, \dots, n\}$ with the property that $$\sigma(i) \leq j \quad \text{for} \quad i \leq t.$$

Is there a simple formula for the cardinality of $S_n(j, t)$?

Example If $t>j$ then $S_n(j,t)=0$ by the pigeonhole principle ($\{1, \dots, t\}$ cannot map injectively into $\{1, \dots, j\}$ ).

Example If $t=j$ then the datum of an element of $S_n(j, t)$ is equivalent to the datum of a permutation of $\{1, \dots, j\}$ and a permutation of its complement in $\{1, \dots, n\}$. Hence $\# S_n(j,j) = j!(n-j)!$.

What about the general case $t\leq j$?

This question arose in a multilinear albgera calculation.

Normally the number of permutations of $$\left\{1,2,\ldots,n\right\}$$ is $$n! = \prod_{k=1}^n k$$ by stating the first element has $$n$$ choices, the next $$n-1$$, etc.
Here we see that the first element has $$j$$ choices, the next $$j-1$$, etc, until $$j + 1 - t$$ after which the next element has no further restrictions so it has $$n - t$$ choices, then $$n - t - 1$$, etc, so we get $$\prod_{k=1}^t (j + 1 - k) \times \prod_{k=t+1}^n (n + 1-k)$$ as our answer.
• You're absolutely right, I think it's that simple! (I think the second product should start with $n-t$ rather than $n-t-1$, no?) – Bruno Joyal Sep 12 '18 at 16:41
• @BrunoJoyal The reason for the error is that as a programmer I often count starting from zero so I thought that the interval with boundary $\leq t$ contained $t + 1$ elements but I forgot that it started at $1$, rather than $0$. – orlp Sep 12 '18 at 16:48