The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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.

Filter by
Sorted by
Tagged with
0
votes
0answers
20 views

How many species of regular 100-sided polygons are there?

I saw a resolution that showed the general case starting at $ n = 8 $. It has been found that the polygon species should be prime numbers relative to $ 100 $ and less than $ 50 $. Why should it be ...
1
vote
1answer
42 views

Class of 100 students, 10 who speak German, 20 who speak Italian, 30 who speak Spanish, 8 who speak both Italian and Spanish, 3 speak all 3 languages

How many people in the class speak none of the 3 languages? 10 speak German, minus the 3 who speak all languages is 7. 20 speak Italian, minus the 3 who speak all languages and the 8 who speak both ...
4
votes
1answer
77 views

175 speak German ,150 French, 180 English, 160 Japanese. How many speak all of them?

Among 200 journalists, there are: 175 speak German 150 speak French 180 speak English 160 speak Japanese Each journalist can speak at least one of the 4 languages. What is the maximum possible ...
1
vote
2answers
32 views

Proving The (Kind-Of) Inclusion-Exclusion Principle

Let $V$ be an $F$-vector space and let $U$ and $W$ be finite dimensional subspaces of $V$. Show that $U+W$ is finite dimensional, and moreover that $$\dim_F(U+W)=\dim_F(U)+\dim_F(W)-\dim_F(U\cap W)...
1
vote
0answers
23 views

Inclusion–exclusion principle on multiple set maximum value?

Say there are $46$ people in a club, $35$ of them are Chess lovers, $30$ of them are sports lovers, $40$ of them are Opera lovers, $38$ of them are video game lovers. So at least how many people are ...
3
votes
3answers
60 views

What is the general method to find an asymptotic formula for alternating sums

How to find an asymptotic formula for the following sum: $$ \sum_{k=0}^n(-1)^k{n\choose k}\frac{n!2^k}{(n-k)!}(2n-2k)! $$ when $n\to\infty$? If we set $S_k:={n\choose k}\frac{n!2^k}{(n-k)!}(2n-2k)!$...
8
votes
1answer
78 views

Showing that two combinatorial expressions are equal

Is there an algebraic way of showing that $$\sum_{m=\lceil p / b\rceil}^{c} \left(-1\right)^m \frac{\binom{b\cdot m}{p}}{\binom{b\cdot c}{p}} \sum_{k=m}^{c}k\cdot(-1)^{k} \binom{c}{k} \binom{k}{m} = c\...
0
votes
1answer
27 views

Inclusion/Exclusion, finding $x,y,z$ and $a,b,c$

In a competition with 80 participants, a school awarded medals in different categories. 36 medals in dance (D), 12 medals in dramatics (R) and 18 medals in music (M). If these medals went to a total ...
1
vote
1answer
22 views

If $P(\cup_{i\in\mathbb{N}}A_{i}) = \sum_{i\in\mathbb{N}} P[A_{i}]$, prove that A_{i} are almost disjoint.

I started with the inclusion exclusion principle. Let $B_{1} = A_{1}, B_{2}=A_{2} - A_{1}, \ldots , B_{n} = A_{n} - (\cup_{i=1}^{n-1}A_{i})$ So, $A_{n} = B_{n} \cup (\cap_{i=1}^{n-1}A_{i})$. We ...
0
votes
0answers
14 views

Help showing an inclusion exclusion identity in an arbitrary measure space

Let $(X,M,\mu)$ be a some measure space (NOT necessarily finite) and denote $I := \{1,2,\ldots,n\}$. I'm having an incredible amount of trouble proving that for any collection of $n$ sets in $M$, the ...
4
votes
2answers
46 views

Ways to Arrange 7 things given restrictions

Let's say you have three $z$'s, two $x$'s, and two $y$'s. How many ways are there to arrange those $7$ variables given that $x$ and $y$ cannot be together? Ex: $zxzxzyy$ and $xxzzzyy$ are valid ...
5
votes
2answers
70 views

Find the thousandth number in the sequence of numbers relatively prime to $105$.

Suppose that all positive integers which are relatively prime to $105$ are arranged into a increasing sequence: $a_1 , a_2 , a_3, . . . .$ Evaluate $a_{1000}$ By inclusion exclusion principle I ...
1
vote
1answer
48 views

Number of functions $f: A \to A$, where $A$ is a set with $8$ numbers, such that $f(i) = j \iff f(j) = i$

The condition is existence of $i = f(j) \leftrightarrow j = f(i)$, for every $i,j$. I tried to solve it with inclusion-exclusion, when the condition is made for single $i,j$, and then for $i_1,j_1$ ...
1
vote
2answers
85 views

Draw $13$ cards out of $52$ with one suit missing

Here’s a probability problem which is causing me some trouble: In a deck of $52$ cards, in how many ways can you draw $13$ cards such that at least one suit is missing. What I've done at first was:...
2
votes
2answers
63 views

If $n$ numbers are generated, what is the probability that the product of all those numbers is a multiple of 10?

A computer generates random numbers from the set $\{1,2,3,4,5,6,7,8,9\}$ (each has equal probability). If $n$ numbers are generated (with replacement), what is the probability that the product of all ...
0
votes
1answer
36 views

Inclusion exclusion involving distribution.

This question was in my book in the inclusion-exclusion principle section. I really don't see how to apply it here. Any tips? A candy maker distributes 3 types of coupons in the packages of Breakfast ...
1
vote
2answers
44 views

Number of bit strings of length four do not have two consecutive 1s

I came across following problem: How many bit strings of length four do not have two consecutive 1s? I solved it as follows: Total number of bit strings of length: $2^4$ Total number of ...
2
votes
3answers
57 views

Inclusion–exclusion principle problem

172 business executives were surveyed to determine if they regularly read Fortune, Time, or Money magazines. 80 read Fortune, 70 read Time, 47 read Money, 47 read exactly two of the three magazines, ...
0
votes
0answers
20 views

Find number of matrices $B$ with no common row and no common column with a given matrix $A$

We are given a matrix $A$ with $n$ rows and $n$ columns and it's elements are $1,2,...,n^2$ (each element appears once). Find the number of matrices $B$ whose elements are $1,2,...,n^2$ that does not ...
0
votes
1answer
40 views

Arranging the $26$ English letters in a row given two constraints

In how many ways can we arrange the $26$ English letters in a row so that no two vowels are adjacent to each other, and each block of consonant(s) (between $2$ vowels) is/are in alphabetical order?...
4
votes
1answer
117 views

How many numbers between $1$ and $999,999$ inclusive have exactly two of the digits $1, 2, 3$ and $4$ at least once?

How many numbers between $1$ and $999,999$ inclusive have exactly two of the digits $1, 2, 3$ and $4$ at least once? I am just not too sure where to start on this one. Does anyone have any hints on ...
5
votes
3answers
45 views

Why are there $2^n-1$ terms in the inclusion-exclusion formula of $n$ sets?

Why are there $2^n-1$ terms in the inclusion-exclusion formula of $n$ sets? An example of what I mean by inclusion-exclusion formula is this: There are three sets (i.e. $n$ $=$ $3$): $A, B,$ and $C$....
1
vote
1answer
65 views

What is the number of possibilities to choose $~80~$ numbers out of the set $~\{10,11,\cdots,99\}~$ with repetition and no order significant

What is the number of possibilities to choose 80 numbers out of the set $~\{10,11,\cdots,99\}~$ with repetition and no order significant. In which if an element that divides by $10$ with no Remain of ...
2
votes
3answers
73 views

Number of solutions to the equation $x_1+x_2+x_3+x_4=19$ with $0\leq x_i\leq 8$

Find the number of solutions to the equation $x_1+x_2+x_3+x_4=19$ with $0\leq x_i\leq 8$. I know that I should use inclusion-exclusion, but I don't quite see why. If I had this problem: Find the ...
0
votes
0answers
20 views

Permutations using PIE or recursion

I can sense that this problem can be either done by principle of inclusion exclusion or by recurrence relation but I am not able to form a path to get to the answer. May be I am doing something wrong. ...
2
votes
2answers
49 views

Show that the number of elements of $X$ belonging to a least $r$ equals to $\sum_{k=r}^n(-1)^{k-r}{k-1\choose r-1}S_k$

Show that the number of elements of $X$ belonging to a least $r$ of the sets $A_1,\ldots,A_n\subset X$ is $$\sum_{k=r}^n(-1)^{k-r}{k-1\choose r-1}S_k.$$ $S_k$ is defined here as: $$ \sum_{1 \le i_1 &...
0
votes
1answer
51 views

Number of graphs on $V = \left \{ 1,2,3,4,5 \right \}$ such that ${\rm deg}(1) ={\rm deg}(2)=2$

I was trying to solve this by calculating different instances, for example - there is an edge between $\left\{ 1,2\right\}$ or if there isn't. I think that the right way of solving this is by using ...
0
votes
1answer
42 views

Combinatorics Inclusion-Exclusion problem with matrix

Let A $\in$ $M_{n}$ (a matrix) with the numbers 1, 2, ..., $n^2$ in it (each number appears once). How many matrices B $\in$ $M_{n}$ with each of the numbers 1, 2,..., $n^2$ once there are such that ...
1
vote
1answer
45 views

Combinatorics Inclusion-Exclusion problem with permutations and derangements

Let $n \ge$ 3 ($n \in \mathbb{N}$). How many permutations $\sigma [n] \to [n]$ there are such that: $\forall i: \sigma (i) \ne i$, $\sigma (1) = 2$, $\sigma (2) = 3$. I know that I'm supposed to ...
1
vote
1answer
66 views

How many pairs $(A_1, A_2)$ of subsets of $\{1,2,\ldots,n\}$ are there such that $A_1 \cap A_2 = \emptyset$?

How many pairs $(A_1, A_2)$ of subsets of $\{1,2,\ldots,n\}$ are there such that $A_1 \cap A_2 = \emptyset$? I am to give a solution involving binomial coefficients. The hint I was given is to ...
0
votes
1answer
33 views

Probability of not receiving a specific toy in a cereal box, but receiving all others

Saw this discussion and I can't understand the answer. Let's say there are 90 unique toys, and a child has a specific one that he wants to get. He opens 225 boxes of cereal to receive this specific ...
1
vote
0answers
27 views

Number of lattice points bounded by lines on plane.

There are given following lines on plane: $A: x=0$ $B: y=0$ $C_{i}:y=a_{i}x+b_{i}$ for $1\le i \le n$ so that these lines intersect with first two lines ($x=0,y=0$) at non-negative coordinates. Let $...
1
vote
0answers
32 views

cardinality of the symmetric difference of m sets where the symmetric difference for each two sets is greater than or equal to 1 [closed]

We given $n$ sets: $A_1,A_2,...,A_n$ such as $\forall A_i,A_j$, $1 \le i,j \le n$, $\left|A_i\Delta A_j \right| \ge 1$ where $\Delta$ denotes the symmetric difference. we are looking for $\left|...
0
votes
0answers
29 views

what do we call the events that one of them is subset of the other

how to describe the relationship (exclusive, inclusive,.. etc) between two events that one is a subset of the other? example: if 'event 1' happened then 100% 'event 2' have happened.
2
votes
2answers
59 views

Number of integers $n$ between 1 and 1000 such that the HCF of $n$ and $36$ is 1

How many integers $n$ are there such that $1< n < 1000$ and the highest common factor of $n$ and $36$ is $1$? I have tried counting the prime numbers up to $1000$ using the prime-counting ...
0
votes
0answers
23 views

Inclusion Exclusion on Multinomial Coefficient

$$ S=\sum_{A+B+C+D=N}{N\choose A,B,C,D},$$ where $A \geq a$, $B \geq b$, $C \geq c$, $D \geq d$ Is there a way to find $S$ using inclusion-exclusion?
1
vote
1answer
32 views

How many labeled rooted trees are there on 12 nodes where no node has exactly 4 children?

Problem: How many labeled rooted trees are there on 12 nodes where no node has exactly 4 children. I thought to use the principle of inclusion-exclusion. Let $N_i$ be the set of rooted labeled ...
1
vote
0answers
28 views

Inclusion–exclusion principle, find the number of students

There are ten students. Eight of them have travelled to Europe, seven of them speak Spanish and six of them study math. How many students have travelled to Europe, speak spanish and study math? Well, ...
2
votes
1answer
135 views

How many numbers with no common divisor are there?

There is quite general question. Let $A=\{1,2,3,...,n\}$ be a set. Calculate the following: $$W_{k}=\sum_{\substack{a_{1},...,a_{k}\in A\\ a_{i}\neq a_{j} \text{ if }i\neq j\\ \gcd(a_{1},...a_{k}...
0
votes
1answer
41 views

Probability that the given students are not sitting adjacent to each other

Please note that I am not looking for a complete answer, but only hints on how to start. If you want to add a complete solution to help others who might want to know it, please put it in spoiler tags ...
0
votes
1answer
40 views

How how many options are there to put the letters AAAABBBBCCCC (4 A, 4 B, 4 C) in a word so that there are at least 2 A next to each other?

how many option there are to put the letters AAAABBBBCCCC (4 A, 4 B, 4 C) in a word so that there are 2 A next to each other? for example AAAABBBBCCCC counts as an option. is there a way to think ...
0
votes
2answers
49 views

Inclusion-exclusion with anagrams

How many are the permutations of the letters of the word PROPOR in which are not consecutive letters equal? How to approach this problem through the principle of inclusion-exclusion?
0
votes
1answer
42 views

Principle of inclusion exclusion

In a class of 30 children, 20 studied Portuguese, 14 studied English and 10 studied French. If 8 study none of these 3 languages ​​and none study the 3 languages, how many children study English and ...
0
votes
1answer
48 views

Proof of $A_3(n)$ in Stanley's Enumerative Combinatorics Exercise 14, Chapter 2

The question is stated as follows: Let $A_k(n)$ denote the number of $k$-element antichains in the Boolean algebra $B_n$, i.e., the number of subsets $S$ of $2^{[n]}$ such that no element of $S$ is ...
0
votes
3answers
75 views

What is the Inclusion-Exclusion Principle for five sets?

Anyone know where I can find the Inclusion-Exclusion Principle for five sets? I tried to use google but found nothing. Inclusion-Exclusion Principle for 4 sets are: \begin{align} &|A\cup B\cup C\...
0
votes
3answers
66 views

Inclusion Exclusion Problem: $x_1 + x_2 + x_3 = 17$ subject to the restrictions that $x_i \leq 7$, $1 \leq i \leq 3$

How many solutions are there to $x_{1} + x_{2} + x_{3} = 17 $ where $x_{i} \leq 7$ for $1\leq i \leq 3$ This problem and solution comes from this youtube video: https://www.youtube.com/watch?v=...
0
votes
2answers
25 views

Inclusion-exclusion Principle for three different sets

Given three set $A$, $S$, and $L$. How to prove that $$|A\cap S'\cap L'|=|A|-|A\cap S|-|A\cap L| + |A\cap S\cap L|$$ by using inclusion exclusion principle ? (without the aid of Venn Diagram)
0
votes
0answers
36 views

Inclusion-Exclusion Principle for “ONLY” case.

There was 50 students to choose among three courses Maths, Science and Arts. Here is the information given. 30 choose Arts. 12 choose Science. 10 choose both Arts and Science. 8 choose Arts and ...
3
votes
1answer
36 views

Proving that the intersection of closed convex sets is nonempty

This question comes from Section I Chapter 7 of Barvinok's "A Course in Convexity". The statement is as follows: Let $A_1,A_2,A_3\subset\mathbb{R}^d$ be closed convex sets such that $A_1\cap A_2\...
0
votes
1answer
38 views

Given an infinite set of events, prove that the probability of an event is smaller than $1$

I have two infinite sets of events $A$ and $B$ with the following probabilities: $P(A_n)=\frac{2}{6n-1}$ $P(B_n)=\frac{2}{6n+1}$ Note that I have divided them into two sets only because it is easier ...