# 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.

881 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
1k views

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 ...
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. ...
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 ...
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 ...
2k views

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 ...
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 ...
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 ...
36 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 ...