Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Inclusion-Exclusion Formula

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 (30)

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 (32)

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.

Prime Numbers and Primality Testing

Covers prime numbers, RSA cryptography, and primality testing, including the Chinese Remainder Theorem and the Miller-Rabin test.

Dependence and Correlation

Explores dependence, correlation, and conditional expectations in probability and statistics, highlighting their significance and limitations.

Conditional Probability: Prediction Decomposition