1
$\begingroup$

Let $X$ be a set of permutations with repetitions of numbers from $1$ to $n$

Let $Y \subseteq X$ be unique if for all $\sigma, \pi \in Y$, $1 \leqslant i < j \leqslant n$ the fact that $\pi(i) = \sigma(i)$ and $\pi(j) = \sigma(j)$ implies $\pi = \sigma$.

The question is what is the maximum number of elements in $Y$ and more interesting how we can get $Y$? What is the algorithm?

  • 0
    No. Every $\sigma$ is a set of $n$ numbers. Every number is an integer from 1 to $n$. And there should be no similar pairs in different $\sigma$ and $\pi$.2012-06-13

2 Answers 2

1

It's easy to see that $Y$ has at most $n^2$ elements. If you have more than $n^2$ ordered $n$-tuples, then by the pigeonhole principle two of them share the same first two components.

Whether you can always achieve $n^2$ is not clear to me. I suspect I'm overlooking some simple construction. Anyway, for $n=2$ as you note we can achieve 4. For $n=3$ there are lots of ways of achieving 9: $\{{123,132,213,231,312,321,111,222,333\}}$ is one way, another is $\{{112,121,211,223,232,322,331,313,133\}}$ and another is $\{{111,122,133,212,223,231,313,321,332\}}$

EDIT: here's a solution for $n=4$: $\matrix{1111&1234&1342&1423\cr2222&2143&2431&2314\cr3333&3412&3124&3241\cr4444&4321&4213&4132\cr}$ I found this by using the field of 4 elements, $F=\{{0,1,\alpha,\beta\}}$, and taking the two-dimensional subspace of $F^4$ spanned by $(1,1,1,1)$ and $(0,1,\alpha,\beta)$, and then renaming the elements of $F$, 1, 2, 3, 4. This ought to work if $n$ is the order of a finite field, that is, if $n$ is a prime power. But maybe there's a simple construction I'm not seeing that works for all $n$.

  • 0
    There's more detail on the $f$ield of 8 eleme$n$ts at http://mathworld.wol$f$ram.com/FiniteField.html and https://wiki.sch.bme.hu/pub/Infoalap/KodTech/field.pdf (which gives an addition table, but you have to work out the multiplication) and maybe the most useful is 13.1.3 at http://math.stanford.edu/~simonr/math121hw7.pdf.2012-06-14
0

for any two permutation $\sigma, \pi $ and for any $i_0 \in \{1...n\}$

if $\forall i \in \{1...n\}-\{i_0\}: \pi(i) = \sigma(i) $ then $\pi = \sigma$

we just have to prouve that $\pi(i_0) = \sigma(i_0)$

if $\pi(i_0) \neq \sigma(i_0)$

let $j = \pi(i_0)$

and let $i_1 $ be such that $\sigma(i_1)=j$

$i_1 \neq i_0$ because of $\sigma(i_1)=\pi(i_0) \neq \sigma(i_0)$

since $i_1 \neq i_0$ so we have $\sigma(i_1)=\pi(i_1)$

so we found the contradiction $\pi(i_0)=\pi(i_1)$ because $\pi$ is injective

i hope that this helps

  • 0
    No, OP is using "permutation" to mean any old map, not necessarily injective. See the comments on the question.2012-06-13