Answers are grounded in this paper and cite their sources.
Multisets are like sets, except that they can contain multiple copies of their elements. If there are nᵢ copies of i, 1≤ i≤ t, in multiset Mₜ, then there are (0.0ptn₁+⋯ +nₜn₁, ,nₜ) possible permutations of Mₜ. Knuth showed how to factor any multiset permutation into cycles. For fixed nᵢ, i≥ 1, we show how to adapt the Chinese restaurant process, which generates random permutations on n elements with weighting θ ^# 0.1667emcycles, θ > 0, sequentially for n=1,2,, to the multiset case, where we fix the nᵢ and build permutations on Mₜ sequentially for t=1,2,. The number of cycles of a multiset permutation chosen uniformly at random, i.e. θ =1, has distribution given by the sum of independent negative hypergeometric distributed random variables. For all θ > 0, and under the assumption that nᵢ=O(1), we show a central limit theorem as t→ ∞ for the number of cycles.
No takes yet. Share an insight, caveat, or question.
Dudley Stark (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: