Permutations and diagonal

  • Thread starter jostpuur
  • Start date
2,100
16
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:
2,100
16
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...
 

CompuChip

Science Advisor
Homework Helper
4,284
47
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.)
 

Related Threads for: Permutations and diagonal

  • Posted
Replies
1
Views
587
Replies
20
Views
1K
  • Posted
Replies
2
Views
2K
Replies
2
Views
485
Replies
7
Views
3K
  • Posted
Replies
4
Views
792
Replies
3
Views
1K
Replies
3
Views
5K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top