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.

| cite | improve this answer | |
  • $\begingroup$ 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?) $\endgroup$ – Bruno Joyal Sep 12 '18 at 16:41
  • $\begingroup$ @BrunoJoyal Fixed. $\endgroup$ – orlp Sep 12 '18 at 16:43
  • $\begingroup$ @orip Thanks :) $\endgroup$ – Bruno Joyal Sep 12 '18 at 16:45
  • $\begingroup$ @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$. $\endgroup$ – orlp Sep 12 '18 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.