Number of permutations with restrictions

I'm looking for a way (formula) to calculate the number of unique ways of setting integers which have to meet specific requirements.

Examples

We have a set of numbers $\{1, 2, 3\}$.
What is the total number of permutations, assuming that number $1$ can only be put in the first or second position and number $2$ only in the second or third position?

Position 1: $1$ or $3$
Position 2: $1$ or $2$ or $3$
Position 3: $2$ or $3$

Edit: I've already found way to solve the problem for example cases but I'm struggling with finding universal case formula.
In this case we have $1$ or $3$ at the first position.
For $1$, we have possibilities $123$ and $132$.
Putting $3$ as the first number implies only $312$.
It's overall $3$ possibilities.

We have a set of numbers $\{1, 2, 3, 4\}$.
What is the total number of permutations, assuming that the number $1$ can only be put in the first or second position and that the number $2$ can only be placed in the second or third position.

Position 1: $1$ or $3$ or $4$
Position 2: $1$ or $2$ or $3$ or $4$
Position 3: $2$ or $3$ or $4$
Position 4: $3$ or $4$

Edit: In this case I've started with the 4th position which can be either $3$ or $4$. We have $3$ possibilities for each of these numbers as in previous example. It's overall 6 possibilities.

Generally

We have a set of numbers $\{1, 2, \ldots, n\}$.
What is the total number of permutations where $k$ numbers have to be put either in the $p$th or $(p+1)$st position (where $1 \leq p \leq n-1$, different $p$ for each of $k$ numbers). And $s$ numbers can be put anywhere.

Edit: I still have no idea how to generalize whole problem. I'd start from putting $s \cdot$ (ways of placing restricted numbers)

Solution 1:

We start with a simple question: what is the total number of permutations on $[k]=\{1,2,3,\dots, k\}$ such that $i$ is in position $i$ or $i+1$ for all $i<k$.

We have $k$ possibilities:

\begin{align*} \begin{matrix} 1&2&3&\dots&k-2&k-1&k\\ 1&2&3&\dots&k-2&k&k-1\\ 1&2&3&\dots&k&k-2&k-1\\ 1&2&3&\dots&k-3&k-2&k-1\\ &&&&\vdots\\ 1&2&k&\dots&k-3&k-2&k-1\\ 1&k&2&\dots&k-3&k-2&k-1\\ k&1&2&\dots&k-3&k-2&k-1\\ \end{matrix} \end{align*}

A more general problem: What is the total number of permutations on $[k]=\{1,2,3,\dots,k\}$ such that $i$ is in position $p_i$ or $p_i+1$ for all $i<k$, where $p_i=p_j$ iff $i=j$.

This is identical to the previous question; there are $k$ possibilities, since we are, in essence, just changing the labeling of the numbers.

The general problem: Let $[n]=\{1,2,3,\dots,n\}$, and let $S\subseteq [n-1]$. What is the total number of permutations on $[n]$ such that for each $i\in S$, $i$ is in position $p_i$ or $p_i+1$, where $p_i=p_j$ iff $i=j$.

Let $\{s_1, s_2, \dots, s_k\}\subset S$, and without loss of generality, suppose $p_{s_i}<p_{s_j}$ for all $i<j$. We will call this subset maximal if it satisfies the following conditions:

• $p_{s_i}=p_{s_1}+i-1$
• If $s\in S\backslash \{s_1, s_2, \dots, s_k\}$, then $p_{s_1}\neq p_s+1$ and $p_s\neq p_{s_k}+1$

Since a maximal subset can be in $k$ of $k+1$ spots in a permutation of $[n]$, there are $k+1$ different possible ways for $\{s_1, s_2, \dots, s_k\}$ permute in $[n]$.

Therefore, we can partition $S$ into disjoint subsets: $S=S_1\cup S_2\cup\dots\cup S_r$, where each $S_i$ is maximal. So, the number of permutations on $[n]$ that satisfy our condition is

$$[(|S_1|+1)(|S_2|+1)\dots(|S_r|+1)]\cdot(n-|S|)!$$

The final factorial comes from the elements that were not in $S$ that are allowed to go anywhere.

Let's see this in action. For your second example, we have $n=4$, $S=\{1,2\}$, $p_1=1$ and $p_2=2$. Therefore, the only maximal subset of $S$ is $S$ itself. Hence, the number of permutations is

$$(|S|+1)\cdot(n-|S|)! = 3\cdot 2!=6.$$

As another example, suppose we were working with $\{1,2,3,4,5,6\}$, and we want

• $2$ to be in position $3$ or $4$,
• $4$ to be in position $4$ or $5$,
• $5$ to be in position $1$ or $2$.

We have $n=6$, $S=\{2,4,5\}$, $p_2=3$, $p_4=4$, and $p_5=1$. So the maximal subsets of $S$ are $S_1=\{2,4\}$ and $S_2=\{5\}$. Therefore, the number of permutations is

$$(|S_1|+1)(|S_2|+1)\cdot(n-|S|)! = 3\cdot2\cdot3!=36.$$