O princípio da inclusão-exclusão e o cálculo de permanentes

José Ricardo Gonçalves de  Mendonça

doi:10.35819/remat2024v10i2id6987

Authors

José Ricardo Gonçalves de Mendonça Universidade de São Paulo (USP), São Paulo, SP, Brasil https://orcid.org/0000-0002-5516-0568

DOI:

https://doi.org/10.35819/remat2024v10i2id6987

Keywords:

discrete mathematics, combinatorial analysis, set partition, Ryser's algorithm, #P-complete problems

Abstract

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

Download data is not yet available.

Author Biography

José Ricardo Gonçalves de Mendonça, Universidade de São Paulo (USP), São Paulo, SP, Brasil

http://lattes.cnpq.br/8792749813872106

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.