The inclusion-exclusion principle and the calculation of permanents
DOI:
https://doi.org/10.35819/remat2024v10i2id6987Keywords:
discrete mathematics, combinatorial analysis, set partition, Ryser's algorithm, #P-complete problemsAbstract
In this article we review the inclusion-exclusion principle (PIE) from set theoretical and algebraic points of view and discuss its application to the calculation of permanents, a subject that is not normally covered in undergraduate courses. The presentation is intended to be rigorous but elementary, accessible to first-year students in mathematics, science, and engineering programs, requiring only familiarity with set notation, arithmetic and matrix algebra. In dealing with the calculation of permanents, we present the Ryser algorithm, one of the most spectacular developments in the approach to difficult combinatorial problems, whose computational complexity we briefly discuss. The article contains examples, complementary notes, and a program in Python that implements Ryser's algorithm using Gray codes to calculate permanents, accompanied by its discussion.
Downloads
References
ARORA, Sanjeev; BARAK, Boaz. Computational Complexity: A Modern Approach. Cambridge, UK: Cambridge University Press, 2009. ISBN: 978-0-521-42426-4.
BARVINOK, Alexander. Combinatorics and Complexity of Partition Functions. [S. l.]: Springer, 2016. v. 30. ISBN: 978-3-319-51828-2. DOI: https://doi.org/10.1007/978-3-319-51829-9.
BRUALDI, Richard A.; RYSER, Herbert John. Combinatorial Matrix Theory. Cambridge, UK: Cambridge University Press, 1991. v. 39. Encyclopedia of Mathematics and its Applications. ISBN: 0-521-32265-0.
GOLDREICH, Oded. Computational Complexity: A Conceptual Perspective. Cambridge, UK: Cambridge University Press, 2008. ISBN: 978-0-521-88473-0.
HAZZAN, Samuel. Fundamentos de Matemática Elementar: Combinatória e Probabilidade. 8. ed. São Paulo, SP: Atual, 2013. v. 5. ISBN: 978-8-535-71750-1.
HEFEZ, Abramo. Aritmética. 2. ed. Rio de Janeiro, RJ: SBM, 2016. v. 8. Coleção PROFMAT. ISBN 978-85-8337-105-2.
KALMANN, Ralph. A method for finding permanents of 0, 1 matrices. Mathematics of Computation, Providence, RI, v. 38, n. 157, p. 167-170, 1982. DOI: https://doi.org/10.1090/S0025-5718-1982-0637294-0.
MINC, Marvin. Permanents. London: Addison-Wesley, 1978. v. 6. Encyclopedia of Mathematics and its Applications. ISBN: 0-201-13505-1.
MORGADO, Augusto César; CARVALHO, João Bosco Pitombeira de; CARVALHO, Paulo Cezar Pinto; FERNANDEZ, Pedro. Análise Combinatória e Probabilidade. 11. ed. Rio de Janeiro, RJ: SBM, 2020. Coleção do Professor de Matemática. ISBN 978-65-990-3953-9.
NIJENHUIS, Albert; WILF, Herbert Saul. Combinatorial Algorithms for Computers and Calculators. 2. ed. New York: Academic Press, 1978.
REALE, Fábio Tosetto. Métodos de Monte Carlo para amostragem de permutações com restrições e aplicações. Orientador: José Ricardo Gonçalves de Mendonça. 2018. 57 f. Dissertação (Mestrado em Modelagem de Sistemas Complexos) - Escola de Artes, Ciências e Humanidades, Universidade de São Paulo, São Paulo, 2018. DOI: https://doi.org/10.11606/D.100.2018.tde-06092018-144335.
RIORDAN, John. Introduction to Combinatorial Analysis. Mineola, NY: Dover, 2002. ISBN 0-486-42536-3.
RYSER, Herbert John. Combinatorial Mathematics. Rahway, NJ: The Mathematical Association of America, 1963. v. 14. Carus Mathematical Monographs.
SCHROEDER, Manfred Robert. Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity. 5. ed.
Berlin: Springer, 2009. ISBN: 978-3-540-85297-1. DOI: http://doi.org/10.1007/978-3-540-85298-8.
TENENBAUM, Gérald; FRANCE, Michel Mendès. The Prime Numbers and Their Distribution. Providence, RI: AMS, 2000. v. 6. Student Mathematical Library. ISBN: 978-0-821-81647-9.
VALIANT, Leslie Gabriel. The complexity of computing the permanent. Theoretical Computer Science, Amsterdam, NL, v. 8, n. 2, p. 189-201, Mar. 1979. DOI: https://doi.org/10.1016/0304-3975(79)90044-6.
VALIANT, Leslie Gabriel. The complexity of enumeration and reliability problems. SIAM Journal on Computing, v. 8, n. 3, p. 410-421, Aug. 1979. DOI: https://doi.org/10.1137/0208032.
VAN LINT, Jacobus Hendricus; WILSON, Richard Michael.A Course in Combinatorics. 2. ed. Cambridge, UK: Cambridge University Press, 2001. ISBN: 978-0-521-80340-3. Disponível em: http://www.cambridge.org/9780521803403. Acesso em: 23 set. 2024.
WHITNEY, Hassler. A logical expansion in mathematics. Bulletin of the American Mathematical Society, New York, v. 38, n. 8, p. 572-579, Aug. 1932. DOI: https://doi.org/10.1090/S0002-9904-1932-05460-X.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 José Ricardo Gonçalves de Mendonça
This work is licensed under a Creative Commons Attribution 4.0 International License.
REMAT retains the copyright of published articles, having the right to first publication of the work, mention of first publication in the journal in other published media and distribution of parts or of the work as a whole in order to promote the magazine.
This is an open access journal, which means that all content is available free of charge, at no cost to the user or his institution. Users are permitted to read, download, copy, distribute, print, search or link the full texts of the articles, or use them for any other legal purpose, without requesting prior permission from the magazine or the author. This statement is in accordance with the BOAI definition of open access.
How to Cite
