Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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, ...
2
votes
1answer
54 views

Closed form or limiting form of an expression involving binomial coefficients

This question leads to an application of the inclusion‒exclusion principle leading to this sum: $$ \sum_{k=0}^n (-1)^k \binom n k (n-k)^x = (-1)^n \sum_{k=0}^n (-1)^k \binom n k k^x $$ $$ \text{e.g. } ...
1
vote
1answer
160 views

Number of directed graphs without isolated vertices

I need to count the number of simple directed graphs, with n vertices, without isolated vertices. There is additional note in task saying that we assume that two graphs are different if there are two ...
1
vote
2answers
105 views

ternary string using the Inclusion-Exclusion

Use the Inclusion-Exclusion Principle to determine how many ternary strings of length five contain two consecutive $1$s.(explain your answer) My attempt was to get the string that has all ones. ...
1
vote
3answers
129 views

Difference between membership and inclusion

I've taken the definition of membership to be the following: Membership $A \in B: A$ is one of the members of $B$. However, I'm not sure where to make the distinction between membership and ...
1
vote
1answer
43 views

Derivation of $\frac{1}{{p}_{1}\, {p}_{2}\, \cdots\, {p}_{m}} \prod\limits_{i = 1}^{m} \left({{p}_{i} - 1}\right)$ from reciprocal sum expansion

How to show that \begin{equation*} \begin{pmatrix} 1 - \sum\limits_{i = 1}^{m} \frac{1}{{p}_{i}} + \sum\limits_{1 \le i < j}^{m} \frac{1}{{p}_{i}\, {p}_{j}} - \sum\limits_{1 \le i < j < k}^...
1
vote
3answers
137 views

Suppose that events $A$, $B$ and $C$ satisfy $P(A \cap B \cap C) = 0$ and each of them has probability not smaller than $\frac{2}{3}$. Find $P(A)$.

Suppose that events $A$, $B$, and $C$ satisfy $P(A \cap B \cap C) = 0$ and each of them has probability not smaller than $\dfrac{2}{3}$. Find $P(A)$. I don't understand this statement: $A \cap B$, ...
1
vote
1answer
441 views

Find the number of ways when $4A, 1B, 1C, 1D$ is distributed among $4$ students with a few conditions

And one of the answers I saw was along the following lines: By Principle of Inclusion-Exclusion, it follows that $4^3({4\choose 3}-4)-4\cdot3^3({6\choose 2}-3)+6\cdot 2^3 ({5\choose 1}-2) =832$. ...
2
votes
0answers
41 views

Unique pairings with repeated elements

I am looking for a generalization of the formula for the number of unique pairs of a list of elements to the case where there are multiple copies of each element. First a review of the standard ...
1
vote
4answers
280 views

Numbers up to 1000 divisible by 2 or 3 and no other prime

My task requires to find all numbers from $1-1000$ such that they are divisible by $2$ or $3$ and no other primes. I know that $2$ divides even numbers and I can use the formula $\left \lfloor{\frac{...
1
vote
1answer
41 views

Counting the equal-differences of an permutation

I'm interesting in calculating how many permutations of $[n]$ have a consecutive difference (in absolute value) equal. For instance if $n=6$ the permutation $613425$ have common difference $2$ because ...
1
vote
1answer
46 views

How many solutions to $x + y = z$ for $x,y \in [1,n]$ and $n > 1$ in general, closed form.

To restate the constraints, I have $x,y$ as strictly positive integers not exceeding $n$. As a result, the number of solutions will be nonzero on the range $z \in [2, 2n]$. My first reaction was to ...
1
vote
1answer
63 views

Size of union of sets when intersection is empty

Suppose $X$ is a space with measure $\mu$, and $\{A_i\}$ are measurable sets such that $\mu(\bigcap_{i = 1}^n A_i) = 0$, $n>1$. Is it true that $ \mu(\bigcup_{i = 1}^n A_i) \geq \frac{\sum_{i=1}^n \...
0
votes
0answers
36 views

Inclusion Exclusion to find multiples

so I have an assignment to write a program that calculates multiples using inclusion exclusion however I am having a little trouble understanding the math. The program is that given two integers a, ...
1
vote
1answer
31 views

Trees on $\{1,2,3,4,5,6,7,8\}$ with conditions

1) How many trees on these vertex have at least 2 leaves ? 2) How many trees on these vertex have more than 2 leaves ? Attempt - I will use inclusion-exclusion for both cases - $1)$ $$\binom{...
4
votes
2answers
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 ...
2
votes
1answer
132 views

Inclusion-exclusion, Injections, Surjections

If $X = \{1, 2, 3\}$ and $Y = \{1, 2, 3, 4, 5, 6\}$, how many injections are there from $X$ to $Y$? How many surjections are there from $Y$ to $X$? For the injections from $X$ to $Y$ there should be $...
1
vote
1answer
23 views

Possible hands in a deck of cards

In a deck of cards there are $52$ different cards. Out of which $4$ jacks, $4$ queens, $4$ kings and $4$ aces. Assuming a valid hand is composed by any $13$ cards. In how many different hands there ...
1
vote
1answer
82 views

Arranging $n$ people around a circular table so that no that no one is to the right of the same person as in the previous seating

A group of $n$ people is seated at a round table. The group leaves the table for a break and then returns. In how many ways can the people sit down so that no one is to the right of the same person ...
0
votes
2answers
122 views

How many ways are there to build a tower of 5 cubes height, out of red, yellow, blue, and green cubes, such that:

How many ways are there to build a tower of 5 cubes height, out of red, yellow, blue, and green cubes, such that at least one of each pair of adjacent cubes is green or blue? Hey everyone. I first ...
0
votes
1answer
75 views

Proving an equality using Inclusion Exclusion Principle [closed]

I found the exact same question that I want to ask here : Proving $\sum\limits_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$ From my understanding this doesn't use Inclusion Exclusion Principle and if it does ...
2
votes
3answers
50 views

6 tests in one month, each must be separated from other tests by 2 free days in between

A university is determining the dates for tests in January. There can be a test on every day in January(all $31 $of them), but each two tests have to have at least $2$ free days in between them. (so ...
2
votes
1answer
63 views

$2n$ students want to sit in $n$ fixed school desks such that no one sits with their previous partner

A classroom has $n$ fixed school desks with exactly $2$ chairs each. There are $2n$ students sitting in the classroom and then they go on a break. After the break they're coming back into the ...
0
votes
2answers
98 views

Suppose that events $A$, $B$ and $C$ satisfy $P(A\cap B\cap C) = 0$ [closed]

Suppose that events $A$, $B$ and $C$ satisfy $P(A\cap B\cap C) = 0$ and each of them has probability not smaller than $\frac{2}{3}$. Find $P(A)$. I'm confused if there is a unique $P(A)$? Thanks!
1
vote
3answers
66 views

combinatorics problem - permutations and e/i

I am hoping that someone can please check my work and let me know if my logic is flawed. I have the string of characters "catvsdog". How many arrangements of this word are there so that "cat" OR "...
0
votes
1answer
204 views

Counting problem involving inclusion-exclusion principle

We're given the following problem: "The number of arrangements where no wife is sitting next to her husband when three married couples are seated together in the cinema (occupying six consecutive ...
1
vote
1answer
39 views

Positive natural numbers $≤ 200$ divisible by one and only one between $12$ and $15$

Calculate how many positive natural numbers $≤ 200$ are divisible by one and only one between $12$ and $15$. My attempt: $B_1=[200/12]=16$ $B_2=[200/15]=13$ $B_1∩B_2=3$ $B_1+B_2+2|B1∩B2|=16+13+6=...
0
votes
1answer
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$ ...
4
votes
2answers
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 ...
2
votes
0answers
125 views

Proving Möbius inversion formula for inclusion exlusion

reading in "Introductory Combinatorics" about Möbius inversion, some questions have arose: 1) Author defines function $$F(K) - \text{# of elements of S that belong to $exactly$ those sets } A_i\text{...
-1
votes
2answers
146 views

how many solutions in natural numbers are there to the inequality $x_1 + x_2 +…+ x_{10} \leq 70$? [duplicate]

how many solutions in natural numbers are there to the inequality $x_1 + x_2 +....+ x_{10} \leq 70$ ? I know it has to be solved with combinatorics and specifically with the inclusion exclusion ...
1
vote
2answers
51 views

Determine how many positive integers are $\leq 500$ and divisible by at least one between $6$, $10$ and $25$

Determine how many positive integers are $\leq 500$ and divisible by at least one between $6$, $10$ and $25$. I used sets to do this exercise. $B_1 = 500/6 = 83$ $B_2 = 500/10 = 50$ $B_3 = 500/25 =...
2
votes
2answers
71 views

Problem on Principle of Inclusion-Exclusion

How many integers $1, 2,....., 11000$ are invertible modulo $880$? $880$ can be rewritten as $2^4\cdot5\cdot11$. So I am supposed to find the number of integers in this range that have $2$, $5$ or $...
0
votes
2answers
155 views

Find the number of sequences of letters: ’AAABBBCCC’ such that: [duplicate]

a)Three identical letters are not next to each other. So I came up with a solution but I have no possibility to check whether it's correct so I've decided to post it here. So |X| - number of all ...
4
votes
5answers
294 views

Count the integer solutions of $x_1+x_2-x_3+x_4-x_5=3$

I am asking for help with solving this exercise: Find the count of possible integer solutions for equation: $$x_1+x_2-x_3+x_4-x_5=3$$ There are restrictions for possible values of $x$: $$ \begin{...
0
votes
1answer
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 ...
0
votes
1answer
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
2
votes
2answers
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?
2
votes
4answers
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 ...
15
votes
3answers
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 ...
2
votes
1answer
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:...
1
vote
0answers
55 views

Inclusion-exclusion related identities

$1.$ Prove $\forall n\in\mathbb{N}\quad n\geq5$$$ n^4-\binom{n}{1}(n-1)^4+\binom{n}{2}(n-2)^4-\binom{n}{3}(n-3)^4+\dots +(-1)^{n-2}\binom{n}{n-2}\cdot2^4+(-1)^{n-1}\binom{n}{n-1}\cdot1^4=0 $$$2.$ ...
2
votes
3answers
107 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
80 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
709 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 ...