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.

877 questions
77 views

The number of sequences of length $2n$ that can be formed with digits from set $A={1,2, … ,n}$ and…

I've been struggling with the following exercise: Find the number of sequences of length $2n$ that can be formed with digits from set $A={1,2, ... ,n}$ where every digit has to appear exactly twice ...
88 views

The number of sequences of length $10$ that can be formed with $5$ unique digits containing two of each where no two adjacent elements are alike

We have $5$ unique digits. For the sake of simplicity let's say that these are $0$, $1$, $2$, $3$ and $4$. We want to find the number of such sequences built using these numbers that: Two adjacent ...
33 views

Sets of students, unions, complements, intersections

There are 93 students in the class; 42 like Math, while 41 like English. If 30 students don't like either subject, how many students like both? A.10 B.20 C.41 D. The answer cannot be determined ...
168 views

Derangement formula for multisets

The usual derangement formula, for permutations of $\{1,\dots,n\}$ without fixed points, is given as follows: $$\sum_{i=0}^n (-1)^{n-i}i!\binom{n}{i} = D(n)$$ Richard Stanley, in his Enumerative ...
58 views

Seemingly negative set cardinality in textbook

So in a textbook, the question states: There are 90 students and each of them must study at least one of Biology, Physics, or Chemistry. There are 36 students who study Biology, 42 who study Physics, ...
54 views

75 views

How many trees on $\{1,2,3,4,5,6,7\}$ have a vertex of degree 2?

How many trees on $\{1,2,3,4,5,6,7\}$ have a vertex of degree 2 ? Attempt - It feels like an inclusion exclusion problem (using kailey's code) , let's define $|A_i| \Rightarrow$ vertex $i$ is of ...
132 views

156 views

How many ways are there to arrange 4 Americans, 3 Russians, and 5 Chinese into a queue, using inclusion-exclusion principle?

How many ways are there to arrange 4 Americans, 3 Russians, and 5 Chinese into a queue, in such a way that no nationality forms a single consecutive block? Let $A$ be the collection of ways that $4$ ...
67 views

how many ways are there to order the word LYCANTHROPIES when C isn't next to A, A isn't next to N and N isn't next to T

a. total number of ways to order 13 letters in a word: 13! b. Number of ways for CA/AC: 2*12! Number of ways for AN/NA: 2*12! Number of ways for NT/TN: 2*12! Total: 3*2*12! c. Number of ways ...
125 views

95 views

Finding number of patients with all three complaints

In a survey of the 100 out-patients who reported at a hospital one day, it was found out that 70 complained of fever, 50 complained of stomach ache and 30 were injured. All 100 patients had at least ...
47 views

Given 3 sets $|A|=6, |B|=4, |C|=3$ and $C \subseteq B$. Calculate the size of the set: $\{f\in A\to B$ $| C\subseteq Imf\}$

Given 3 sets $|A|=6, |B|=4, |C|=3$ and $C \subseteq B$. Calculate the size of the set: $\{f\in A\to B$ $| C\subseteq Imf\}$ Please let me know if you have any idea on how to solve this. Thank you
53 views

Is there a way to solve it by using exclusion-inclusion method

How many functions $f:\{1,2,3 \cdots n\} \rightarrow \{1,2,3 \cdots n\}$ have no fixed points? Is there a way to solve it by using exclusion-inclusion method?
297 views

Relation between inclusion-exclusion principle and maximum-minimums identity

Inclusion-exclusion principle states that the size of the union of $n$ finite sets is given by the sum of the sizes of all sets minus sum of the sizes of all the pairwise intersections plus sum of the ...
2k views

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 ...
55 views

How many words with $N$-characters can be formed from the numbers $\{0, 1, 2\}$, such that adjacent numbers have maximum difference 1? [duplicate]

How many words with $N$-characters can be formed from the numbers $\{0, 1, 2\}$, such that adjacent numbers have maximum difference $1$? Example: For $N = 2$ there are $7$ words that can be formed:...