Lecture

Inclusion-Exclusion Formula

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture covers the proof and applications of the inclusion-exclusion formula in discrete mathematics. The formula is demonstrated through examples, including the computation of permutations without fixed points and Euler's totient function. The lecture also explores the hat-check girl problem and the probability of nobody receiving their own hat back.

Official source

Related concepts (31)

Euler's totient function

In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as or , and may also be called Euler's phi function. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n. For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8.

Probability

Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, 0 indicates impossibility of the event and 1 indicates certainty. The higher the probability of an event, the more likely it is that the event will occur. A simple example is the tossing of a fair (unbiased) coin.

Probability theory

Probability theory or probability calculus is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set of axioms. Typically these axioms formalise probability in terms of a probability space, which assigns a measure taking values between 0 and 1, termed the probability measure, to a set of outcomes called the sample space.

Jordan's totient function

Let be a positive integer. In number theory, the Jordan's totient function of a positive integer equals the number of -tuples of positive integers that are less than or equal to and that together with form a coprime set of integers. Jordan's totient function is a generalization of Euler's totient function, which is given by . The function is named after Camille Jordan. For each , Jordan's totient function is multiplicative and may be evaluated as where ranges through the prime divisors of .

Probability distribution

In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon in terms of its sample space and the probabilities of events (subsets of the sample space). For instance, if X is used to denote the outcome of a coin toss ("the experiment"), then the probability distribution of X would take the value 0.5 (1 in 2 or 1/2) for X = heads, and 0.

Related lectures (64)

Conditional Density and Expectation

Explores conditional density, expectations, and independence of random variables with practical examples.

Probability and Statistics

Introduces probability, statistics, distributions, inference, likelihood, and combinatorics for studying random events and network modeling.

Probability and Statistics

Covers fundamental concepts in probability and statistics, emphasizing data analysis techniques and statistical modeling.

Probability and Statistics

Delves into probability, statistics, paradoxes, and random variables, showcasing their real-world applications and properties.

Law of Large Numbers: Strong Convergence

Explores the strong convergence of random variables and the normal distribution approximation in probability and statistics.

Related concepts (31)

Euler's totient function

Probability

Probability theory

Jordan's totient function

Probability distribution