Results 1 to 10 of 10

Math Help - special set of permutations

  1. #1
    Newbie
    Joined
    Jun 2012
    From
    belgium
    Posts
    4

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    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
    Last edited by Deveno; June 22nd 2012 at 01:37 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: special set of permutations

    Quote Originally Posted by andrews View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: special set of permutations

    Quote Originally Posted by Deveno View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: special set of permutations

    lol, you don't need to shout. i understand you want them to clarify. it's all good ^^.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jun 2012
    From
    belgium
    Posts
    4

    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,914
    Thanks
    779

    Re: special set of permutations

    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:

    . . \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)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: special set of permutations

    Quote Originally Posted by Soroban View Post
    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".
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jun 2012
    From
    belgium
    Posts
    4

    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)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Looking for special polynomials
    Posted in the Differential Geometry Forum
    Replies: 9
    Last Post: July 6th 2010, 09:48 AM
  2. Special Property?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 30th 2009, 01:03 PM
  3. Find a special set
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 4th 2008, 07:33 AM
  4. Special equation?
    Posted in the Calculus Forum
    Replies: 3
    Last Post: May 19th 2008, 04:50 PM
  5. special e
    Posted in the Calculus Forum
    Replies: 3
    Last Post: August 22nd 2007, 02:31 PM

Search Tags


/mathhelpforum @mathhelpforum