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.

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?
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 ...
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
81 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
20 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
1answer
37 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 ...
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
38 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\...
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 ...
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 ...
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 ...
3
votes
1answer
50 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$ ...
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 ...
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 ...
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 ...
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 ...
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
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 ...
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$ ...
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 ...
0
votes
3answers
61 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 ...
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
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 ...
2
votes
2answers
104 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 ...
0
votes
0answers
33 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 ...
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
39 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 ...
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
32 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, ...
1
vote
2answers
85 views

An explicit “formula” for the prime counting function?

It is known that $\log(p_1),\cdots,\log(p_n)$ are linearly independet over $\mathbb{Q}$, where $p_i$ denotes the $i$-th prime. For a number $1 \le k \le n$ let $Log(k)$ denote the vector with respect ...
0
votes
1answer
77 views

Colouring the sides of a hexagon

If the walls of a hexagon shaped room are to be painted so that no two adjacent walls get painted the same colour, and there are 10 colours of paint to be chosen from, how many ways can the room be ...
1
vote
1answer
85 views

What is the probability that no 2 books from the same major will be placed next to each other?

4 mathematics, 3 physics, 2 chemistry (all distinct) books are supposed to arrange on a bookshelf randomly. What is the probability that no 2 books from the same major will be placed next to each ...
0
votes
1answer
33 views

Notation for “or” in inclusion-exclusion formula

Suppose that I have a set $A$ and I want to compute the probability that this set contains at least one of the elements $x_1,\dots, x_n$. In other words, $p(x_1 \in A \text{ or } \dots \text{ or } ...
0
votes
1answer
115 views

Positive Integers between 100 and 999 inclusive that are divisible by 3 but not by 4?

I've reviewed this question and a little stuck on the formula presented: Integers divisible by 4 but not by 3 and 16 and was hoping someone could provide some additional details as to the logic being ...
3
votes
2answers
77 views

How many permutations are there of M, M, A, A, A, T, T, E, I, K, so that no two consecutive letters are the same?

How many permutations are there of $$ M, M, A, A, A, T, T, E, I, K $$ so that there are no two consecutive letters are the same? I would use the Inclusion-exclusion principle where $$ A_{i} = \{ \...
3
votes
1answer
100 views

How to count all the solutions for $\sum\limits_{i=1}^{n} \frac{1}{2^{k_i}}= 1$ for $k_i\in \Bbb{N}$ and $n$ a fixed positive integer?

After reading this question, I would like to just count all solutions for: $$\frac{1}{2^{k_1}} + \frac{1}{2^{k_2}} + \frac{1}{2^{k_3}} + \dots + \frac{1}{2^{k_n}}=1$$ for $k_i\in \Bbb{N}$ (we can ...
0
votes
1answer
36 views

Reverse Inclusion - Exclusion Principle

The Inclusion-Exclusion Principle is usually expressed as a way of determining unions from intersections, i.e. $$\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2)$$ $$\...
-2
votes
1answer
28 views

Why does taking floored root of a natural number x give me all natural numbers up to x which are perfect squares,cubes,fifths etc.

Eg. The number of perfect squares from $1$ to $10^{10}$ is $\left(10^{10}\right)^{1/2}= 10^{5}$ Context:I got this question from this one: Count the number of integers in the range $1$ to $10^{10}$ ...
3
votes
0answers
40 views

Calculate $\sum_{|S|=k}(n-|\cup S|)^m$ where $S$ is a subset of $X=\{\{a_1,a_2\},\{a_2,a_3\},\cdots,\{a_{n-1},a_n\},\{a_n,a_1\}\}$

Let $x_i=\{a_i,a_{i+1}\}\ (1 \leq i \leq n-1)$, $x_n=\{a_n,a_1\}$ and $X=\{x_1, \cdots, x_n\}$. Given $n,m$ and $k$, I'd like to ask how to calculate $\sum_{|S|=k}(n-|\cup S|)^m$ where $S$ is a subset ...