Document Open Access Logo

Counting and Matching

Authors Bart Jacobs, Dario Stein

PDF
Thumbnail PDF

File

LIPIcs.CSL.2023.28.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Bart Jacobs
  • Radboud University Nijmegen, The Netherlands
Dario Stein
  • Radboud University Nijmegen, The Netherlands

Acknowledgements

We like to thank Dusko Pavlovic for lively discussions on the topic of this paper - and on much more.

Cite As Get BibTex

Bart Jacobs and Dario Stein. Counting and Matching. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CSL.2023.28

Abstract

Lists, multisets and partitions are fundamental datatypes in mathematics and computing. There are basic transformations from lists to multisets (called "accumulation") and also from lists to partitions (called "matching"). We show how these transformations arise systematically by forgetting/abstracting away certain aspects of information, namely order (transposition) and identity (substitution). Our main result is that suitable restrictions of these transformations are isomorphisms: This reveals fundamental correspondences between elementary datatypes. These restrictions involve "incremental" lists/multisets and "non-crossing" partitions/lists. While the process of forgetting information can be precisely spelled out in the language of category theory, the relevant constructions are very combinatorial in nature. The lists, partitions and multisets in these constructions are counted by Bell numbers and Catalan numbers. One side-product of our main result is a (terminating) rewriting system that turns an arbitrary partition into a non-crossing partition, without improper nestings.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
Keywords
  • List
  • Multiset
  • Partition
  • Crossing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Aldous. Exchangeability and related topics. In P. Hennequin, editor, École d'Été de Probabilités de Saint-Flour XIII - 1983, number 1117 in Lect. Notes Math., pages 1-198. Springer, Berlin, 1985. URL: https://doi.org/10.1007/BFb0099421.
  2. M. Bona. Handbook of Enumerative Combinatorics. Discrete Mathematics and Its Applications. CRC Press, 2015. Google Scholar
  3. T. Broderick, J. Pitman, and M. Jordan. Feature allocations, probability functions, and paintboxes. Bayesian Analysis, 8:801-836, 2013. URL: https://doi.org/10.1214/13-BA823.
  4. H. Crane. The ubiquitous Ewens sampling formula. Statistical Science, 31(1):1-19, 2016. URL: https://doi.org/10.1214/15-STS529.
  5. W. Ewens. The sampling theory of selectively neutral alleles. Theoret. Population Biology, 3:87-112, 1972. URL: https://doi.org/10.1016/0040-5809(72)90035-4.
  6. Z. Galil and G. Italiano. Data structures and algorithms for disjoint set union problems. ACM Comput. Surv., 23:319-344, September 1991. URL: https://doi.org/10.1145/116873.116878.
  7. F. Hoppe. Pólya-like urns and the Ewens' sampling formula. Journ. Math. Biology, 20:91-94, 1984. URL: https://doi.org/10.1007/BF00275863.
  8. B. Jacobs. From multisets over distributions to distributions over multisets. In Logic in Computer Science. IEEE, Computer Science Press, 2021. URL: https://doi.org/10.1109/lics52264.2021.9470678.
  9. B. Jacobs. Multinomial and hypergeometric distributions in Markov categories. In A. Sokolova, editor, Math. Found. of Programming Semantics, number 351 in Elect. Proc. in Theor. Comp. Sci., pages 98-115, 2021. URL: https://doi.org/10.4204/EPTCS.351.7.
  10. B. Jacobs. Sufficient statistics and split idempotents in discrete probability theory. In Math. Found. of Programming Semantics, 2022. Google Scholar
  11. A. Joyal. Une théorie combinatoire des séries formelles. Advances in Mathematics, 42(1):1-82, 1981. URL: https://doi.org/10.1016/0001-8708(81)90052-9.
  12. G. Kreweras. Sur les partitions non croisées d'un cycle. Discrete Math., 1(4):333-350, 1972. Google Scholar
  13. R. Stanley. Parking functions and noncrossing partitions. Elect. Jour. of Combinatorics, 2(4), 1997. URL: https://doi.org/10.37236/1335.
  14. R. Stanley and S. Fomin. Enumerative Combinatorics, volume 2 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1999. URL: https://doi.org/10.1017/CBO9780511609589.
  15. S. Tavaré. The magical Ewens sampling formula. Bull. London Math. Soc., 53:1563-1582, 2021. URL: https://doi.org/10.1112/blms.12537.
  16. E. Weisstein. Restricted growth string. MathWorld - A Wolfram Web Resource. http://mathworld.wolfram.com/RestrictedGrowthString.html, July 2022.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact