Probability question within a group of three males and three females. There are $3$ men and $3$ women, and all $6$ of them are different heights. If the women are randomly paired with the men to form $3$ couples, what is the probability that the shortest man is paired with the tallest woman, or the tallest man is paired with the shortest woman?
Attempted Solution:
So I'll denote the three men from shortest to tallest as {$1,2,3$} and the three women from shortest to tallest as {$4,5,6$}. I will arbitrarily choose the men to be ordered as {$1,2,3$}. Then using the inclusion-exclusion principle,
P($1$ with $6$) = $1\over3$
P($3$ with $4$) = $1\over3$
P($1$ with $6$ $\cap$ $3$ with $4$) = $1\over3$ * $1\over2$ = $1\over6$
So $1\over3$ + $1\over3$ - $1\over6$ = $1\over2$
Is this a valid solution? Is there a combinatorial explanation? I initially tried solving it using combinations and permutations but had difficulty.
 A: That looks good. If you want to do it by combinations you could list all possible pairings and see which fraction have your desired conditions. Possible pairings:
1-4|2-5|3-6
1-4|2-6|3-5
1-5|2-4|3-6
1-5|2-6|3-4
1-6|2-4|3-5
1-6|2-5|3-4
Only the last 3 have 1-6 or 3-4 in them. So you get probability of 1/2.
$\textbf{Edit (generalize to size n):}$
Label both the women and the men 1,2, ...,n with 'n' corresponding to the tallest person of that gender. Let a-b correspond to man 'a' being paired with woman 'b'.
Number of ways with 1-n or n-1 = number of ways with 1-n + number of ways with n-1 - number of ways with 1-n and n-1
To count these, imagine n buckets corresponding to the men
_ _ _ _ _ ... _
1 2 3 4 5 ... n
You can imagine pairing a specific woman with a man as placing her number in one of these buckets.  
To count the number ways woman 'n' can be paired with man '1', we place 'n' in bucket '1'. Then the rest of the numbers can be placed arbitrarily. So there are (n-1)! ways to do this.
To count the number ways woman '1' can be paired with man 'n', we place '1' in bucket 'n'. Then the rest of the numbers can be placed arbitrarily. So there are (n-1)! ways to do this.
To count the number of ways woman '1' can be paired with man 'n' and woman 'n' can be paired with man'1', we place' '1' in bucket 'n' and 'n' in bucket '1'. Then the rest of the numbers can be placed arbitrarily. So there are (n-2)! ways to do this.
This means our answer is 2 * (n-1)! - (n-2)!.
To calculate the probability, we divide by the number of possible pairings there are. The number of possible pairings corresponds to the number of ways we can place the numbers in the buckets, which is n!.
