Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutations and diagonal

  1. Feb 10, 2008 #1
    For fixed [itex]n\in\mathbb{N}[/itex], how many permutations [itex]X\in S_n[/itex] there exists, so that [itex]X(t)=t[/itex] at least for some [itex]t\in\{1,2,3,\ldots,n\}[/itex]?

    Is the solution to this well known? I couldn't solve it by the most direct approach that seemed to be the only apparent way. This is how far I got:

    Question 1: How many ways is there to choose X so that X(1)=1? The answer is clearly (n-1)!.

    Remark: It would not make sense to next ask that how many ways is there to choose X so that X(2)=2, because some of these X have already been counted.

    Question 2: How many ways is there to choose X so that X(1)!=1 and X(2)=2? The X(1) must be different from 1 and 2, so it can be chosen in n-2 different ways. Remaining values X(3),...,X(n) can be chosen in (n-2)! different ways, so the answer is (n-2)*(n-2)!.

    Question 3: How many ways is there to choose X so that X(1)!=1, X(2)!=2, and X(3)=3. The choice of X(1) has effect on how many ways the X(2) can be chosen. If we choose X(1)=2, then X(2) can be chosen in n-2 different ways. Remaining X(4),...,X(n) can be chosen in (n-3)! different ways. If we instead choose X(1)!=2, then X(1) can be chosen in n-2 different ways, X(2) can be chosen in n-3 different ways, and again remaining X(4),...,X(n) can be chosen in (n-3)! different ways. So the answer is ((n-2)+(n-2)*(n-3))*(n-3)!.

    Question 4: How many ways is there to choose X so that X(1)!=1, X(2)!=2, X(3)!=3 and X(4)=4? If we choose X(1)=2, then [if we choose X(2)=3, then blabla. If we instead choose X(2)!=3, then blabla]. If we choose X(1)=3, then blabla. If we choose X(1)!=2 and X(1)!=3, then blabla. ARGH! :frown:

    ...

    This doesn't seem to be giving the answer.
     
    Last edited: Feb 10, 2008
  2. jcsd
  3. Feb 10, 2008 #2
    Or did I post this too soon again. The answer to the question 4 seems to be 2*((n-2)+(n-2)*(n-3))*(n-4)!. Perhaps some pattern arises if one proceeds by force...
     
  4. Feb 10, 2008 #3

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Hint: the number of permutations that fixes at least one t plus the number of permutations that fixes none is the total number of permutations. Now try induction (how many are there for n = 2? If I now consider permutations of three elements, how many ways are there to make each of these into a permutation of all elements?)

    (Disclaimer: looked at this briefly, but cannot guarantee it will work. Maybe I missed something.)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Permutations and diagonal
  1. Diagonal of rectangle (Replies: 2)

  2. Diagonal Lines (Replies: 13)

Loading...