The Strong Birthday Problem Revisited
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_ | 1866908892196241408 |
|---|---|
| author | Tripathy, Chijul B. |
| author_facet | Tripathy, Chijul B. |
| contents | We revisit the Strong Birthday Problem (SBP) introduced by DasGupta'05, which asks for the minimum population n required such that, with a probability of at least 1/2, every individual in the group shares a birthday with at least one other person. Formally, we develop and analyze computational frameworks to determine the probability that in a group of n people with birthdays distributed over m days, each day either has two or more birthdays or is birthday-free. We derive both counting-based and probability-based recurrence relations to solve this problem and establish a novel connection to associated Stirling numbers of the second kind. This relationship is exploited to derive new, more efficient recurrences. Finally, we implement these recurrences using dynamic programming, provide analysis of their asymptotic complexities, and present numerical evaluations that demonstrate the practical efficiency and scalability of our proposed approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26056 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Strong Birthday Problem Revisited Tripathy, Chijul B. Combinatorics Discrete Mathematics Data Structures and Algorithms We revisit the Strong Birthday Problem (SBP) introduced by DasGupta'05, which asks for the minimum population n required such that, with a probability of at least 1/2, every individual in the group shares a birthday with at least one other person. Formally, we develop and analyze computational frameworks to determine the probability that in a group of n people with birthdays distributed over m days, each day either has two or more birthdays or is birthday-free. We derive both counting-based and probability-based recurrence relations to solve this problem and establish a novel connection to associated Stirling numbers of the second kind. This relationship is exploited to derive new, more efficient recurrences. Finally, we implement these recurrences using dynamic programming, provide analysis of their asymptotic complexities, and present numerical evaluations that demonstrate the practical efficiency and scalability of our proposed approaches. |
| title | The Strong Birthday Problem Revisited |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.26056 |