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.

0
votes
0answers
22 views

what do we call the events that one of them is subset of the other

how to describe the relationship (exclusive, inclusive,.. etc) between two events that one is a subset of the other? example: if 'event 1' happened then 100% 'event 2' have happened.
2
votes
2answers
44 views

Number of integers $n$ between 1 and 1000 such that the HCF of $n$ and $36$ is 1

How many integers $n$ are there such that $1< n < 1000$ and the highest common factor of $n$ and $36$ is $1$? I have tried counting the prime numbers up to $1000$ using the prime-counting ...
3
votes
2answers
81 views

What is the probability that no cup is on a saucer of the same colour?

A tea set comprises four cups and saucers in four distinct colours. If the cups are placed at random on the saucers, what is the probability that no cup is on a saucer of the same colour? MY ATTEMPT ...
1
vote
1answer
25 views

How many labeled rooted trees are there on 12 nodes where no node has exactly 4 children?

Problem: How many labeled rooted trees are there on 12 nodes where no node has exactly 4 children. I thought to use the principle of inclusion-exclusion. Let $N_i$ be the set of rooted labeled ...
0
votes
0answers
14 views

Inclusion Exclusion on Multinomial Coefficient

$$ S=\sum_{A+B+C+D=N}{N\choose A,B,C,D},$$ where $A \geq a$, $B \geq b$, $C \geq c$, $D \geq d$ Is there a way to find $S$ using inclusion-exclusion?
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)...
1
vote
0answers
22 views

Inclusion–exclusion principle, find the number of students

There are ten students. Eight of them have travelled to Europe, seven of them speak Spanish and six of them study math. How many students have travelled to Europe, speak spanish and study math? Well, ...
2
votes
1answer
118 views

How many numbers with no common divisor are there?

There is quite general question. Let $A=\{1,2,3,...,n\}$ be a set. Calculate the following: $$W_{k}=\sum_{\substack{a_{1},...,a_{k}\in A\\ a_{i}\neq a_{j} \text{ if }i\neq j\\ \gcd(a_{1},...a_{k}...
0
votes
1answer
26 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 ...
0
votes
1answer
33 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 ...
0
votes
1answer
38 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 ...
0
votes
1answer
21 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?
0
votes
3answers
39 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\...
1
vote
1answer
29 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 ...
0
votes
3answers
59 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=...
0
votes
2answers
22 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)
0
votes
0answers
31 views

Inclusion-Exclusion Principle for “ONLY” case.

There was 50 students to choose among three courses Maths, Science and Arts. Here is the information given. 30 choose Arts. 12 choose Science. 10 choose both Arts and Science. 8 choose Arts and ...
6
votes
2answers
3k views

Partitions and Bell numbers

Let $F(n)$ be the number of all partitions of $[n]$ with no singleton blocks. Find the recursive formula for the numbers $F(n)$ in terms of the numbers $F(i)$, with $i ≤ n − 1$ Find a formula for $F(...
3
votes
1answer
26 views

Proving that the intersection of closed convex sets is nonempty

This question comes from Section I Chapter 7 of Barvinok's "A Course in Convexity". The statement is as follows: Let $A_1,A_2,A_3\subset\mathbb{R}^d$ be closed convex sets such that $A_1\cap A_2\...
0
votes
1answer
32 views

Given an infinite set of events, prove that the probability of an event is smaller than $1$

I have two infinite sets of events $A$ and $B$ with the following probabilities: $P(A_n)=\frac{2}{6n-1}$ $P(B_n)=\frac{2}{6n+1}$ Note that I have divided them into two sets only because it is easier ...
0
votes
2answers
78 views

How to apply inclusion - exclusion principle

Let W, X, Y, Z be subsets of {1, 2, . . . , 100} such that W ∩X = ∅, W ∩Y = ∅ and X ∩Y = ∅. Use the inclusion-exclusion principle to write down an expression for |W ∪ X ∪ Y ∪ Z| Based on the ...
3
votes
1answer
52 views

Bijection between “circularly nonconsecutive” permutations and permutations with one fixed point

A permutation $\pi$ of $[n]:=\{1,2,\dots,n\}$ is called circularly nonconsecutive (CNC) if $\pi_{i+1}-\pi_i\neq 1$ for all $i=1,2,\dots,n-1$, and furthermore $\pi_1-\pi_n\ne 1$. In other words, $i+1$ ...
0
votes
0answers
30 views

How can I prove the following equation? I believe it is an application of Inclusion-Exclusion Principle.

$$\sum_Xf_=(X)x^{\#X}=\sum_Yf_{\ge}(Y)(x-1)^{\#Y}$$ I believe it is related to the Inclusion-Exclusion Principle, but how to apply it to the equation? $$f_=(S) : 2^{[n]}\to R $$ $$S\mapsto f_=(S)$$
1
vote
2answers
51 views

Inclusion Exclusion Application

If $A$, $B$, and $C$ are finite sets then, the number of elements in EXACTLY ONE (i.e. at most one) of the sets $A$,$B$,$C$:$$n(A)+n(B)+n(C)-2 \times n(A \cap B)-2 \times n(A \cap C)-2 \times n(C \cap ...
0
votes
2answers
33 views

Number of surjective functions where $f(a) = b$

Let $A,B$ be groups such that $\left | A \right | = 7$ $\left | B \right | = 5$ and let $a\in A$ and $b\in B$ Find the number of onto functions $f:A \mapsto B$ where $f(a) = b$ Using the inclusion -...
2
votes
0answers
33 views

Counting Surjections - Combinatorics

I am working on a combinatoric proving that the number of surjective functions $f\colon [n]\to [3]$ is equal to $1/2(3^{n-1}-2^n+1)$ I approached the problem as below Let’s consider that we have a ...
1
vote
2answers
38 views

Number of one to one functions from the set {1, 2, . . . , n} to {1, 2, . . . , n} so that f(x) = x for some x and f(x) $\neq$ x for all the other x?

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the setm {1, 2, . . . , n} so that f(x) = x for some x and f(x) $\neq$ x for all the other x? Alright so the fact ...
7
votes
3answers
140 views

Computing how many distinct digital products are below $10^n$

Given a number $n$, its digital product is the product of its digit. So the digital product of $15$ is $1\times 5=5$, and the digital product of $760$ is $0$, etc. I recently saw a nice video on ...
1
vote
1answer
39 views

Calculate cardinality of a set

There is given: set $B=A_{1} \cup...\cup A_{n}$ $|A_{i}|=m_{i}$ for each $i$ every element of $B$ belongs to exactly $k$ sets $A_{i_{1}},...,A_{i_{k}}$ Calculate $|B|$ in terms of $m_{i}$. If it ...
2
votes
1answer
62 views

How many solutions does the equation $\sum_{i=1}^{k}{x_i}=c$ have, given that the $x_i\in\mathbb{Z}$ and $0\leq x_i\leq d$?

We are given initially some $k,c,d\in\mathbb{N}$. How many solutions $(x_1, x_2, ..., x_k)$ does the equation $\sum_{i=1}^{k}{x_i}=c$ have, where $x_i\in\mathbb{Z}$ and $0\leq x_i\leq d$?
3
votes
0answers
48 views

Reasoning about remainders and the Möbius function

This one seems counter intuitive to me but I am not seeing a mistake in my reasoning. Please let me know if you find one. Let: $x > 0$ be an integer $\mu(x)$ be the möbius function $x\#$ be the ...
0
votes
1answer
87 views

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x?

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x? Alright so I did see this question, but it really ...
2
votes
1answer
62 views

Is this the correct solution to find a number of one-to-one functions?

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x? If we take $A_{i}$ to be a set of one-to one ...
0
votes
0answers
14 views

Probability of having picked every item from the set at least once after n turns, while picking 3 per turn

Let's say I have a set of 100 items. Each turn, I pick three items at random, note which ones I've picked, and put them back. What is the probability I've picked every item at least once after $n$ ...
10
votes
4answers
6k views

Enumerating number of solutions to an equation

How do you find the number of solutions like this? $$x_1 + x_2 + x_3 + x_4 = 32$$ where $0 \le x_i \le 10$. What's the generalized approach for it?
1
vote
2answers
1k views

Probability when a professor distributes a quiz and homework assignment to a class of n students.

Need help with this problem. Suppose our lazy professor collects a quiz and a homework assignment from a class of n students one day, then distributes both the quizzes and the homework assignments ...
0
votes
1answer
21 views

How do use inclusion-exclusion to find the probability of encountering all n outcomes in m tries

This is a repost as my last post broke some rules. Assume that every time you buy a box of Wheaties, you receive one of the pictures of the n players on the New York Yankees. Over a period of ...
1
vote
1answer
39 views

Combinatorics and composite functions

X, Y, and Z are sets with the cardinality of each set being l, m, and n, respectively with l < m < n. I'm trying to figure out how many possible 1-1 functions there are of the form of f∘g, with ...
1
vote
1answer
59 views

Combinatorics- dividing animals

We have n pairs of different animals (male and female from each species, so each pair is different). How many ways are to divide the $2n$ animals into $n$ different rooms, so in every room there are ...
0
votes
3answers
63 views

Let $n\ge3$ be an integer. How many permutations $f : [n]\to [n]$ are in which $f(i)\neq i$ for each $i\in \{2,3,…,n\}$ and $f(1)=1$, $f(2)=3$?

Let $n\ge 3$ be an integer. How many permutations $f : [n]\to [n]$ are in which $f(i)\neq i$ to each $i \in \{2,3,...,n\}$ and $f(1)=1$, $f(2)=3$? I need to use the Inclusion-exclusion principle but ...
0
votes
0answers
62 views

Sum of a finite series

I was solving a question where I had to find the number of numbers of length N without having any consecutive zeros from the set [0,K-1] for any K. I came up with the following equation using ...
0
votes
0answers
34 views

Asymptotics for the sums from the inclusion-exclusion principle

What is a method to compute the asymptotics of a sum resulting from the inclusion-exclusion principle? Each term of the sum can be approximated perhaps by Sterling's formula or the Gaussian ...
19
votes
5answers
583 views

Inclusion-exclusion-like fractional sum is positive?

Let $A_1,A_2,\ldots,A_n$ be finite nonempty sets. Is it true that $$\sum_{i=1}^n\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup A_j\...
2
votes
2answers
112 views

Find the probability of rolling ten different, standard 6-sided dice simultaneously and obtaining a sum of 30? [duplicate]

Find the probability of rolling ten different, standard 6-sided dice simultaneously and obtaining a sum of 30? I started to answer this question by setting up an equation like this: x1+x2+...+x10=30 ...
1
vote
2answers
42 views

Combinatorics Inclusion-Exclusion

At one school, three computer languages, Basic, FORTRAN, and Pascal are taught. Suppose that for each language 27% of the students know that language, for each pair of languages 12% of the students ...
0
votes
1answer
40 views

Determine the number of 6 digit positive integers such that at least one pair of consecutive digits differs by an odd number.

I noticed that for an odd digit, then there are 4 choices for an even digit. For an even digit, there are 5 choices for an odd digit. There are 5 locations possible in the integer. What would be a ...
7
votes
2answers
181 views

Showing an alternating sum is positive

I am trying to prove the following for $n > 1$. $$\sum_{k=0}^n (-1)^k \binom{n}{k} \max\{0,n-2k\}^{n-1} > 0.$$ From numerical computations, this seems to be true, but I am struggling to find ...
0
votes
0answers
10 views

probability for maximal result of m randomly generated numbers, solve binomial

I need to solve the following problem: we generate m random numbers where each: $\forall n, n\in [2,20] $ find the probability function of variable $X$ where $X= max(n_1 , n_2 ...,n_m )$ Now, I ...
4
votes
3answers
218 views

Told by Professor that this is PIE, but don't see how it's PIE. Help understanding what constitutes the sets, or alternative ways to solve?

So, basically, my professor has taught us the principle of inclusion and exclusion. We were given the basic formulation of the problem using set theory (A$\cup$B$\cup$C), and then launched into ...
0
votes
0answers
34 views

Bonferroni inequality from probability to sets

I want to prove that the second inequalityis a consequence of the first. If I multiply the first inequality with the space of events $\Omega = A_1\cup\dots\cup A_n $ is it enough? ( I assume this, ...