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?

$\endgroup$
5
  • 1
    $\begingroup$ So by "permutations" what you really mean is ordered $n$-tuples with all components integers between 1 and $n$, inclusive, with repetitions allowed? E.g., for $n=2$, we are talking about $X=\{{(1,1),(1,2),(2,1),(2,2)\}}$? $\endgroup$
    – Gerry Myerson
    Jun 12, 2012 at 12:59
  • $\begingroup$ Yes. And for $n=2$ $X$ is unique, obviously. $\endgroup$
    – sas
    Jun 12, 2012 at 13:03
  • $\begingroup$ The use of the word "permutation" here is highly misleading; I suggest that you change it. $\endgroup$
    – Gadi A
    Jun 12, 2012 at 14:26
  • $\begingroup$ Are you talking about a single fixed pair of $i$ and $j$, so that a member $\sigma$ of $Y$ is comple by the two numbers $\sigma(i)$ and $\sigma(j)$? $\endgroup$
    – Brian M. Scott
    Jun 12, 2012 at 22:23
  • $\begingroup$ 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$. $\endgroup$
    – sas
    Jun 13, 2012 at 11:15

2 Answers 2

Reset to default
1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ And what should I do for $n=8$? I have $11111111$ and $12345678$. I want to get other 6 elements where 1 is the first number. It should be smth like $$1.2.....$$ $$ 1..2....$$ $$ 1...2... $$ $$ 1....2..$$ $$ 1.....2.$$ $$ 1......2$$ How should I fill in the gaps? $\endgroup$
    – sas
    Jun 14, 2012 at 13:17
  • $\begingroup$ There is a field of 8 elements. Call it $F=\{{0,1,a,a^2,a^3,a^4,a^5,a^6\}}$. In this field, $1+a=a^3$, and that relation enables you (with a fair bit of work) to write out the addition table for the field. The vector space of ordered 8-tuples of elements of $F$ has a 2-dimensional subspace $V$ generated by $v=(1,1,1,1,1,1,1,1)$ and $w=(0,1,a,a^2,a^3,a^4,a^5,a^6)$; all the vectors $bv+cw$, $b$ and $c$ in $F$. The 64 elements of that vector space are the elements of $Y$. Just rename $0,1,a,a^2,a^3,a^4,a^5,a^6$ as $1,2,3,4,5,6,7,8$. $\endgroup$
    – Gerry Myerson
    Jun 14, 2012 at 23:32
  • $\begingroup$ There's more detail on the field of 8 elements at mathworld.wolfram.com/FiniteField.html and 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 math.stanford.edu/~simonr/math121hw7.pdf. $\endgroup$
    – Gerry Myerson
    Jun 14, 2012 at 23:37
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ No, OP is using "permutation" to mean any old map, not necessarily injective. See the comments on the question. $\endgroup$
    – Gerry Myerson
    Jun 13, 2012 at 5:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .