Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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)\}}$? –  Gerry Myerson Jun 12 '12 at 12:59
    
Yes. And for $n=2$ $X$ is unique, obviously. –  sas Jun 12 '12 at 13:03
    
The use of the word "permutation" here is highly misleading; I suggest that you change it. –  Gadi A Jun 12 '12 at 14:26
    
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)$? –  Brian M. Scott Jun 12 '12 at 22:23
    
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$. –  sas Jun 13 '12 at 11:15
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
    
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? –  sas Jun 14 '12 at 13:17
    
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$. –  Gerry Myerson Jun 14 '12 at 23:32
    
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. –  Gerry Myerson Jun 14 '12 at 23:37
add comment

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

share|improve this answer
    
No, OP is using "permutation" to mean any old map, not necessarily injective. See the comments on the question. –  Gerry Myerson Jun 13 '12 at 5:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.