Derangements and Generalizations: A Counting Note on the Matching Problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911230917083136 |
|---|---|
| author | Luciano, Antoine |
| author_facet | Luciano, Antoine |
| contents | We give a concise historical background to Montmort's matching problem and its modern variants such as the hat-check problem, then develop a unified counting framework for fixed-point-free allocations. Using elementary recurrence and inclusion-exclusion arguments, we derive closed forms for derangements, rectangular injections, and partial l-matchings, and we combine them into a single formula. We also provide exact counts for the number of fixed points and Poisson limit laws. This note thus offers a compact, self-contained synthesis linking classical results with their two principal generalizations in a single scheme. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21753 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Derangements and Generalizations: A Counting Note on the Matching Problem Luciano, Antoine History and Overview Combinatorics We give a concise historical background to Montmort's matching problem and its modern variants such as the hat-check problem, then develop a unified counting framework for fixed-point-free allocations. Using elementary recurrence and inclusion-exclusion arguments, we derive closed forms for derangements, rectangular injections, and partial l-matchings, and we combine them into a single formula. We also provide exact counts for the number of fixed points and Poisson limit laws. This note thus offers a compact, self-contained synthesis linking classical results with their two principal generalizations in a single scheme. |
| title | Derangements and Generalizations: A Counting Note on the Matching Problem |
| topic | History and Overview Combinatorics |
| url | https://arxiv.org/abs/2510.21753 |