Questions tagged [inclusion-exclusion]
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.
1,480
questions
0
votes
0
answers
111
views
Inequality of inclusion-exclusion terms
While analyzing the properties of an algorithm I am working on, I came up with the following inequality of inclusion-exclusion terms.
Let $0 \leq i \leq j < k$ be natural numbers. Then, I want to ...
- 15
-2
votes
0
answers
33
views
In how many ways can 5 non identical letters be mailed if there are 3 different mailboxes available if each letter and no mailbox remains empty [closed]
In how many ways can 5 non identical letters be mailed if there are 3 different mailboxes available if each letter and no mailbox remains empty?
1
vote
0
answers
30
views
What is the exact probability of rolling every possible result on an a-sided die at least b times each after rolling c times?
I have found answers to similar, much simpler questions on this site before (such as here How do you calculate probability of rolling all faces of a die after n number of rolls?), but can't find ...
- 221
1
vote
2
answers
32
views
Practical illustration of the inclusion-exclusion principle
I am currently doing a combinations problem that has two parts.
Part A: There are $26$ uppercase letters in the alphabet (A, B, C ... Z). How many $20$-letter words contain the subword 'DOWNTIME' ...
- 33
0
votes
1
answer
201
views
In how many ways $n$ balls can be given to $k$ children so that no child gets more than $3$ balls when balls are distinct/identical?
In how many ways $n$ balls can be given to $k$ children so that no child gets more than $3$ balls when balls are
a) balls are distinct
b) balls are identical
I am trying to solve this problem using ...
- 309
0
votes
1
answer
87
views
What is the probability that a positive integer not exceeding 100 selected at random is divisible by 5 or 7?
Q: What is the probability that a positive integer not exceeding 100 selected at random is divisible by $5$ or $7$?
Choosing a number from $1$ to $100$ divisible by $5$ is $\frac{5}{100} = \frac{1}{20}...
- 121
0
votes
0
answers
44
views
Is there a limit to the use of the Inclusion-exclusion principle for probability?
I'm scratching my head over this probability problem - can you help me figure out where I'm going wrong?
The problem states:
$P(A) = P(B) = P(C) = 0.25;$
$P(\color{red}{B}C) = 0;$
$P(AB) = P(AC) = 0....
1
vote
1
answer
51
views
How many permutations of set are there with 4 fixed points?
Given the set of numbers $A = \left \{ 1, 2, 3, 4, 5, 6, 7, 8 \right \}$. How many permutations leave exactly four numbers fixed?
I've considered this as a solution... but then I stumbled upon a ...
0
votes
0
answers
19
views
If 5 married couples are arranged in a row, find the probability that no one sits next to their spouse? [duplicate]
I tried to first finding the probability that only one couple sits together (9x2!8!) then two couples (25x2!2!2!6!) then three (22x3!2!2!2!4!) then four (14x4!2!2!2!2!) then five (5!x2!2!2!2!2!)
I ...
- 1
0
votes
0
answers
74
views
proof for $\sum_{r=0}^{40} {40 \choose r} (-1)^r {100-r \choose 40} = 1$
$\sum_{r=0}^{40} {40 \choose r} (-1)^r {100-r \choose 40} = 1$
I have tried expanding, simplifying it. It doesn't work. Anyone has any ideas?
- 1
1
vote
1
answer
74
views
Connection between probability and finite cardinality for Bonferroni inequalities
Let
$$S_1=\sum_i|A_i|, \quad S_2= \sum_{i<j}|A_i \cap A_j|, \quad S_3=\sum_{i<j<k} |A_i \cap A_j \cap A_k| ,\quad \cdots$$
Define alternating partial sums
$$R_1 = S_1,\quad R_2 = S_1 - S_2, \...
- 10.5k
0
votes
2
answers
82
views
There are $\mathrm{400}$ identical seats to be distributed among $\mathrm{3}$ parties such that each party has at most $\mathrm{200}$ seats
There are $\mathrm{400}$ identical seats to be distributed among $\mathrm{3}$ parties such that each party has at most $\mathrm{200}$ seats. What is the number $\mathrm{L}$ of all the possibilities ...
- 333
1
vote
1
answer
95
views
How many subsets $S$ of integer interval $[0,n]$ such that $n, n-1 \not \in S+S$?
Conjecture:
Given any $n \in \mathbb{Z}_{\geq 0}$, we have $$|\{S : (S \subseteq [0,n]) \land (n, n-1 \not \in S+S)\}| = F(n+2),$$ where $F$, the sequence of Fibonacci numbers, is given by $F(j) = F(...
- 115
0
votes
0
answers
39
views
Number of surjections from from a set of size $m$ onto a set of size $n$ using inclusion exclusion techniques
Basically, I need to show the number of functions from a set $A$ with $m$ elements onto the set $B$ with $n$ elements is $n!$ whenever $m=n$. It is easy to argue that each onto function is a bijection ...
- 744
0
votes
1
answer
69
views
Find the number of numbers with 5 digits that don't have the sequence 17 within them
This is simillar to another question that was asked on here but with 4 digits instead, I have already seen that question and used the same method, but for some reason I am still getting this question ...
- 199
2
votes
1
answer
78
views
Union of sets formula
Given a family of sets $A_i$, with i $\in\{1,2,...,n\}$, we need to prove the formula:
\begin{equation}
\bigcup_{i=1}^n A_i =(A_1\setminus A_2)\cup (A_2\setminus A_3) \cup \cdots\cup (A_{n-1}\setminus ...
1
vote
1
answer
57
views
How many six digit numbers are there containing digits from $\{1,...,9\}$ in which no digit appears more than three times?
The assignment doesn't have numerical answers, and I always make little errors with counting, so I'm just checking my work here.
Let $E_j$ be the event that the digit $j$ appears at most three times.
...
- 121
0
votes
0
answers
48
views
0
votes
2
answers
67
views
In how many ways can we seat 5 pairs of twins in a row of 10 chairs, such that nobody sits next to his or her twin?
This was a problem from the AOPS Intermediate Probability and Counting book, from a chapter on Principle of Inclusion Exclusion (PIE). I was able to follow the solution, but don't understand why PIE ...
- 51
5
votes
1
answer
130
views
Exercise 2 Stanley combinatorics volume 1: Bijective proof of a sum equality
Let $S$ be a finite set of objects and let $\mathscr{P}$ be a finite set of properties that the elements of $S$ may or may not satisfy. Given a subset of properties $X$, I define $f_=(X)$ as the ...
- 3,593
0
votes
0
answers
50
views
Chance that all $k$ bins are filled by $n≥k$ balls without using PIE
Find the probability that all $k$ bins are filled, if each of $n≥k$ balls are randomly placed into one of the $k$ slots.
I have solved the above question using PIE where I take the complement ($1$ - $...
- 13
2
votes
2
answers
173
views
Inclusion-exclusion solution to a probability problem about lotteries
A lottery consists of randomly drawing $6$ balls (without regard to order) from a bin of $44$ balls numbered $1$ through $44$. What is the probability at least one pair of consecutively numbered balls ...
3
votes
4
answers
301
views
Permutation question on arrangement of 6 objects, grouped in pairs of 2, in 2 rows with 3 spaces in each row.
Q. Three couples sit for a photograph in 2 rows of three people each such that no couple is sitting in
the same row next to each other or in the same column one behind the order. How many
arrangements ...
- 309
2
votes
1
answer
85
views
Counting $\{a,a,b,b,c,c,d,d,d \}$ derangements. [duplicate]
Exam question:
Let $D(d_{1},d_{2},...,d_{k})$ denote the number of derangements of a multiset where there are $d_{i}$ copies of elements of the $i$-th kind, for $i=1,...,k$.
This means the ...
- 371
8
votes
2
answers
177
views
Re-arrangements of $(1,1,2,2,3,3,4,4)$ with $(1,2,3,4)$ as a subsequence
In how many ways is it possible to re-arrange the sequence $(1,1,2,2,3,3,4,4)$, such that $(1,2,3,4)$ is a subsequence of it?
In case the question is not clear: what is the number of functions $f\...
- 404
0
votes
2
answers
179
views
How many six digit numbers are even or are divisible by 5?
Here is my attempt:
$$\text{Let A be the set of 6-digit numbers that are even.}$$
$$\text{Let B be the set of 6-digit numbers divisible by 5.}$$
$$\text{Thus, $A\cap B$ is the set of 6-digit numbers ...
- 21
0
votes
0
answers
12
views
Is the almost-disjoint gap minimized when all the sets almost overlap?
I recently defined the almost-disjoint gap to be
$$\mathcal{D}_{\mu} \left( E_1, \ldots, E_n \right) \triangleq \mu \left( \bigcup_{k=1}^{n} E_k \right) - \sum_{k=1}^n \mu \left( E_k \right)$$
where $\...
- 1,800
0
votes
1
answer
97
views
Is a measure of a union of sets is equal to the sum of measures on individual sets IFF the sets are disjoint?
Background
A (finite) measure is countably additive by definition. This entails that for a collection of disjoint sets the measure on the union of those sets is equal to the sum of the measures on ...
- 1,800
0
votes
1
answer
256
views
How to use Inclusion Exclusion On Dice
Here is the question
Suppose we roll 5 standard fair dice and sum the upfaces of the
largest 3 values showing. Find the probability that the sum is
18.
I tried an easier version of this question ...
- 39
2
votes
1
answer
115
views
Given six people of different heights, how many ways can we order them so no 3 consecutive people are ordered in increasing height
https://artofproblemsolving.com/wiki/index.php/Principle_of_Inclusion-Exclusion#Four_Set_Example
Here is where I found the problem, go to the four set example section. My question how do they say |A| ...
- 41
1
vote
1
answer
86
views
is this formula for $N(A \cup B \cup C \cup D)$ correctly applied?
Question : In a school, the students are fans of one or more of the four actors- A,B,C and D.The four actors given in the above order are liked by $230,180,180$ and $220$ students respectively.The no. ...
- 11
0
votes
0
answers
49
views
probability of intersection of confidence intervals
Suppose $\hat{\boldsymbol{\theta}} = \left(\hat{\theta}_1,\hat{\theta}_2\right)^{\top} \xrightarrow d N_2(\boldsymbol{\theta}, V)$ for some unknown $V.$ We have consistent estimator of $V:$ $\hat{V},$ ...
- 15
1
vote
1
answer
36
views
Having trouble understanding adding back the intersection of all elements when trying to get | A U B U C|, A, B, C being sets
According to the principle of inclusion and exclusion,
finding the union of 3 sets A,B, and C
I first need to add |A| + |B| + |C|, then subtract the intersections of all 3 sets,
(| A intersection B| +|...
- 41
0
votes
1
answer
56
views
Inclusion-Exclusion Lower Bound
Suppose that 80% of families own a DVD player and that 70% of families that own a computer. What is the range of possible percentages of families that own both?
I was able to see that the highest ...
- 775
0
votes
2
answers
55
views
Equivalence of categories: inclusion preservation
If $F: \mathscr{A} \rightarrow \mathscr{B}$ is an equivalence of categories, and $A,\tilde{A} \in \mathrm{obj}(\mathscr{A})$ such that $\tilde{A} \subseteq A$ in $\mathscr{A}$, does it immediately ...
0
votes
0
answers
46
views
Number of ways to select subsets to cover the original set
Suppose $S$ is a set with $n$ elements. Let $U=\{T|T\subseteq S\text{ and }|T|=k\}$, i.e., $U$ is the set of all possible subsets of $S$ with cardinality $k$. Clearly $|U|=\binom{n}{k}$. Then how many ...
- 185
3
votes
0
answers
81
views
Differential inclusion for piecewise finite-time lyapunov function
For each segment of a piecewise Lyapunov function that exhibits asymptotic stability, we can utilize the LaSalle-Yoshizawa theorem and solve it using a differential inclusion. This allows us to merge ...
- 745
7
votes
3
answers
628
views
6 children are sitting on a merry-go-round, in how many ways can you switch seats so that no one sits opposite the person who is opposite to them now?
I'm preparing for an exam and I would appreciate your help if you can tell me if there's a mistake in my solution.
Question
$6$ children are sitting on a merry-go-round:
Now, we need to change their ...
- 621
0
votes
1
answer
84
views
Stars and Bars with Multiple Restrictions
I've seen this Number of solutions to $x_1 +x_2 +x_3 +x_4 = 1097$ with multiple "at least" restrictions
and this Stars and bars (combinatorics) with multiple bounds.
But I am having trouble ...
- 39
3
votes
2
answers
110
views
Minimum size of set intersection
There was a survey about 5 kinds of common diseases and 100 people took the survey. 72 people have the first kind of disease, and 68, 66, 59, 82 for other 4 diseases respectively. People with at least ...
- 31
0
votes
1
answer
71
views
Basic Probability of 3 Events with 1 event being disjoint from the other 2.
Given that $\textrm{P}(Cc) = 0.82, \textrm{P}(B \cup C) = 0.41, \textrm{P}(A \cup C) = 0.52, \textrm{P}(A \cup B \cup C) = 0.69$. The event $C$ is disjoint from events $A$ and $B$. Compute
a.) $\...
- 3
0
votes
1
answer
320
views
We roll a $6$-sided die $n$ times. What is the probability that all faces have appeared?
How do I solve these questions, there are so many cases I know the total outcomes is$6^n$. However, I am lost after that.
- 1
1
vote
2
answers
756
views
Number of students who study both Hindi and English
In a survey of $100$ students, the number of students studying the various languages is found as: English only $18; $ English but not Hindi $23; $ English and Chinese $8;$ Chinese and Hindi $8;$ ...
- 5,146
3
votes
0
answers
93
views
Bizarre function that generalizes the inclusion-exclusion formula for $\pi(t) - \pi(\sqrt{t + 1})$. For all reals $t\geq 5$, the function is non-zero
Conjecture. The following arithmetic function is never zero, for any $t \in \Bbb{R}$, and $t \geq 5$:
$$
g(t) := \sum_{d \mid p_n\#}(-1)^{\omega(d)}\left\lfloor\frac{t}{d}\right\rfloor|G_d|
$$
where $...
- 21k
0
votes
5
answers
98
views
What is the greatest possible number of students that could have taken both algebra and chemistry?
Problem statement,
In a graduating class of $236$ students, $142$ took algebra and $121$ took chemistry. What is the greatest possible number of students that could have taken both algebra and ...
- 485
0
votes
0
answers
45
views
Is there sufficient information to determine how many people are both engineers and MBAs?
In a group of 500 people, 350 are engineers, 250 are MBA. Find how many people are both engineers and MBA?
I believe there is insufficient information given in the question.
My teacher gave $100$ as ...
- 485
4
votes
0
answers
153
views
How many partitions are there of the set {1, 2, ... , 25} into 5 equal parts, where no part is equal to either {1, ... , 5} , ... , {21, ... , 25}?
Find the number of partitions of the set {1, 2, ... , 25} into 5 equal parts, where no part is equal to either {1, ... , 5}, {6, ... , 10}, {11, ... , 15}, {16, ... , 20}, {21, ... , 25}.
So far I ...
- 163
2
votes
2
answers
100
views
Inclusion-exclusion conundrum: $\sum_{k=1}^{\lfloor n/2\rfloor} (-1)^{k-1}k\binom{n-k}{k}2^{n-2k} = \binom{n+1}{3}$
I want a proof (preferably combinatorial) of the identity
$$
\sum_{k=1}^{\lfloor n/2\rfloor} (-1)^{k-1}k\binom{n-k}{k}2^{n-2k} = \binom{n+1}{3}.
$$
I suspect that there is an inclusion-exclusion proof ...
- 451
2
votes
1
answer
64
views
Using inclusion-exclusion to determine how many solutions $x_1 + x_2 + x_3 + x_4 = 20$.
I've got a question regarding this assignment I've been looking at. The task itself is to use inclusion-exclusion principle to solve the equation:
$$
a + b + c + d = 20, \qquad \text{ where } 2 \le a, ...
- 47
10
votes
2
answers
350
views
Probability of rolling 4 dice and obtaining a sum from 2 dice of 3, 8, or 11?
Problem:
You roll 4 dice. What is the probability of getting 2 of the 4 dice to have a sum of 3, 8, or 11?
Examples:
1 2 3 4 -> counts -> as 1 + 2 = 3
1 2 3 6 -> counts -> as 1 + 2 = 3 OR ...
- 203