1
$\begingroup$

Let $S=1234567$. How many permutations of $S$ are possible if a digit at index $i$ where $1\le i \le5$ can't equal the index?

For example the permutation $1532467$ is illegal because the digits at index $1$ and $3$ are also $1$ and $3$. This permutation is legal: $5472361$.

I realize this is a classic problem for inversions but it is complicated by the fact that there're no restrictions for the last two digits of the string.

Using inclusion/exclusion principle I was thinking something along these lines: $$ 7!-{5\choose 1}6!+{5\choose 2}5!-{5\choose 3}4!+{5\choose 4}3!+{5\choose 5}2! $$ where first we choose one digit out of five which equals its index and permute the rest of digits, then we choose two digits that equal their index and we permute the rest of the digits, etc.

But I'm not sure this is correct because I'm wondering if permutation of the first $5$ digits should be separate from permuting the last two digits.

$\endgroup$
2
$\begingroup$

The last posted plus is a minus, of course, the result is $$ 7! -{5\choose 1}6! +{5\choose 2}5! -{5\choose 3}4! +{5\choose 4}3! \color{red}{-}{5\choose 5}2!\ . $$

Let $S=S_7$ be the set of all permutations of the seven given simbols.

We use the sets $A_k=\{\ s\in S_7\ :\ s(k)\ne k\ \}$, $1\le k\le 5$.

We use theit complement sets $B_k=\complement A_k=\{\ s\in S_7\ :\ s(k)= k\ \}$, $1\le k\le 5$.

The problem wants the cardinality of $A_1\cap A_2\cap A_3\cap A_4\cap A_5$, the complement of it can be covered by the inclusion & exclusion principle... $$ \begin{aligned} & \operatorname{card}(A_1\cap A_2\cap A_3\cap A_4\cap A_5) \\ &\qquad= \operatorname{card}(S) - \operatorname{card}\complement(A_1\cap A_2\cap A_3\cap A_4\cap A_5) \\ &\qquad= 7! - \operatorname{card}(\complement A_1\cup \complement A_2\cup \complement A_3\cup \complement A_4\cup \complement A_5) \\ &\qquad= 7! - \operatorname{card}(B_1\cup B_2\cup B_3\cup B_4\cup B_5) \\ &\qquad= 7! - \sum_{1\le N\le 5} (-1)^{N-1}\sum_{I\text{ index with $N$ components }} \operatorname{card}\left(\bigcap_{i\in I}B_i\right) \text{ by inclusion/exclusion} \\ &\qquad= 7! - \sum_{1\le N\le 5} (-1)^{N-1}\sum_{I\text{ index with $N$ components }} (7-N)! \\ &\qquad= 7! - \sum_{1\le N\le 5} (-1)^{N-1}\binom 5N (7-N)! \\ &\qquad= \sum_{0\le N\le 5} (-1)^N\binom 5N (7-N)! \ . \end{aligned} $$

Computer check:

sage: sum( [ (-1)^k * binomial(5,k) * factorial(7-k) for k in [0..5] ] )
2428
sage: len([ s for s in SymmetricGroup(7) if prod([s(k)-k for k in [1..5]]) ])
2428
$\endgroup$
1
$\begingroup$

You could also approach this as an extended derangement, which for whimsy I'll call an estrangement.

We can find a recursive definition of the permutations in an estrangement $e(d,w)$ where $d$ are the "deranged" items - the ones that have a forbidden location - and $w$ are the wildcards. Then placing a wildcard item either falls one of the "free" locations - there are $w$ of these - or one of the $d$ restricted locations, which turns the corresponding deranged item into a wildcard.

Thus $e(d,w) = w\cdot e(d,w-1) + d\cdot e(d-1,w)$

Also $e(0,w) = w!$ of course and $e(d,0) = {}!d$, the derangements of $d$ which can also be found recursively with ${}!d = (d-1)(!(d-1)+{}!(d-2))$.

Then we can make the following table for $e(d,w)$:

\begin{array}{c|ccc} d \backslash w & 0 & 1 & 2 \\\hline 0 & 1 & 1 & 2 \\ 1 & 0 & 1 & 4 \\ 2 & 1 & 3 & 14 \\ 3 & 2 & 11 & 64 \\ 4 & 9 & 53 & 362 \\ 5 & 44 & 309 & 2428 \\ \end{array}

$\endgroup$
  • $\begingroup$ I would've never thought about using recursion here but this is really cool. Also it would have been quite hard for me to come up with the correct recurrence. $\endgroup$ – Yos Jun 13 '18 at 19:06

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.