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
2answers
20 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
29 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
25 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
30 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
74 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
29 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
48 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
44 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
38 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
137 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
86 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
38 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
59 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
58 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
80 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
9 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
216 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
28 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
84 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
54 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
81 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
94 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
97 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
30 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
39 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 ...
0
votes
0answers
15 views

Inclusion–exclusion principle in projective geometry

In the problems that I have to apply Grassmann in projective geometry, can I use the inclusion-exclusion principle? Consider the following problem: We consider three linear varieties of dimension ...
0
votes
1answer
42 views

How many numbers between $1 - 1000$ leave no remainder when divided by $4$ and when divided by $6$ but not when divided by $21$?

Numbers between $1 - 1000$ which leave no remainder when divided by $4$ and divided by $6$ but not by $21$? I tried $$\frac{1000}{12} = 83 - \frac{83}{21} = 83-3 = 80$$ Am I correct? Can someone ...
7
votes
2answers
177 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
28 views

Principle of I/E: In how many ways can eight cakes be distributed among four kids if every kid receives at least one cake?

Eight cakes are distributed randomly among four kids. Use I/E to determine in how many of the possible distributions every kid receives at least $1$ cake. Hint: Define $A_i$ to be the set of ...
1
vote
2answers
67 views

Counting Surjections with Inclusion-Exclusion

Compute the number of surjective functions $f : [10] → [5]$ using the I/E principle. With Stirling numbers of the second kind, we can obtain the answer with the following way $S(10,5)5!$. How I can ...
0
votes
2answers
131 views

How many numbers from 0 to 99999 contain the digits 2, 5 and 8?

I have this problem: How many integers between 0 and 99999 contain the digits 2, 5 and 8? I've tried a lot, but I don't know how resolve it. P.S. The solution should be 4350.
0
votes
1answer
44 views

What is a k-wise intersection?

I am having a hard time visualizing and conceptualizing what a k-wise intersection is. I am guessing 3-wise intersection for 3 sets: $S_1,S_2,S_3$ would be $(S_1 {\cap}S_2{\cap}S_3)$ and 2-wise ...
2
votes
1answer
28 views

Calculate the expected value of the number of different digits

Question. $n$ is a $m$-digit number. ($m$ can start with zero.) Let $P(n)$ the number of different digits in $n$. What is the expected value of $P(n)$? (For example, $P(12341234)=4$.) My approach. ...
0
votes
1answer
22 views

Is my proof valid? Let $\{A_i\}_{i=0}^{i=n}$ a series of events such that $\forall i$ $P(A_i)=1$. Show that $\bigcap\limits_{0 \leq i \leq n}A_i=1$.

Let $\{A_i\}_{i=0}^{i=n}$ a series of events such that $\forall i$ $P(A_i)=1$. Show that $\bigcap\limits_{0 \leq i \leq n}A_i=1$. My attempt: Let $0\leq k\ne j\leq n$, so $P(A_j)=1, P(A_k)=1$. ...
1
vote
2answers
37 views

Selecting conditional states depending on previous states

I've seen a post which was started as a joke saying : "Well, Guess the code ?" (4 digit code) Apart from the joke , I was thinking , well , how many combinations do we have here , knowing that <...
0
votes
1answer
53 views

4 couples and 4 single people seated at 3 round tables

In how many ways can you seat the 12 people at 3 round tables such that: A) All couples are seated together. (the two members of each couple sit side-by-side) B) No couples sit together. I've ...