# special set of permutations

• Jun 22nd 2012, 12:14 PM
andrews
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
• Jun 22nd 2012, 12:32 PM
Deveno
Re: special set of permutations
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
• Jun 22nd 2012, 12:37 PM
Plato
Re: special set of permutations
Quote:

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.

• Jun 22nd 2012, 12:49 PM
Deveno
Re: special set of permutations
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.
• Jun 22nd 2012, 12:56 PM
Plato
Re: special set of permutations
Quote:

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.
• Jun 22nd 2012, 01:07 PM
Deveno
Re: special set of permutations
lol, you don't need to shout. i understand you want them to clarify. it's all good ^^.
• Jun 22nd 2012, 02:34 PM
andrews
Re: special set of permutations
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
• Jun 22nd 2012, 03:39 PM
Soroban
Re: special set of permutations
Hello, andrews!

Quote:

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:

. . $\begin{array}{ccc}2143 & 2341 & 2413 \\ 3142 & 3412 & 3421 \\ 4123 & 4312 & 4321 \end{array}$

There are 8 permutations with exactly one match:

. . $\begin{array}{cccc}{\color{red}1}342 & 3{\color{red}2}41 & 24{\color{red}3}1 & 312{\color{red}4} \\ {\color{red}1}423 & 4{\color{red}2}13 & 41{\color{red}3}2 & 231{\color{red}4} \end{array}$

Therefore, with 4 elements, there are:
. . $9 + 8 \:=\:17$ permutations with at most one match.

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

For $n$ objects, a derangment is a permutation of the $n$ 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.

. . $\begin{array}{cc}n & d(n) \\ \hline 2 & 1 \\ 3 & 2 \\ 4 & 9 \\ 5 & 44 \\ 6 & 265 \\ 7 & 1,\!854 \\ 8 & 14,\!833 \end{array}$

The formula you seek is: . $f(n) \;=\;d(n) + n\!\cdot\!d(n\!-\!1)$
• Jun 22nd 2012, 04:33 PM
Plato
Re: special set of permutations
Quote:

Originally Posted by Soroban
The formula you seek is: . $f(n) \;=\;d(n) + n\!\cdot\!d(n\!-\!1)$
[/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".
• Jun 22nd 2012, 09:25 PM
andrews
Re: special set of 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