Thomas Young remarked that if two different languages have the same word for one concept one cannot yet conclude that they are related since it may be a coincidence. \(^{\text {* })}\) In this connection he solved the following "Rencontre Problem" or "Matching Problem": What is the probability that an arbitrary permutation of \(n\), objects leaves no object in its place? Naturally it is assumed that each permutation has a probability \(n !^{-1}\) to occur. Show that the desired probability \(p\) as a function of \(n\) obeys the recurrence relation $$ n p(n)-(n-1) p(n-1)=p(n-2) $$ Find \(p(n)\) and show that \(p(n) \rightarrow \mathrm{e}^{-1}\) as \(n \rightarrow \infty\).

Combinatorics is an area of mathematics focused on counting, arranging, and combination. It lays the foundation for analyzing events where order or grouping is pivotal. An intuitive example is how we can organize books on a shelf or select a subset of fruits from a basket.

Within this field, the Rencontre Problem presents a classic combinatorial scenario. It queries the likelihood of a perfect non-alignment of elements within a permutation, forming what is called a derangement. By studying these combinatorial structures, we not only improve our conceptual understanding but also cultivate analytical skills vital for problem-solving in real-world applications and other mathematical domains.

A permutation is an arrangement of all the members of a set into a sequence or order. For a set with 'n' distinct elements, there are 'n!' (n factorial) possible permutations. This means if we have three books, there are 3! = 6 different ways to arrange them.

In the context of the Rencontre Problem, we're interested in a special type of permutation called a derangement, where no element appears in its original position. Calculating these specific permutations is key to understanding the problem and connects deeply with combinatorics and probability theory.

Probability is the measure of the likelihood of an event to occur. It’s a fundamental concept in mathematics that allows us to predict how often events are expected to happen. In the Rencontre Problem, we determine the probability that a random permutation of 'n' objects results in a derangement. Each possible derangement or permutation is equally likely, occurring with a chance of !^{-1}.

Understanding the probability of derangements leads to fascinating conclusions about seemingly random patterns and has important implications in fields like cryptography, game theory, and statistical mechanics.

A derangement is a permutation in which none of the objects appear in their original positions. Famously illustrated by the Rencontre Problem, a derangement represents a complete mismatch between two sets, such as assigned seats to guests, and none of the guests sit in their assigned seat.

To precisely compute the probability of a derangement, we employ factorials to count possible arrangements and apply inclusion-exclusion principles. Interestingly, derangements are not just a theoretical curiosity but have practical relevance in the design of secure communication systems and the study of shuffled decks in card games.

A recurrence relation is an equation that defines a sequence based on preceding terms. It's a way to express complex relationships in a recursive format, often simplifying the process of finding terms in a sequence without computing every single one directly.

The recurrence relation provided in the Rencontre Problem, (n p(n) - (n-1) p(n-1) = p(n-2)), elegantly encapsulates the behavior of derangement probabilities across different values of 'n'. By starting with initial conditions and applying this recursive pattern, one can reveal the structure of the sequence and venture towards a general formula.