1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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




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

  2. Diagonal Lines (Replies: 13)

Loading...