I am trying to understand this "matching problem". given n distinct objects, number each of them. We are said to have a "match" if we permute the n objects, and the ith object is in the ith position. This books says that "the probability that there are no matches among j randomly permuted objects is defined as p_j. Then there are j!*p_j number of ways we that j objects can be permuted such that there are no matches"
How is this possible? I understand that if we take objects that are completely different from the positions, such as (6,7,8) because the positions are 1,2, and 3, and we can arrange this in 3! ways and never obtain a match because the objects themselves aren't any of the possible positions (if we had 8 objects for example, and I pulled these 3).
But if I take j objects, number them so that they are distinct, then how could there be j! ways to arrange these objects so they don't match? Wouldn't at some point they will arrange themselves in a position where they match?
(For context, this is introduction to probability theory by Hoel. The problem is the example "Two equivalent decks of cards are well shuffled and matched against each other. What is the probability of at least one match?) Thank you!
Best Answer
Let the number of ways to permute $n$ objects such that there are no matches be called the number of derangements of $n$, or $d_n$.
The probability that a random permutation is a derangement is
$$ p_n = \frac{d_n}{n!} $$
It is now clear that
$$ n! p_n = d_n $$