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.

909 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
32 views

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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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:...
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 ...
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 ...
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 ...
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, ...
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 ...
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?...
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 ...
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$....
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 ...
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 ...
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. ...
49 views

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 ...
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 ...
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?
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 ...
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 ...
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\...
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=...
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)