Formulations of the inclusion–exclusion principle from Legendre to Poincaré, with emphasis on Daniel Augusto da Silva

Abstract

The inclusion–exclusion principle is a simple, intuitive, and extremely versatile result. It is one of the most useful methods for counting and it can be used in different areas of mathematics. In the eighteenth century, the first uses of this result that appear in the literature are related to the study of problems of games of chance. However, the first formulations of this principle appear, independently by several authors, only in the nineteenth century. In this article, we study the formulations obtained by Adrien-Marie Legendre, Daniel Augusto da Silva, James Joseph Sylvester, and Henri Poincaré. We highlight the contribution of the Portuguese mathematician Daniel Augusto da Silva, since his formulation can be applied to different problems of number theory, whenever collections of numbers satisfying certain properties are involved, and this is the reason why his formulation stands out compared with all the others.

Acknowledgments

The authors thank the anonymous referee for the careful reading of the manuscript and for the helpful suggestions which improved the final version of the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 All quotations in Portuguese and French have been translated into English by the authors.

2 In his Théorie analytique des probabilités (1812), Laplace uses the IEP to solve a probability problem, but he does not write a formal statement of the principle (Laplace 1812, 253–261). We have identified a brief indication of this in (Takács 1967, 104, 106). In his Calcul des probabilités (1896), Poincaré determines the probability that at least one event occurs among a collection of n events. The solution of this problem is known as the general probability theorem or the probabilistic inclusion-exclusion principle. A brief note of this fact can be found in (Takács 1967, 103). The references to da Silva and Sylvester appear in introductory monographs to the study of combinatorics or discrete mathematics, also with very brief considerations. As examples, see (Ryser 1963, 19; van Lint and Wilson 2001, 96; Erickson 1996, 107; Mazur 2010, 94; and Gallier 2011, 229–236).

3 Smith's text, also about the resolution of binomial congruences, was published in 1861 in the Philosophical Transactions. Da Silva's extensive memoir in mechanics, Memória sobre a rotação das forças em torno dos pontos de applicação (Memoir on the Rotation of Forces Around the Points of Application) (1851), which places him as a reference in the history of astatics, was also unknown to the scientific community since it was written in Portuguese. For further details, see (Martins 2014) (a biography, on the occasion of the bicentenary of his birth) and (Martins 2013) (for an overview of his scientific production and details on his instruction, teaching activity, affiliation to scientific and literary institutions and contributions on actuarial calculus). For a digital copy of some of his scientific texts, see https://www.marinha.pt/pt/a-marinha/historia/personalidades-ilustres/Paginas/Daniel-Augusto-da-Silva.aspx#tab2.

4 Boolean algebra was introduced by Boole in The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning (1847) and set forth more fully in his Investigation of the Laws of Thought, on which are Founded the Mathematical Theories of Logic and Probabilities (1854). For more details, see (Valencia 2004).

5 Nicolaus Bernoulli also studied the problem and he gave the proof of Montmort's formulas (Montmort 1713, 301–302). The ‘problem of coincidences’ is currently formulated as follows. Let n objects be labelled from $1,2,\dots ,n$. A permutation such that object i is placed in the ith position is called a coincidence. The aim is to determine the number of permutations with at least one coincidence. For further details, see (Takács 1980) and (Hald 1990, 330–332).

6 For further details, see (Takács 1980) and (Hald 1990, 336–338).

7 The classical occupancy problem, in its most simple form, is about the problem of randomly assigning a set of objects into a group of cells: if we place k objects into n cells, what is the probability that exactly j cells ($1\le j\le k$) are occupied? For further details, see (Bellhouse 2011, 65–80).

8 For further details the reader is referred to (Edwards 1983) and (Takács 1969).

9 The current notation $\varphi N$ was introduced by Carl Gauss (1777–1855) in the Disquisitiones Arithmeticae (1801). Da Silva uses the notation $\phi N$, that we will adopt.

10 Margiochi, naval officer, politician and professor, taught Mathematics at the Academia Real de Marinha (Royal Navy Academy) since 1801 and occasionally at the Academia Real dos Guardas-Marinhas (Royal Academy of Ensigns). He was a member of the RASL and of the Sociedade Real Marítima, Militar e Geográfica (Royal Maritime, Military and Geographical Society). His writings include topics on arithmetic, geometry, calculus, integral calculus and celestial mechanics. For political reasons, he was forced into exile in England and France in 1823, returning to Portugal in 1833. On Margiochi's proof, da Silva says that the induction method he used ‘is far from being evident’ (da Silva 1854, 13). On Margiochi's texts published by the RASL see (Saraiva 2008).

11 In fact, the primacy of Cantor's contribution to the genesis of set theory has been widely disseminated since the beginning of the twentieth century, and da Cunha shared this opinion. Nowadays, historiographic approaches that also emphasize the role of other mathematicians are not frequent. The texts of José Ferreirós, since the 1990s, stand out; see (Ferreirós 2007).

12 A full analysis of Poincaré's text is made in (Sheynin 1991).

13 The origin of the idea of expected value dates from the mid-seventeenth century, with the study of games of chance. Pascal and Fermat introduced the idea of ‘value of a game as the probability of winning times the total stake’, which Christiaan Huygens (1629–1695) would later call expectation (Hald 1990, 43–44). Poincaré adopts that definition. In the mid-nineteenth century, Pafnuty Chebyshev (1821–1894) ‘was the first to think systematically in terms of ‘random variables' and their ‘expectations' and ‘moments’ (Mackey 1980, 529).

14 Poincaré presents the incorrect expression $\sum p_i$, in both editions: (Poincaré 1896, 35; Poincaré 1912, 58).

15 Poincaré incorrectly says that the gain when events A_i and A_k (i = 1, …, n) occur, is 1. The claim is reproduced in both editions: (Poincaré 1896, 35; Poincaré 1912, 58).

16 Observe that the last inequality follows directly from the binomial expansion, for a single variable x, when we take x to be equal to $-1$. In fact, since $(1+x{)}^n=(\genfrac{}{}{0ex}{}{n}{0})x^0+(\genfrac{}{}{0ex}{}{n}{1})x^1+(\genfrac{}{}{0ex}{}{n}{2})x^2+\dots (\genfrac{}{}{0ex}{}{n}{n-1})x^{n-1}+(\genfrac{}{}{0ex}{}{n}{n})x^n$, for x = −1 we have: $0=1-n-\frac{n(n-1)}{2}+\dots +(-1{)}^n$.

Additional information

Funding

Ana Patrícia Martins was partially funded by national funds through the FCT – Fundação para a Ciência e a Tecnologia, I.P./MCTES, under the scope of the projects (PIDDAC): UIDB/00286/2020 e UIDP/00286/2020 (Interuniversity Centre for the History of Science and Technology). Teresa Sousa was partially funded by national funds through the FCT – Fundação para a Ciência e a Tecnologia, I.P., under the scope of the projects UIDB/00297/2020 and UIDP/00297/2020 (Center for Mathematics and Applications).