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

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

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.

Please reply and help me umderstand.

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.

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

Re: special set of permutations

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

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

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:

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

There are 8 permutations with exactly one match:

. . $\displaystyle \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:

. . $\displaystyle 9 + 8 \:=\:17$ permutations with at most one match.

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

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

. . $\displaystyle \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: .$\displaystyle f(n) \;=\;d(n) + n\!\cdot\!d(n\!-\!1)$

Re: special set of permutations

Quote:

Originally Posted by

**Soroban** The formula you seek is: .$\displaystyle 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".

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

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)