pith. sign in

arxiv: 1906.08671 · v1 · pith:2HJN6TV2new · submitted 2019-06-20 · 🧮 math.CO · math.NT

Counting birthday collisions using partitions

Rob Burns , Jen McKenzie This is my paper

Pith reviewed 2026-05-25 19:38 UTC · model grok-4.3

classification 🧮 math.CO math.NT
keywords birthday probleminteger partitionss-collisionscombinatorial countingcollision enumerationprobability formulaemultiplicity patterns
0
0 comments X

The pith

Integer partitions yield formulae for counting s-collisions in the birthday problem and its variants.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that integer partitions supply counting formulae for s-collisions and related events across different versions of the birthday problem. The approach organizes the possible patterns of shared birthdays by the multiplicity of each birthday value. A sympathetic reader would care because these counts determine the probabilities that appear in the classic birthday paradox and its generalizations to larger groups or different numbers of days. The partition method supplies explicit or recursive expressions that replace direct case-by-case enumeration.

Core claim

By associating each possible collision configuration with an integer partition that records the sizes of the colliding groups, the authors obtain formulae that count the number of ways s-collisions and other specified events can occur when birthdays are assigned uniformly at random.

What carries the argument

Integer partitions, used to classify the multiplicity patterns of shared birthdays among the people in the sample.

If this is right

  • Explicit counts become available for the number of ways to realize exactly one s-collision or a prescribed collection of collision sizes.
  • The same partition enumeration applies to variants with unequal day probabilities or with restrictions on which birthdays are possible.
  • The formulae support direct computation of probabilities for the absence of s-collisions or for the occurrence of multiple disjoint collision events.
  • Recursive relations among the counts follow from the standard recurrence properties of integer partitions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The partition technique could be applied to related allocation problems such as hash collisions or balls-and-bins occupancies that share the same multiplicity structure.
  • Comparison of the new counts against known closed forms for the ordinary birthday problem would provide an immediate consistency check.
  • The approach may extend naturally to generating functions that track the full distribution of collision sizes rather than isolated events.

Load-bearing premise

The patterns of birthday collisions correspond in a direct and useful way to the parts of integer partitions.

What would settle it

For small fixed numbers of people and days, the number of configurations with a given s-collision obtained from the partition formulae differs from the number obtained by exhaustive enumeration of assignments.

read the original abstract

We use partitions to provide some formulae for counting s-collisions and other events in various forms of the Birthday Problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript claims that integer partitions can be used to derive formulae for counting s-collisions and related events across variants of the birthday problem. It rests on the observation that collision multiplicity vectors stand in one-to-one correspondence with integer partitions of the sample size, thereby furnishing a direct combinatorial enumeration technique.

Significance. If the claimed formulae are both correct and new, the partition correspondence supplies a clean combinatorial language for a classic problem in enumerative combinatorics and probability. The approach is parameter-free by construction and could streamline calculations that are otherwise handled by inclusion-exclusion or generating functions; however, the absence of any displayed formulae, proofs, or numerical checks in the supplied text leaves the practical gain unclear.

major comments (2)
  1. No explicit formulae, derivations, or worked examples appear in the text. Without at least one concrete identity (e.g., an expression for the number of 3-collisions in the classical birthday problem expressed via partition functions), the central claim cannot be verified.
  2. The manuscript supplies neither a statement of the main theorem nor any verification data (tables, small-case checks, or comparison with known birthday probabilities). This omission makes it impossible to confirm that the partition enumeration reproduces standard results or yields new ones.
minor comments (1)
  1. The abstract is essentially a single sentence and does not indicate the precise variants treated or the form of the resulting formulae.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their comments. We agree that the submitted manuscript lacks explicit formulae, a formal theorem statement, and verification data, and we will revise to address these points directly.

read point-by-point responses

  1. Referee: No explicit formulae, derivations, or worked examples appear in the text. Without at least one concrete identity (e.g., an expression for the number of 3-collisions in the classical birthday problem expressed via partition functions), the central claim cannot be verified.

    Authors: We agree that the manuscript as submitted does not display explicit formulae or derivations. This was an oversight in the presentation of the partition correspondence. In revision we will add a concrete identity expressing the number of s-collisions via the relevant partition enumeration (specifically, summing over partitions whose parts encode the multiplicity vector), together with a short derivation and a worked numerical example for s=3. revision: yes

  2. Referee: The manuscript supplies neither a statement of the main theorem nor any verification data (tables, small-case checks, or comparison with known birthday probabilities). This omission makes it impossible to confirm that the partition enumeration reproduces standard results or yields new ones.

    Authors: We acknowledge the omission of both a formal theorem statement and any verification. The revised manuscript will state the main theorem (the bijection between collision multiplicity vectors and integer partitions of the sample size) explicitly. We will also include small-case tables comparing the partition-derived counts against direct enumeration and classical inclusion-exclusion formulae for the birthday problem, confirming agreement on known probabilities. revision: yes

Circularity Check

0 steps flagged

No significant circularity; direct combinatorial enumeration

full rationale

The paper's central claim is a direct combinatorial correspondence: collision multiplicity vectors are in one-to-one correspondence with integer partitions of the number of samples, yielding explicit formulae for counting s-collisions. No equations, parameters, or self-citations are described that reduce a result to its own inputs by construction. The approach is self-contained as a standard partition enumeration technique applied to the birthday problem, with no fitted inputs called predictions, no uniqueness theorems imported from self-citations, and no ansatz smuggled via prior work. This is the most common honest non-finding for a purely enumerative combinatorics paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities can be identified.

pith-pipeline@v0.9.0 · 5514 in / 873 out tokens · 20853 ms · 2026-05-25T19:38:44.722345+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages · 3 internal anchors

  1. [1]

    The computational com plexity of linear optics

    Scott Aaronson and Alex Arkhipov. The computational com plexity of linear optics. IN PROCEEDINGS OF STOC 2011 , 2011. 2

    work page 2011

  2. [2]

    Ahmed and R.J

    S.E. Ahmed and R.J. McIntosh. An asymptotic approximati on for the birthday prob- lem. Crux Math. , 26:151–155, 2000. 1

    work page 2000

  3. [3]

    The bosonic birthday p aradox

    Alex Arkhipov and Greg Kuperberg. The bosonic birthday p aradox. arXiv, arXiv:1106.0849:3, 2011. 2

    work page arXiv 2011

  4. [4]

    Arratia, S

    R. Arratia, S. Garibaldi, and J. Kilian. Asymptotic dist ribution for the birthday problem with multiple coincidences, via an embedding of the collision process. Random Structures and Algorithms , 48(3):480–502, 2016. 2

    work page 2016

  5. [5]

    The birthday problem and Markov chain Monte Carlo

    Itai Benjamini and Ben Morris. The birthday problem and m arkov chain monte carlo. arXiv, arXiv:math/0701390:7, 2007. 2

    work page internal anchor Pith review Pith/arXiv arXiv 2007

  6. [6]

    Bhattacharya, Somabha Mukherjee, and Sumit M ukherjee

    Bhaswar B. Bhattacharya, Somabha Mukherjee, and Sumit M ukherjee. Birthday paradox, monochromatic subgraphs, and the second moment ph enomenon. arXiv, arXiv:1711.01465:28, 2017. 2

    work page arXiv 2017

  7. [7]

    A (probably) exact solution to the birthday problem

    David Brink. A (probably) exact solution to the birthday problem. The Ramanujan Journal, 28(2):223–238, Apr 2012. 1, 8

    work page 2012

  8. [8]

    The matching, birthday and the strong birthday problem: a contemporary review

    Anirban DasGupta. The matching, birthday and the strong birthday problem: a contemporary review. Journal of Statistical Planning and Inference , 130(1):377 – 389,

    work page

  9. [9]

    Herman Chernoff: Eightieth Birthday Felicitation Volu me. 2, 9

    work page

  10. [10]

    A generalization of the Birthday problem and the chromatic polynomial

    Sukhada Fadnavis. A generalization of the birthday prob lem and the chromatic poly- nomial. arXiv, arXiv:1105.0698v3:17, 2015. 2

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  11. [11]

    A poisson limit law for a generalized bir thday problem

    Norbert Henze. A poisson limit law for a generalized bir thday problem. Statistics and Probability Letters, 39(4):333 – 336, 1998. 2

    work page 1998

  12. [12]

    Multicollisions in iterated hash functi ons

    Antoine Joux. Multicollisions in iterated hash functi ons. application to cascaded con- structions. Lecture Notes in Computer Science , pages 306–316, 2004. 2

    work page 2004

  13. [13]

    A birthday paradox for markov chains with an optimal bound for collision in the p ollard rho algorithm for discrete logarithm

    Jeong Han Kim, Ravi Montenegro, Yuval Peres, and Prasad Tetali. A birthday paradox for markov chains with an optimal bound for collision in the p ollard rho algorithm for discrete logarithm. Annals of Applied Probability , 20(2):495–521, 2010. 2

    work page 2010

  14. [14]

    E. H. Mckinney. Generalized birthday problem. The American Mathematical Monthly , 73(4):385, Apr 1966. 8

    work page 1966

  15. [15]

    A simple method fo r precisely determining complexity of many birthday attacks

    Ravi Montenegro and Ravi Montenegro. A simple method fo r precisely determining complexity of many birthday attacks. 2012. 2

    work page 2012

  16. [16]

    Rivest and Adi Shamir

    Ronald L. Rivest and Adi Shamir. Payword and micromint: Two simple micropayment schemes. Lecture Notes in Computer Science , pages 69–87, 1997. 2 10

    work page 1997

  17. [17]

    Integral Factorial Ratios

    K. Soundararajan. Integral factorial ratios. arXiv, arXiv:1901.05133:31, 2019. 4

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  18. [18]

    Soundararajan

    K. Soundararajan. Integral factorial ratios: Irreduc ible examples with height larger than 1. arXiv, arXiv:1906.06413:16, 2019. 4

    work page arXiv 1906

  19. [19]

    A new non-mds hash f unction resisting birth- day attack and meet-in-the-middle attack

    Shenghui Su, Tao Xie, and Shuwang Lu. A new non-mds hash f unction resisting birth- day attack and meet-in-the-middle attack. Theoretical Computer Science, 654:128–142, Nov 2016. 2

    work page 2016

  20. [20]

    Birthday para- dox for multi-collisions

    Kazuhiro Suzuki, Dongvu Tonien, Kaoru Kurosawa, and Ko ji Toyota. Birthday para- dox for multi-collisions. Lecture Notes in Computer Science , pages 29–40, 2006. 2, 8 11

    work page 2006