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
2
votes
3answers
108 views

In how many ways can $4$ of $100$ people sitting at a circular table be selected so that no two of them are adjacent?

At a circular table for $100$ persons, $4$ people will shake hands with each other. How many ways are there to choose $4$ people in that group so that there are no person who shakes hands sits ...
-2
votes
3answers
83 views

Calculating the number of ways a surjective function can be defined. [closed]

The image above contains the questions with their solutions. I'm really not quite sure how they arrived with $36$ in case of answer (e). I don't understand why the $3$ is multiplied to $16$ and ...
3
votes
1answer
712 views

How to calculate the number of graphs without vertices of degree 0 using inclusion-exclusion principle?

So there is this homework question where we have to determine the number of graphs with no vertices of degree 0 using the inclusion-exclusion principle. With $V = {1, 2, ... n}$ and the answer should ...
0
votes
2answers
32 views

How many households have both treadmill and exercise bike? (Venn Diagram problem)

Full question: Suppose that among 1000 households surveyed, 30 have neither an exercise bicycle nor a treadmill, 50 have only an exercise bicycle, and 60 have only a treadmill. How many households ...
5
votes
1answer
1k views

What is the possibility that at least one digit will not show up in a 20-digit “code”?

A "code" is composed of 20 digits (numbers from 0 to 9), and we want to choose a number randomly. What is the possibility that at least one digit will not show up in the code? What I did: We have $10^...
1
vote
2answers
93 views

One hundred identical tennis balls are to be distributed among 10 children. In how many ways can this be done so that no child gets more than 20 balls

One hundred identical tennis balls are to be distributed among 10 children. In how many ways can this be done so that no child gets more than 20 balls. So what I got so far is that we need to ...
1
vote
2answers
77 views

What is the value of $|A \cap B|$? [closed]

For $A$ and $B$ sets, $|B \times (A \cup B)| = 108$, $|A - B| = 3$ and $|B-A| = 5$ What is the value of $|A \cap B|$? I see that there's cartesian product. What should I think?
2
votes
1answer
61 views

Using IE-principle to obtain this outcome

I'm working on a problem, where 4 people enter a room with 100 seats, and each of these four people has their own chair. However, they seat randomly, so with $\mathbb{P}(\mathrm{own \ chair})= \mathbb{...
12
votes
2answers
124 views

An application of the Inclusion Principle to Chemistry? (Proof Verification)

Background I’m taking chemistry and one thing they have us do is draw Lewis structures for molecules. Guessing if there are going to be double or triple bonds is kind of annoying. I’d like to be able ...
0
votes
1answer
348 views

Arranging distinct books of three different subjects so that no two books of the same subject are adjacent

How many ways are there to arrange 3 physics books, 3 math books and 3 chemistry books so that no two books of the same subject are next to each other. All the books of the same subject are distinct. ...
0
votes
1answer
36 views

Number of handshakes - exclusion apporach

5 indian and 5 american couples meet at a party and shake hands. If no wife shakes hands with her husband and no indian wife shakes hands with a male, then the number of hand shakes that take place at ...
0
votes
1answer
56 views

A problem about combination with inclusion exclusion principle

There are 5 groups, let's say group A, B, C, D E. In each group, you can pick several numbers from 0 to 9. With these 5 groups, we can pick 1 number from each group, and come up to 1 sequence. The ...
3
votes
2answers
2k views

Number of 8-digit Passwords with at least 1 digit and/or 1 symbol

I think I know how to calculate the number of 8-digit passwords with 1 digit or 1 symbol. The sets are lowercase (26), uppercase (26), symbols (32), digits(10). That means there are $(26 + 26 +32 + 10)...
2
votes
2answers
55 views

help verifying answer to inclusion/exclusion on strings example

So I'm trying to learn inclusion/exclusion but am having a hard time understanding this example. How many strings of length 6 over the alphabet ${A, B, C}$ start with a $C$ or end with a $C$? So I ...
0
votes
1answer
64 views

Finding the number of solutions for an equation using Principle of Inclusion and Exclusion

Given that $$x_1 + x_2 + x_3 + x_4 + x_5 = 30$$ find the number non-negative integer solutions which satisfy the restrictions $x_1 \leq 5$ and $x_2 \geq 7$. I found the number of solutions when ...
2
votes
4answers
131 views

Number of surjective functions $f:X\rightarrow Y$ where $|X| = n,|Y| = 3$.

Let $f:X\rightarrow Y$ be a function where $|X| = n$ and $|Y| = 3$. I think it is $n(n-1)(n-2)$ since for the first element in $Y$, I pick out of $n$ possible elements that map to this first ...
0
votes
1answer
295 views

Terminology question about containment relation between sets

I am not a mathematician and I need your help about naming a relation holding between subsets that are in a particular relation to one another. (For the fact that I am not a mathematician and hence my ...
1
vote
1answer
141 views

Counting :- Inclusion exclusion principle

Out of a group of $21$ persons, $9$ eat vegetables, $10$ eat fish and $7$ eat eggs. $5$ persons eat all three. How many persons eat at least two out of the three dishes? My approach:- $N(A∪B∪C)=N(A)+...
2
votes
1answer
44 views

Find an expression for $|S-\{A_1\cap A_2\cap \dots \cap A_n\}|$ for $ A_1,\, A_2, \dots , A_n\subset S$

Find an expression for $|S-\{A_1\cap A_2\cap \dots \cap A_n\}|$ for $ A_1,\, A_2, \dots , A_n\subset S$ . and we assume the knowledge of the size of the union of any number of $ A_i$'s but not of the ...
3
votes
3answers
60 views

Show that $\sum\limits_{P\subseteq S}(-1)^{n-|P|}\left(\sum\limits_{a\in P}a\right)^n=n!\prod\limits_{a\in S}a$, where $n=|S|$

I want to prove the following: $$\sum_{P\in 2^S}(-1)^{n-\mid P\mid}(\sum_{a\in P}a)^n = n!\prod_{i=1}^na_i$$ where $S = \{a_i\mid i\in [n]\}$ which is a multiset of positive integers. It is pretty ...
1
vote
0answers
19 views

Number of Permutations of the Set $\{x_1, x_2, … , x_n, y_1, y_2, … y_n\}$ where $x_i, y_i$ are not next to each other

I'd like to find the number of permutations of the set $$\{x_1, x_2, ... , x_n, y_1, y_2, ... y_n\}$$ where that $x_i, y_i$ are not consecutively located for each $i \in[n]$ solution Let $A_i$ be ...
1
vote
0answers
36 views

Proof of $\sum_{r=0}^n(-1)^{n-r}\binom{n}{r}r^n = n!$ [duplicate]

I want to provide proof for the following equation: $$\sum_{r=0}^n(-1)^{n-r}\binom{n}{r}r^n = n!$$ I think it resembles the typical way of representing the Principle of Exclusion & Inclusion: $$...
2
votes
1answer
35 views

Proof make use of Principle of Inclusion and Exclusion

I am trying to prove the equation below with P.I.E : $$\sum_{i=0}^{n}(-1)^n\binom{n}{i}\binom{m+n-i}{k-i} = \binom{m}{k}$$ First RHS is quite simple, i.e., choosing k among m, and then move to LHS, ...
1
vote
2answers
287 views

Set theory problem with the inclusion-exclusion principle

I started learning set theory, but as for the begin firstly I'm having problems with some notations. From the lectures we learned about this principle which is as following: 1.$$ |A \cup B|= |A|+|B|$$...
0
votes
1answer
53 views

How to find how many students passed both exams?

Here is my question In a class which has $36$ students, there are $26$ students who passed math and $20$ students who passed physics exam and $4$ students couldn't pass the both subjects. Then,...
2
votes
1answer
50 views

Find the value of $\mathop{\sum\sum\sum\sum}_{0\leq i \leq j \leq k \leq l\leq n} 1$

Find the value of $$\mathop{\sum\sum\sum\sum}_{0\leq i \leq j \leq k \leq l\leq n} 1$$ I am not sure but perhaps the answer is ${n+5}\choose 5$. We know that $\displaystyle\mathop{\sum\sum\sum\sum}...
1
vote
0answers
82 views

Combining letters with the inclusion exclusion principle problem

In every detergent box there is one of these three letters, $(H,M,O)$. The three letters are found with the same probability. What is the probability of making the word $HOMO$ buying ten detergent ...
-2
votes
2answers
520 views

Solving dice problem using the inclusion-exclusion principle [closed]

We roll a die ten times. What's the probability of getting all the six different numbers of the dice? If $A_i$ is the event of getting at least of the numbers from $i=1$ to $6$. What the problem is ...
1
vote
1answer
136 views

Extended Inclusion/Exclusion Principle

I have been working on this problem for a while but couldn't find the general formula Let $$P(A_k) = \frac{1}{k+1}, \forall k\geq 1$$ Find: $$P(\bigcup_{k=1}^{n}A_k)$$ Knowing that all $A_k$ ...
1
vote
2answers
44 views

Inclusion-exclusion principle: Die thrown 10 times

Question: Use inclusion-exclusion to calculate the probability that the numbers 1,2 and 3 each appear at least once when a die is thrown 10 times. My attempt: $(6^{10}-3.5^{10} +3.4^{10}-3^{10})/6^{...
0
votes
1answer
60 views

Why does finding the union of these three sets yield a negative number?

I've been working on a homework problem that I can't seem to be able to solve. The question states: Suppose 25 people attended a conference that contains 3 sessions. 15 people attended session #1; ...
1
vote
3answers
199 views

How am I using the inclusion-exclusion principle wrongly?

I was trying to solve this problem (taken from Harvard's Stat 110 class) using the inclusion-exclusion principle: A city with 6 districts has 6 robberies in a particular week. Assume the robberies ...
1
vote
2answers
36 views

Counting permutations of distinct items with repetition allowed and compulsory inclusion of some items

I have following problem: I have five elements $\{a,b,c,d,e\}$. I have to form ordered group of three elements out of these five elements. at least one or both of $a$ and $b$ should appear in the ...
7
votes
3answers
1k views

How to approach this counting problem?

Let $n ≥ 1$ be an integer. A function $f : \{1, 2, \ldots , n\} \to \{1, 2, \ldots, n\}$ is considered "valid", if there is at least one integer $i$ in $\{1, 2, \ldots, n\}$ for which $f(i) = i$. ...
1
vote
2answers
863 views

Inclusion–exclusion principle and permutations / derangements

In order to practice the Inclusion–exclusion principle and permutations / derangements, I tried to develop an exercise on my own. Assume there are $6$ players throwing a fair die with $6$ sides. In ...
1
vote
1answer
331 views

Possible ways of putting 7 balls into 3 boxes

We have 7 balls each of different colors (red, orange, yellow, green, blue, indigo, violet) and 3 boxes each of different shapes (tetrahedron, cube, dodecahedron). How many ways are there to place ...
4
votes
0answers
131 views

Find the number of $n$ husband's placing

Let there be $n$ pairs of husband-wife, and a round table with $2n$ chairs. Suppose that $n$ wives are already sat down, and between any two neighboring wives there is exactly one free chair (there is ...
2
votes
2answers
225 views

Card Probability using inclusion exclusion

You are dealt $13$ cards from a shuffled deck of $52$ cards. Compute the probability that you get all four cards of at least one denomination (all Aces, or all Kings, or all Queens, . . . , or all ...
0
votes
0answers
89 views

If an element x of S satisfies exactly r of the t conditions, how many times is x counted in the following expressions?

Use the standard notation for Inclusion-Exclusion ($S$ is a set of $N$ elements, ${c_1} {c_2} ...{c_t}$ are conditions on the elements of $S$, and $N({c_i}_1 {c_i}_2...{c_i}_m)$ is the number of ...
3
votes
0answers
115 views

How many permutations of the letters: DREAMORTEAM do not have identical consecutive letters?

I tried to do do this using inclusion-exclusion principle, and got something like this: $ \frac{11!}{2!2!2!2!} -\binom{4}{1} \frac{10!}{2!2!2!}+\binom{4}{2} \frac{9!}{2!2!}-\binom{4}{3} \frac{8!}{2!} ...
5
votes
2answers
128 views

Number of permutations of $9$ people of three nationalities in which no two people of the same nationality are adjacent

$9$ different people must be put in a row. Three of them are of nationality $X$, three are of $Y$, and the remaining three are of $Z$. In how many combinations there will be no two people of the ...
2
votes
1answer
62 views

How can I write this in a different ways? $\vert(\bigcup_{i=0}^n Ai)\vert$ [closed]

I'm trying to write this equation in a more compressed way. For me, I think it would contribute a lot to my practice to see different ways of writing the same identity. How can I write this in a ...
0
votes
1answer
94 views

I need help in proving an identity about the Inclusion exclusion principle

I need to prove the following identity: $$ 1 = \sum_{k=0}^n \sum_{i=0}^k \frac{(-1)^i}{(n-k)!i!}$$ The solution has to do with the Inclusion exclusion principle.
1
vote
2answers
209 views

A question about permutations without fixed point

I need to find how many permutations $f:[n]\to [n]$ exist that answer the following conditions: For every $i$: $f(i) \neq i$ $ f(1)=2, f(2)=3$ Notes: Here $[n] = \{x| 1 \le x \le n\}$. ...
-2
votes
1answer
52 views

How many students are not enrolled in any of these three courses?

55 people are enrolled in courses of the Diploma of Information Technology. While 35 are registered in OOP, 23 in BD, 27 in SAP, 15 in OOP and SAP, 9 in SAP and BD, 12 in OOP courses and BD and, ...
1
vote
2answers
242 views

Use inclusion/exclusion to find the number of derangements of the string aabbcc

There is a problem exactly like the one I asked, however I am still stuck and still need help. So I tried to edit the question with the work you see below before deciding to ask this question again, ...
4
votes
1answer
192 views

Find the number of rearrangements of the string 12345 in which none of the sequences 12, 23, 34, 45, and 51 occur.

So I posted a similar problem before, so please don't try to close this problem. Anyway I think I did this problem correctly, but I just want to make sure if I'm understanding what this question is ...
1
vote
1answer
129 views

Find the number of rearrangements of the string 123456 in which none of the sequences 123, 321, 456, and 654 occur.

My attempt: Let $A_{1}$ denotes where 123 occurs, $A_{2}$ denotes where 321 occurs, $A_{3}$ denotes where 456 occurs, and $A_{4}$ denotes where 654 occurs. Also $|U|$=6! $$\begin{...
0
votes
2answers
152 views

Use inclusion/exclusion to find the number of derangements of each of the following strings. [duplicate]

a) aabcd (already answered) b) aabbcc There is a problem exactly like the one I asked, however I am still stuck and still need help. Here is my attempt Let A denotes where aa occurs, B denotes ...
0
votes
2answers
290 views

Find the number of seven-letter words that use letters from the set $\{\alpha, \beta, \gamma\}$

Find the number of seven-letter words that use letters from the set $\{\alpha, \beta, \gamma\}$ and contain at least one $\alpha$ and at least two $\beta$'s. I posted a similar problem before, in ...