# How many permutations of n elements exist, such that for each pair of permutations, they are still distinct after removing any element?

Question: How many permutations of $$n$$ elements exist, such that for each pair of permutations, they are still distinct after removing any element?

To elaborate on what I mean by removing any element, consider the permutations on $$\{1,\dots,5\}$$:

• $$12345$$ and $$54321$$ are distinct no matter which element is removed: $$1234$$ and $$4321$$ are distinct, $$1235$$ and $$5321$$ are distinct and so on and so forth.

• If you consider $$12345$$ and $$12453$$ however this is not the case, as by removing 3 both permutations turn into $$1245$$.

I am looking for a general formula to describe the maximum number of distinct permutations that satisfy this condition (pairwise) for a set of $$n$$ elements. I conjecture that this number is $$(n-1)!$$ for $$n\ge 2$$, but I am struggling with proving it. An approach to solving this would already be greatly appreciated.

$$(n-1)!$$ is an upper bound for the size of this set, as after removing a fixed element from all permutations, $$n-1$$ elements are left and there can be at most $$(n-1)!$$ different permutations of these elements.

For $$n=2,\dots,6$$ I have computed solutions of size $$(n-1)!$$. I showcase the case $$n=2,3,4$$ below:

• Case $$n=2$$: As $$(2-1)!=1$$, the sets containing a single permutation ($$\{12\}$$ and $$\{21\}$$) satisfy the above condition.

• Case $$n=3$$: Here $$(3-1)!=2$$. The set $$\{321,123\}$$ fulfills the property.

• Case $$n=4$$: Here $$(4-1)!=6$$. The set $$\{1234, 4132, 2143, 4231, 3142, 3241\}$$ satisfies the property, as no matter which element is removed the permutations still differ from each other. E.g., after removing $$1$$ the set becomes $$\{234,432,243,423,342,324\}$$.

• It may be useful to construct a graph as follows: include a vertex for each permutation of $1,2,3, \dots , n$, and draw an edge between two vertices if the permutations fail the desired property: if it is possible to remove an element $k$ from both permutations so that the results are equal. Then your problem is the maximum independent set problem on this graph, which has some nice properties like being symmetric and regular. Commented Jul 3 at 13:25
• There are at most $(n-1)!$ because when you remove one element you can have at most that many permutations of what is left. I believe a construction that can be made to work is to start with the permutations of $[n-1]$ and put $n$ next to $1$ so that the permutation is even. I haven't found a rule for which end to put $n$ on when $1$ is on the end. Your $n=4$ case works this way. Commented Jul 15 at 15:13
• Your last sentence makes me want to clarify: am I correct that we want the resulting permutations to be different even after removing any number from any pair of permutations? We're not restricted to removing the same number from all the permutations simultaneously? Commented Jul 15 at 16:21
• @Cid, could you share your solution for $n =6$? Commented Jul 17 at 15:56
• Via integer linear programming, I have confirmed the conjecture for $n \le 6$ and found a set of $716$ permutations for $n=7$ but have not ruled out $720$. Commented Jul 17 at 16:01

## 4 Answers

As mentioned in a comment, one approach is to solve a maximum independent set problem in a graph with a node for each permutation $$p\in P$$ and an edge $$(p,q)\in E$$ for each pair of permutations that become identical after removing some $$k$$ (denote this as $$p \setminus k = q \setminus k$$). You can solve such a problem via integer linear programming by introducing a binary decision variable $$x_p$$ for each permutation $$p$$ and maximizing $$\sum_{p\in P} x_p$$ subject to linear "conflict" constraints $$x_p + x_q \le 1 \quad \text{for all (p,q)\in E}. \tag1\label1$$

A stronger formulation is to replace \eqref{1} with "clique" constraints $$\sum_{q\in P: p \setminus k = q \setminus k} x_q \le 1 \quad \text{for all p\in P and k\in \{1,\dots,n\}}. \tag2\label2$$

For $$n \le 6$$, the maximum indeed turns out to be $$(n-1)!$$. For $$n=7$$, I found a feasible solution with objective value $$716$$ but have not ruled out $$720$$.

Here's one optimal solution for $$n=6$$ (with elements $$\{0,\dots,5\}$$ instead of $$\{1,\dots,6\}$$):

013524
014253
021345
021543
023541
024315
024513
031254
031452
034251
041325
041523
043521
051243
051342
052314
053241
054213
054312
102534
103245
103542
104235
104532
120543
123045
123540
124035
124530
132504
134025
134520
140523
143205
143502
150243
152034
153042
153240
154032
154230
201435
201534
203415
203514
204531
213054
214503
231405
231504
234501
241053
241350
243051
250413
251034
251430
253014
253410
254031
301245
301542
302514
304215
304512
310524
314250
320541
321045
321540
324015
324510
340521
341205
341502
350241
351042
351240
352014
354012
354210
401235
401532
402531
403215
403512
412503
413052
420513
421035
421530
423015
423510
431025
431520
432501
450213
451032
451230
452031
453012
453210
501234
501432
503214
503412
504231
513024
514203
521043
521340
523041
524013
524310
531204
531402
534201
541023
541320
543021


We can achieve $$\tfrac{n!}{(n-1)^2+1}$$.

Each permutation that we put in the set eliminates $$(n-1)^2$$ other permutations from consideration. (Proof: We can choose any of the numbers $$1$$ through $$n$$ and slide it to any of $$n-1$$ positions besides its original position. This seems to be $$n(n-1)$$ options eliminated, but the $$n-1$$ cases where we swap two neighboring letters are counted twice, so $$n(n-1) - (n-1) = (n-1)^2$$.

Therefore, if we have put $$M$$ elements into our set so far, there are at mos $$(n-1)^2$$ permutations which we could not put into our set. So, if $$|M| < \tfrac{n!}{(n-1)^2+1}$$, then we can add some other permutation. Keeping going this way, we can put $$\tfrac{n!}{(n-1)^2+1}$$ permutations into our set.

• One way to improve this might be to consider how putting permutations that are "closer" together would result in fewer permutations being eliminated at each step, although the details were too tricky for me. Commented Jul 21 at 22:15
• It seems we can achieve a somewhat better bound, if we restrict our consideration to permutations of the same parity. Commented Jul 22 at 4:44

Here is a lower bound, although one which is much worse than $$(n-1)!$$: I can show that there are at least $$\tfrac{n!}{2^n-1}$$ such permutations. This is the best I can achieve constructively, although I can achieve $$\tfrac{n!}{(n-1)^2+1}$$ non-constructively (link).

It will be convenient to work with permutations of $$\{0,1,\ldots, n-1 \}$$, rather than permutations of $$\{1,2,\ldots, n \}$$.

Proof: Set $$M = 2^n-1$$. For $$w \in S_n$$, define $$\sigma(w) = \sum_{\substack{0 \leq i w(j)}} 2^{i+j} \bmod M.$$ I think of $$\sigma$$ as coloring the set of permutations with one of $$M$$ colors. I will show that, if $$u$$ and $$v$$ are permutations that differ only by moving one element, then $$\sigma(u) \neq \sigma(v)$$. By the pigeonhole principle, there must be some color which is used at least $$n!/M$$ times, so the permutations with that color form the desired set.

Okay, let $$u$$ and $$v$$ be permutations which differ only in the position of some letter, say $$q$$. Without loss of generality, let $$q$$ be further to the left in $$u$$ and further to the right in $$v$$, so there are some letters which are to the right of $$q$$ in $$u$$ and to the left of $$q$$ in $$v$$. Let $$X$$ be the set of those letters, and write $$X = P \sqcup R$$, where $$P = \{ p \in X : p and $$R = \{ r \in X : r>q \}$$.

For example, let $$u = 142\boldsymbol{5}6378$$ and $$v = 142637\boldsymbol{5}8$$. Then $$q = 5$$, $$P = \{ 3 \}$$ and $$R = \{ 6,7 \}$$.

So $$\sigma(v) - \sigma(u) = \sum_{r \in R} 2^{q+r} - \sum_{p \in P} 2^{p+q} = 2^q \left( \sum_{r \in R} 2^{r} - \sum_{p \in P} 2^{q} \right).$$ We need to show that this is not $$\equiv 0 \bmod M$$. Since $$M$$ is odd, we can ignore the factor of $$2^q$$, so it is enough to see that $$\sum_{r \in R} 2^{r}$$ and $$\sum_{p \in P} 2^{q}$$ are distinct modulo $$M$$.

Now, $$\sum_{r \in R} 2^{r}$$ is most $$2^1+2^2+\cdots+2^{n-1} = 2^n-2 and $$\sum_{p \in P} 2^{p}$$ is most $$2^0+2^1+\cdots+2^{n-2} = 2^{n-1}-1. (Note that $$0 \not\in R$$ and $$n-1 \not\in P$$.) So the only way that the sums are equal modulo $$M$$ is if they are equal as integers. But this can't happen, since they have distinct binary expansions. $$\square$$

Of course, my original strategy was to color $$S_n$$ with $$n$$ colors, but after trying a lot of things, I haven't been able to find a way to use fewer then $$2^n-1$$.

EDIT: It has been demonstrated through counterexample that the below approach cannot be generalized to a full proof (credit @ConnFus).

e.g. for $$n=4$$, this collection of permutations cannot be extended: $$\{1423,3124,4321,2341\}$$

PREVIOUS ANSWER: I propose a 'just do it' solution whereby we attempt to prove a slightly stronger result. Namely that not only can we find a set of permutations of size $$(n-1)!$$, but we can do so greedily. By which I mean that we can start by choosing an arbitrary permutation and keep adding permutations which preserve the required property (that for any pair, they are different upon removal of a single element).

I will just deal with a special case and leave it for the reader to extend to a full proof.

Let's introduce some notation.

Let $$\Pi$$ represent the set of permutations of $$\{ 1,2,...n\}$$
Let $$\Pi_k$$ represent the set of permutations of $$\{1,2,...n\} - \{k\}$$.
$$|\Pi| = n!$$, $$|\Pi_k| = (n-1)!$$

Let $$P \subset \Pi$$ be the collection of permutations we have chosen thus far.

Let $$f_k: \Pi \rightarrow \Pi_k$$ map an element of $$\Pi$$ to it's corresponding element in $$\Pi_k$$ through removal of $$k$$. From the question $$f_k$$, is injective $$\forall$$ $$k$$. I will use $$f_k(P)$$ to refer to $$\{\pi_k \in \Pi_k : \pi_k = f_k(p), p \in P\}$$

Now suppose $$|P| = (n-1)! - 1$$, we wish to show that it is possible to add another element to $$P$$ whilst preserving our required property that $$f_k$$ remains injective for all $$k$$. We will do this by supposing that no such extension of $$P$$ is possible and reaching a contradiction.

Notice that once $$|P| = (n-1)!, f_k$$ will in fact be a bijection.

Now of course, $$|P| = (n-1)! - 1$$ is just a special case. To extend to a full proof, I recommend instead considering a least counterexample.

Let's now consider $$f_k(P)$$.
$$f_k(P) \subset \Pi_k$$ and $$|f_k(P)| = (n-1)! - 1$$
Therefore, $$\Pi_k / f_k(P)$$ contains single element which we will denote as $$\pi^*_k$$

We want to show that all the $$\pi^*_k$$ can be stitched together into some $$\pi^* \in \Pi$$.

For $$x,y \in \{1,...n\}$$, we say that $$\pi_k(x \sim y)$$ if within the permutation $$\pi_k$$, $$x$$ precedes $$y$$.

Notice that $$\sim$$ is not an equivalence relation for $$x \sim y \implies y \nsim x$$. In fact, this makes it 'anti-symmetric'. It is also clearly transitive.

In order to stitch the $$\pi^*_k$$ together, we require $$\forall$$ $$k, l, x,y$$ $$[\pi^*_k(x \sim y) \implies \pi^*_l(x \sim y)]$$
(given $$x,y \neq k,l$$). And if this condition holds, then it is easy to construct $$\pi^*$$.

This is where we now attempt to find a contradiction. Suppose that it is not possible to extend $$P$$.
Then $$\exists$$ $$i,j,a,b$$ with $$i,j \neq a,b : \pi^*_i(a \sim b) \wedge \pi^*_j(a \nsim b)$$.

Since $$\Pi_i / f_i(P) = \{\pi^*_i\}$$, $$\forall$$ $$\pi_i \in \Pi_i, \pi_i(b \sim a) \implies \pi_i \in f_i(P)$$

By applying $$f_j \circ f^{-1}_i$$, it follows that $$\forall$$ $$\pi_j \in \Pi_j, \pi_j(b \sim a) \implies \pi_j \in f_j(P)$$.

Recalling the definition of $$\pi^*_j$$,
$$\pi^*_j \in \Pi_j$$ and $$\pi^*_j(a \nsim b) \implies \pi^*_j(b \sim a)$$. Therefore $$\pi^*_j \in f_j(P)$$.

But by definition, $$\pi^*_j \notin f_j(P)$$, a contradiction.

• Why can't we have another permutation $π_i'\in\Pi_i$ for which also holds $π_i'(a∼b)$? Commented Jul 16 at 16:03
• some of my notation choices may not have been best. $\pi_i$ is the single element in $\Pi_i / f_i(P)$. $\Pi_i$ does in fact contain many such $\pi$ with $\pi( a \sim b$) Commented Jul 16 at 16:07
• I've changed the notation so that $\pi_i$ is now a general element of $\Pi_i$ and $\Pi_i/f_i(P) = \pi^*_i$ Commented Jul 16 at 16:31
• For future use, I'd also recommend using $a<_{\pi}b$ instead of $\pi(a\sim b)$. Because you have shown asymmetry and transitivity, you more or less already showed it's a partial order: en.wikipedia.org/wiki/Partially_ordered_set#Partial_orders Commented Jul 16 at 16:36
• Thanks, that's helpful! In fact it's the partial ordering which I utilize to 'stitch' the $\pi^*_k$ together. I think with all my subscripts and superscripts it could get messy here though e.g. $a \lt_{\pi^*_i} b$ Commented Jul 16 at 16:50