Thread: special set of permutations

Hi,
I define a subset of permutations as a subset where there is no more then 1 element the same on the same place
For example a permutation of 4 elements
1 2 3 4
1 3 4 2
1 4 2 3
2 1 4 3
2 3 1 4
..
there are 12 of them (I think)

For a permutation of 6 elements
2 4 3 6 5 2
2 5 6 1 2 3
2 6 5 2 1 4
3 1 3 5 2 4
3 2 4 6 1 3
.....
maybe 24 of them?

My questions are :
1) can be calculated how many there are for n elements
2) how can the set be constructed?
Thanks for any response

there are n! permutations of a set with n elements.

to see this, note we can freely choose which element is in "the first place" (n choices).

having done this, we can only choose from the n-1 elements remaining for the "second place" (n -1 choices).

after we have chosen which 2 elements go in the first two places, we have n-2 elements remaining to choose to "put in the third place".

so, in all, we have n(n-1)(n-2)....(3)(2) = n! ways to do this.

explicitly, here are the 24 = 4! = 4*3*2 ways to permute 4 elements:

1234
1243
1324
1342
1423
1432

2134
2143
2314
2341
2413
2431

3124
3142
3214
3241
3412
3421

4123
4132
4213
4231
4312
4321

note how i sub-divided these into 4 blocks. each block represents one of the 4 choices for the first position. the first 2 entries in each block represent the lowest number remaining of the remaining 3 as my second choice, and the second 2 entries in each block are the "next lowest choice for the second entry", and the final pair is the last of the (4-1 = 3) choices for the second element in the list.

i further listed the ordering of the final two positions in each pair of each block with i < j first, and i > j second (where "i" is what goes in "3rd place" and "j" is what goes in "4th place"). note that by the time we have chosen 3 positions, the 4th position is already determined (it's the only element left). i could do this for all permutations of 5 elements, but it would be too long to post here (there are 120 such permutations). the list would begin like so:

12345
12354
12435
12453
12534
12543

13245
13254... and so on

Originally Posted by andrews

Hi,
I define a subset of permutations as a subset where there is no more then 1 element the same on the same place
For example a permutation of 4 elements
1 2 3 4
1 3 4 2
1 4 2 3
2 1 4 3
2 3 1 4
..
there are 12 of them (I think)

I am not sure that I understand your example.
There are 17 permutations of four which have no more than 1 fixed element.
There are 9 permutations of four which have no fixed element. (the are call derangements)
There are 8 permutations of four which have exactly one fixed element.

Please reply and help me umderstand.

i inferred from his listing, which included 1234 which fixes 4 elements, that the OP is not speaking of derangements, or permutations which fix any given number (1 or 2, since if a permutation fixes 3, it fixes all) of elements.

Originally Posted by Deveno

i inferred from his listing, which included 1234 which fixes 4 elements, that the OP is not speaking of derangements, or permutations which fix any given number (1 or 2, since if a permutation fixes 3, it fixes all) of elements.

But the OP wrote there is no more then 1 element the same on the same place.

lol, you don't need to shout. i understand you want them to clarify. it's all good ^^.

Hi,
I will clarify my question because there is some misunderstanding.
f.e
1234
2341
1423
is a good set
and
1234
1243
1342
2413
is not a good set but
1234
1342
2413
is a good set because we have to delete 1243 because 1243 and 1234 have two same elements on the same place 1)element 1 on first place 2)elenment 2 on second place

Hello, andrews!

I define a subset of permutations as a subset
where there is no more then 1 element the same on the same place.
Very sloppy description, but I thought I understood it.

For example a permutation of 4 elements:

1 2 3 4 .← This is not one of them!
1 3 4 2
1 4 2 3
2 1 4 3
2 3 1 4
. . .
there are 12 of them (I think)


For a permutation of 6 elements
2 4 3 6 5 2 . two 2's ?
2 5 6 1 2 3
2 6 5 2 1 4
3 1 3 5 2 4 . two 3's ?
3 2 4 6 1 3
.....

Now I'm not sure of your definition.


My questions are :
1) can be calculated how many there are for n elements?
2) how can the set be constructed?

Let me illustrate my interpretation of this problem.

There are four cards, labelled 1, 2, 3, 4.
They are shuffled and dealt face up one at a time.
As we deal the cards, we recite "One, two, three, four."

If we happen to say the number of the card we just dealt,
. . we have a match.

In how many ways can we have at most one match?
(This means: no matches or exactly one match.)


There are 9 permutations have no matches:

. .


There are 8 permutations with exactly one match:

. .


Therefore, with 4 elements, there are:
. . permutations with at most one match.


~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~


For objects, a derangment is a permutation of the objects
. . in which none of the objects is in its original position.

The derangement formula is quite complex,
. . but I'll give you the first few values.

. .


The formula you seek is: .

Originally Posted by Soroban

The formula you seek is: .
[/size]

Hi Soroban. You and I agree 100% on what the OP means. However it is wrong.
Read Andrews reply #7. He seems to be saying that good set of permutations is one that pair-wise agree on not more that one position. But I have no idea what-so-ever how he intends to group the "good permutations".

There are no good permutations, but good sets of permutations
And you have to join the set of no same elements and those with one same element folowing the definition .
Then there are no 17 permutations but at most 12 for 4 elements.
f.e.
ABCD
ACDB
ADBC
BADC
BCAD
BDCA
CABD
CBDA
CDAB
DACB
DBAC
DCBA
I think the formula is n(n-1) but I am not sure
The big question is how to construct such a maximum set (there must be many of them for n > N)