On the minimum of independent collecting processes via the Stirling numbers of the second kind

DOI10.1016/J.SPL.2022.109426arXiv2202.03713WikidataQ114130476 ScholiaQ114130476MaRDI QIDQ6390467

Aristides V. Doumas

Publication date: 8 February 2022

Abstract: We consider the combinatorial problem where $p$ players aim to a complete set of $N$ different types of items (species) which are uniformly distributed. Let the random variables $T_{N(i)},,,i=1,2,cdots,p$ denoting the number of trials needed until all $N$ types are detected (at least once), respectively for each player. This paper studies the impact of the number $p$ in the asymptotics of the expectation, the second moment, and the variance of the random variable �egin{equation*} M_{N(p)}: = �igwedge_{i=1}^p T_{N(i)},,,,,,,N ightarrow infty. end{equation*} The main ingredient in the expression of these quantittes are sums involving the Stirling numbers of the second kind; for which the asymptotics are explored. At the end of the paper we conjecture on a remarkable extit{combinatorial identity}, regarding alternating binomial sums. These sums have been studied (mainly) by P. Flajolet due to their applications to digital search trees and quadtrees.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Central limit and other weak theorems (60F05) Bell and Stirling numbers (11B73) Combinatorial identities, bijective combinatorics (05A19) Asymptotic enumeration (05A16)

This page was built for publication: On the minimum of independent collecting processes via the Stirling numbers of the second kind

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6390467)