Derangement Problem of Cards in Numbered Envelopes
Six cards and six envelopes are labeled with the numbers . The cards are placed into envelopes such that each envelope contains precisely one card, no card is inserted into the envelope bearing its own number, and card is specifically placed into envelope . The total number of ways to perform this is
Options
Topics & Concepts
Step-by-Step Solution
To determine the number of ways the cards can be placed into the envelopes, we define the placement of cards into envelopes as a permutation of the set , where represents the envelope into which card is placed.
The problem imposes the following conditions:
- Each envelope contains precisely one card, so is a bijection (a permutation of elements).
- No card is placed into the envelope bearing its own number, which means for all . This implies that is a derangement of elements.
- Card is specifically placed into envelope , which means .
The total number of derangements of elements, denoted by , is given by the formula:
For :
In any derangement of elements, the first card, card , can be placed into any envelope other than envelope . Thus, .
By the inherent symmetry of derangements, the number of derangements in which is identical for each .
Alternatively, using the standard recurrence relation for derangements: When card is fixed into envelope , there are two mutually exclusive cases for card :
-
Case 1: Card goes into envelope (). The remaining cards must be deranged among the remaining envelopes, which can be done in:
-
Case 2: Card does not go into envelope (). Card cannot go into envelope , card cannot go into envelope , and so forth. This is equivalent to finding the number of derangements of objects, which can be done in:
Therefore, the total number of ways to place card into envelope while satisfying the derangement condition is:
Equivalently, using symmetry:
Hence, the correct option is C.