The inclusion-exclusion principle states that the number of elements in the union of two given sets is the sum of the number of elements in each set, minus the number of elements that are in both sets.
Questions tagged [inclusion-exclusion]
1435 questions
85
votes
10 answers
100 Soldiers riddle
One of my friends found this riddle.
There are 100 soldiers. 85 lose a left leg, 80 lose a right leg, 75
lose a left arm, 70 lose a right arm. What is the minimum number of
soldiers losing all 4 limbs?
We can't seem to agree on a way to approach…
Pieter van Niekerk
- 907
- 1
- 7
- 10
62
votes
5 answers
Number of onto functions
What are the number of onto functions from a set $\Bbb A $ containing m elements to a set $\Bbb B$ containing n elements.
I found that if $m = 4$ and $n = 2$ the number of onto functions is $14$.
But is there a way to generalise this using a…
IcyFlame
- 857
- 1
- 10
- 15
46
votes
2 answers
What is the optimal number of dice to roll a Yahtzee in one roll?
Description
In the game of Yahtzee, 5 dice are rolled to determine a score. One of the resulting rolls is called a Yahtzee.
To roll a Yahtzee you must have 5 of a kind. (5 1's or 5 2's or 5 3's etc..).
In the game of Yahtzee you can only have 5…
Michael King
- 591
- 3
- 6
32
votes
6 answers
Why is the Derangement Probability so Close to $\frac{1}{e}$?
A derangement is a permutation $\sigma$ of $\{1,2,3,\dots,n\}$ such that $\sigma(i) \neq i$ for every $i$. A common application of inclusion/exclusion in undergraduate combinatorics and probability classes is to compute the number of derangements,…
Kevin P. Costello
- 6,224
- 22
- 45
22
votes
5 answers
In how many ways can $1000000$ be expressed as a product of five distinct positive integers?
I'm trying to solve the following problem:
"In how many ways can the number $1000000$ be expressed as a product of five distinct positive integers?"
Here is my attempt:
Since $1000000 = 2^6 \cdot 5^6$, each of its divisors has the form $2^a \cdot…
user144765
- 700
- 1
- 5
- 18
21
votes
1 answer
Is the Maclaurin series expansion of $\sin x$ related to the inclusion-exclusion principle?
When I see the alternating signs in the infinite series expansion of $\sin x$, I'm reminded of the inclusion-exclusion principle. Could there be any way to visualize it in such a way?
Also, is there an elementary reason why the Taylor series…
hollow7
- 2,385
- 5
- 21
- 24
19
votes
4 answers
Sum of binomial coefficients $\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$
How do I prove the following identity:
$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$$
I am trying to use inclusion-exclusion, and this will boil down to a sum like inclusion-exclusion, and the $\binom{2n-2k}{n-1}$ term wouldn't…
Mark
- 193
- 3
19
votes
3 answers
Combinatorial argument to prove the recurrence relation for number of derangements
Give a combinatorial argument to prove that the number of derangements satisfies the following relation:
$$d_n = (n − 1)(d_{n−1} + d_{n−2})$$
for $n \geq 2$.
I am able to prove this algebraically but not able to see the combinatorial example.
Arjun Kaa
- 191
- 1
- 1
- 3
19
votes
5 answers
Inclusion-exclusion-like fractional sum is positive?
Let $A_1,A_2,\ldots,A_n$ be finite nonempty sets. Is it true that
$$\sum_{i=1}^n\frac{1}{|A_i|}-\sum_{1\leq i
nan
- 1,045
- 5
- 16
18
votes
5 answers
Famous uses of the inclusion-exclusion principle?
The standard textbook example of using the inclusion-exclusion principle is for solving the problem of derangement counting; using inclusion-exclusion (and some basic analysis) it can be shown that $D(n)=\left[\frac{n!}{e}\right]$ which I consider…
Gadi A
- 18,755
- 7
- 77
- 120
18
votes
5 answers
Generalised inclusion-exclusion principle
In answers to combinatorial questions, I sometimes use the fact that if there are $a_k$ ways to choose $k$ out of $n$ conditions and fulfill them, then there are
$$
\sum_{k=j}^n(-1)^{k-j}\binom kja_k
$$
ways to fulfill exactly $j$ of the conditions.…
joriki
- 227,898
- 14
- 283
- 497
17
votes
1 answer
A general "inclusion-exclusion principle" / Formulas like $\inf(a,b)\sup(a,b)=ab$
Let me list a few formulas which should be well-known:
(GCD-LCM product formula) For positive integers $n,m$,
$$\operatorname{gcd}(n,m)\operatorname{lcm}(n,m)=nm.$$
(Inclusion-exclusion principle) For sets $A,B$,
$$\#(A\cap B)+\#(A\cup…
Luiz Cordeiro
- 18,034
- 29
- 60
16
votes
2 answers
Number of functions $f:\{1,...,n\}\to\{1,...,n\}$ that have $|f^{-1}(\{i\})|=i$ for some $i$
Let $S=\{1,...,n\}$, I am looking at number of functions functions $f:S\to S$ such that there exists $i \in S$ such that $$|f^{-1}(\{i\})|=i$$
I am guessing I am supposed to use PIE (Principle of Inclusion and Exclusion)
I let $X=\{f:S\to S\}$.
My…
Nasal
- 768
- 3
- 14
16
votes
3 answers
What is the cardinality of the union A∪B∪...∪Z?
I have figured out that $|A \cup B| = |A| + |B| - |A \cap B| $
and that
$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$.
I have not managed to figure out what $|A \cup B \cup C \cup D|$ is equal to.…
K. Claesson
- 619
- 4
- 16
16
votes
2 answers
Arrangements of a,a,a,b,b,b,c,c,c in which no three consecutive letters are the same
Q: How many arrangements of a,a,a,b,b,b,c,c,c are there such that
$\hspace{5mm}$ (i). no three consecutive letters are the same?
$\hspace{5mm}$ (ii). no two consecutive letters are the same?
A:(i). 1314. ${\hspace{5mm}}$ (ii). 174.
I thought of…
Stoner
- 1,176
- 4
- 15
- 34